Leftist tree

Every node x has an s-value which is the distance to the nearest leaf in subtree rooted at x.

[1] 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.

Leftist trees are advantageous because of their ability to merge quickly, compared to binary heaps which take Θ(n).

[4]) 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.

To maintain the leftist tree property, after each merge is done, we check if the S-value of right subtree became bigger than the S-value of left subtree during the recursive merge calls.

The boxes represent each merge call.When the recursion unwinds, we swap left and right children if x.right.s_value > x.left.s_value for every node x.

Initializing a height biased leftist tree is primarily done in one of two ways.

To initialize a min HBLT, place each element to be added to the tree into a queue.

Each line of the diagram represents another cycle of the algorithm, depicting the contents of the queue.

Notice that the freshly created HBLT is added to the end of the queue.

The sixth step shows two trees merged with each other, with predictable results.

Here, we recursively call merge twice (each time with the right child 's subtree that is not grayed out).

The upward traversal is continued until either we hit the root or the s-value does not change.

Each node needs to have a pointer to its parent, so that we can traverse the path to the root updating the s-values.

It follows that the number of nodes traversed is at most log(m), m being the size of the subtree rooted at y.

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.

But in an WBLT tree, we have to update the weight of each node back to the root, which takes O(n) worst case.