Сол жақ басымдық ағаштары және олардың түрлері

Priority queue implemented with a variant of a binary heap
In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s value which is the distance to the nearest leaf in subtree rooted at x. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s value. The height biased leftist tree was invented by Clark Allan Crane. The name comes from the fact that the left subtree is usually taller than the right subtree. A leftist tree is a mergeable heap. When inserting a new node into a tree, a new one node tree is created and merged into the existing tree. To delete an item, it is replaced by the merge of its left and right sub trees. Both these operations take O(log n) time. For insertions, this is slower than Fibonacci heaps, which support insertion in O(1) (constant) amortized time, and O(log n) worst case. Leftist trees are advantageous because of their ability to merge quickly, compared to binary heaps which take Θ(n). In almost all cases, the merging of skew heaps has better performance. However merging leftist heaps has worst case O(log n) complexity while merging skew heaps has only amortized O(log n) complexity.

The usual leftist tree is a height biased leftist tree.

The s value (or rank) of a node is the distance from that node to the nearest empty position in the subtree rooted at that node. Put another way, the s value of a null child is implicitly zero. Other nodes have an s value equal to one more the minimum of their children's s values. Thus, in the example at right, all nodes with at least one missing child have an s value of 1, while node 4 has an s value of 2, since its right child (8) has an s value of 1. (In some descriptions, the s value of null children is assumed to be −1.) Knowing the shortest path to the nearest missing leaf in the subtree rooted at x is exactly of s(x), every node at depth s(x)−1 or less has exactly 2 children since s(x) would have been less if not. Meaning that the size of the tree rooted at x is at least Thus, s(x) is at most , m being the number of nodes of the subtree rooted at x.==
Leftist trees can also be weight biased. In this case, instead of storing s values in node x, we store an attribute w(x) denoting the number of nodes in the subtree rooted at :

w(x) = w(x. right) + w(x. left) + 1

WBLTs ensure w(x. left) ≥ w(x. right) for all internal nodes x. WBLT operations ensure this invariant by swapping the children of a node when the right subtree outgrows the left one, just as in HBLT operations.

The merge operation in WBLTs can be done using a single top to bottom traversal since the number of nodes in the subtrees are known prior to recursive call to merge. Thus, we can swap left and right subtrees if the total number of nodes in the right subtree and the tree to be merged is bigger than the number of nodes in the left subtree. This allows the operations be completed in a single path and so improves the time complexity of the operations by a constant factor. The merge operation is depicted in the graph below.

Insertions and deletion of the min element can be done in the same as for HBLTs using the merge operation. Although WBLTs outperform HBLTs in merge, insertion and deletion of the Min key by a constant factor, the O(log n) bound is not guaranteed when deleting an arbitrary element from WBLTs, since θ(n) nodes have to be traversed. If this was an HBLT, then deleting the leaf node with key 60 would take O(1) time and updating the s values is not needed since the length of rightmost path for all the nodes does not change. But in an WBLT tree, we have to update the weight of each node back to the root, which takes O(n) worst case.