Leftist tree · Lablypedia

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.

Bias

The usual leftist tree is a height-biased leftist tree. However, other biases can exist, such as in the weight-biased leftist tree.

The exact worst-case complexity of both types of leftist trees is 2 log₂ n, counting comparisons. The exact amortized complexity of weight-biased leftist trees is known to match the log_φ n (approximately 1.44 log₂ n) exact amortized complexity of skew heaps, where φ denotes the golden ratio; similarly, the amortized complexity of height-biased leftist trees is bounded below by log_φ n, but whether this is also the upper bound is an open problem.

4 more chapters are free with a Lably account.

S-value

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 $2^{s (x)} - 1$ . Thus, s(x) is at most $\log (m + 1)$ , m being the number of nodes of the subtree rooted at x.

Operations on a height biased leftist tree

Most operations on a Height Biased Leftist Tree are done using the merge operation.

Merging two Min HBLTs

The merge operation takes two Min HBLTs as input and returns a Min HBLT containing all the nodes in the original Min HBLTs put together.

If either tree empty, the merged tree is the other. Otherwise, label their roots A and B so that A.key ≤ B.key. To preserve the heap property, A must be the root of the merged tree.

The merge is done by recursively merging B with A's right subtree. This may increase the s-value of A's right subtree, and thus A's s-value. If the result has a greater s-value than A's left subtree, swap the two subtrees to maintain the leftist tree property.

Pseudocode for merging two min height biased leftist trees

MERGE(A, B) <b id="mwaw">if</b> A = null <b id="mwbA">return</b> B <b id="mwbQ">if</b> B = null <b id="mwbg">return</b> A <b id="mwbw">if</b> A.key > B.key <b id="mwcA">return</b> MERGE(B, A) A.right := MERGE (A.right, B) <i id="mwcQ">// the result cannot be null since B is non-null</i> <b id="mwcg">if</b> A.left = null <b id="mwcw">then</b> SWAP(A.left, A.right) A.s_value := 1 <i id="mwdA">// since the right subtree is null, the shortest path to a descendant leaf from node A is 1</i> <b id="mwdQ">return</b> A <b id="mwdg">if</b> A.right.s_value > A.left.s_value <b id="mwdw">then</b> SWAP(A.right, A.left) A.s_value := A.right.s_value + 1 <b id="mweA">return</b> A

Java code for merging two min height biased leftist trees

<span id="mwfA"></span><span class="kd" id="mwfQ">public</span><span class="w" id="mwfg"> </span><span class="n" id="mwfw">Node</span><span class="w" id="mwgA"> </span><span class="nf" id="mwgQ">merge</span><span class="p" id="mwgg">(</span><span class="n" id="mwgw">Node</span><span class="w" id="mwhA"> </span><span class="n" id="mwhQ">a</span><span class="p" id="mwhg">,</span><span class="w" id="mwhw"> </span><span class="n" id="mwiA">Node</span><span class="w" id="mwiQ"> </span><span class="n" id="mwig">b</span><span class="p" id="mwiw">)</span><span class="w" id="mwjA"> </span><span class="p" id="mwjQ">{</span> <span class="w" id="mwjg"> </span><span class="k" id="mwjw">if</span><span class="w" id="mwkA"> </span><span class="p" id="mwkQ">(</span><span class="n" id="mwkg">a</span><span class="w" id="mwkw"> </span><span class="o" id="mwlA">==</span><span class="w" id="mwlQ"> </span><span class="kc" id="mwlg">null</span><span class="p" id="mwlw">)</span> <span class="w" id="mwmA"> </span><span class="k" id="mwmQ">return</span><span class="w" id="mwmg"> </span><span class="n" id="mwmw">b</span><span class="p" id="mwnA">;</span> <span class="w" id="mwnQ"> </span><span class="k" id="mwng">if</span><span class="w" id="mwnw"> </span><span class="p" id="mwoA">(</span><span class="n" id="mwoQ">b</span><span class="w" id="mwog"> </span><span class="o" id="mwow">==</span><span class="w" id="mwpA"> </span><span class="kc" id="mwpQ">null</span><span class="p" id="mwpg">)</span><span class="w" id="mwpw"> </span> <span class="w" id="mwqA"> </span><span class="k" id="mwqQ">return</span><span class="w" id="mwqg"> </span><span class="n" id="mwqw">a</span><span class="p" id="mwrA">;</span> <span class="w" id="mwrQ"> </span><span class="c1" id="mwrg">// Reverse the sense of this comparison for a max-heap</span> <span class="w" id="mwrw"> </span><span class="k" id="mwsA">if</span><span class="w" id="mwsQ"> </span><span class="p" id="mwsg">(</span><span class="n" id="mwsw">a</span><span class="p" id="mwtA">.</span><span class="na" id="mwtQ">element</span><span class="p" id="mwtg">.</span><span class="na" id="mwtw">compareTo</span><span class="p" id="mwuA">(</span><span class="n" id="mwuQ">b</span><span class="p" id="mwug">.</span><span class="na" id="mwuw">element</span><span class="p" id="mwvA">)</span><span class="w" id="mwvQ"> </span><span class="o" id="mwvg">></span><span class="w" id="mwvw"> </span><span class="mi" id="mwwA">0</span><span class="p" id="mwwQ">)</span><span class="w" id="mwwg"> </span><span class="p" id="mwww">{</span> <span class="w" id="mwxA"> </span><span class="n" id="mwxQ">Node</span><span class="w" id="mwxg"> </span><span class="n" id="mwxw">temp</span><span class="w" id="mwyA"> </span><span class="o" id="mwyQ">=</span><span class="w" id="mwyg"> </span><span class="n" id="mwyw">a</span><span class="p" id="mwzA">;</span> <span class="w" id="mwzQ"> </span><span class="n" id="mwzg">a</span><span class="w" id="mwzw"> </span><span class="o" id="mw0A">=</span><span class="w" id="mw0Q"> </span><span class="n" id="mw0g">b</span><span class="p" id="mw0w">;</span> <span class="w" id="mw1A"> </span><span class="n" id="mw1Q">b</span><span class="w" id="mw1g"> </span><span class="o" id="mw1w">=</span><span class="w" id="mw2A"> </span><span class="n" id="mw2Q">temp</span><span class="p" id="mw2g">;</span> <span class="w" id="mw2w"> </span><span class="p" id="mw3A">}</span> <span class="w" id="mw3Q"> </span><span class="k" id="mw3g">if</span><span class="w" id="mw3w"> </span><span class="p" id="mw4A">(</span><span class="n" id="mw4Q">a</span><span class="p" id="mw4g">.</span><span class="na" id="mw4w">leftChild</span><span class="w" id="mw5A"> </span><span class="o" id="mw5Q">==</span><span class="w" id="mw5g"> </span><span class="kc" id="mw5w">null</span><span class="p" id="mw6A">)</span><span class="w" id="mw6Q"> </span><span class="p" id="mw6g">{</span> <span class="w" id="mw6w"> </span><span class="k" id="mw7A">assert</span><span class="w" id="mw7Q"> </span><span class="n" id="mw7g">a</span><span class="p" id="mw7w">.</span><span class="na" id="mw8A">rightChild</span><span class="w" id="mw8Q"> </span><span class="o" id="mw8g">==</span><span class="w" id="mw8w"> </span><span class="kc" id="mw9A">null</span><span class="p" id="mw9Q">;</span><span class="w" id="mw9g"> </span><span class="c1" id="mw9w">// By the leftist property</span> <span class="w" id="mw-A"> </span><span class="c1" id="mw-Q">// neither child exists, so trivial merge into left child.</span> <span class="w" id="mw-g"> </span><span class="n" id="mw-w">a</span><span class="p" id="mw_A">.</span><span class="na" id="mw_Q">leftChild</span><span class="w" id="mw_g"> </span><span class="o" id="mw_w">=</span><span class="w" id="mwAQA"> </span><span class="n" id="mwAQE">b</span><span class="p" id="mwAQI">;</span> <span class="w" id="mwAQM"> </span><span class="k" id="mwAQQ">assert</span><span class="w" id="mwAQU"> </span><span class="n" id="mwAQY">a</span><span class="p" id="mwAQc">.</span><span class="na" id="mwAQg">s</span><span class="w" id="mwAQk"> </span><span class="o" id="mwAQo">==</span><span class="w" id="mwAQs"> </span><span class="mi" id="mwAQw">1</span><span class="p" id="mwAQ0">;</span> <span class="w" id="mwAQ4"> </span><span class="p" id="mwAQ8">}</span><span class="w" id="mwARA"> </span><span class="k" id="mwARE">else</span><span class="w" id="mwARI"> </span><span class="p" id="mwARM">{</span> <span class="w" id="mwARQ"> </span><span class="n" id="mwARU">Node</span><span class="w" id="mwARY"> </span><span class="n" id="mwARc">temp</span><span class="w" id="mwARg"> </span><span class="o" id="mwARk">=</span><span class="w" id="mwARo"> </span><span class="n" id="mwARs">merge</span><span class="p" id="mwARw">(</span><span class="n" id="mwAR0">a</span><span class="p" id="mwAR4">.</span><span class="na" id="mwAR8">rightChild</span><span class="p" id="mwASA">,</span><span class="w" id="mwASE"> </span><span class="n" id="mwASI">b</span><span class="p" id="mwASM">);</span> <span class="w" id="mwASQ"> </span><span class="k" id="mwASU">if</span><span class="w" id="mwASY"> </span><span class="p" id="mwASc">(</span><span class="n" id="mwASg">a</span><span class="p" id="mwASk">.</span><span class="na" id="mwASo">leftChild</span><span class="p" id="mwASs">.</span><span class="na" id="mwASw">s</span><span class="w" id="mwAS0"> </span><span class="o" id="mwAS4"><</span><span class="w" id="mwAS8"> </span><span class="n" id="mwATA">temp</span><span class="p" id="mwATE">.</span><span class="na" id="mwATI">s</span><span class="p" id="mwATM">)</span><span class="w" id="mwATQ"> </span><span class="p" id="mwATU">{</span> <span class="w" id="mwATY"> </span><span class="n" id="mwATc">a</span><span class="p" id="mwATg">.</span><span class="na" id="mwATk">rightChild</span><span class="w" id="mwATo"> </span><span class="o" id="mwATs">=</span><span class="w" id="mwATw"> </span><span class="n" id="mwAT0">a</span><span class="p" id="mwAT4">.</span><span class="na" id="mwAT8">leftChild</span><span class="p" id="mwAUA">;</span> <span class="w" id="mwAUE"> </span><span class="n" id="mwAUI">a</span><span class="p" id="mwAUM">.</span><span class="na" id="mwAUQ">leftChild</span><span class="w" id="mwAUU"> </span><span class="o" id="mwAUY">=</span><span class="w" id="mwAUc"> </span><span class="n" id="mwAUg">temp</span><span class="p" id="mwAUk">;</span> <span class="w" id="mwAUo"> </span><span class="p" id="mwAUs">}</span><span class="w" id="mwAUw"> </span><span class="k" id="mwAU0">else</span><span class="w" id="mwAU4"> </span><span class="p" id="mwAU8">{</span> <span class="w" id="mwAVA"> </span><span class="n" id="mwAVE">a</span><span class="p" id="mwAVI">.</span><span class="na" id="mwAVM">rightChild</span><span class="w" id="mwAVQ"> </span><span class="o" id="mwAVU">=</span><span class="w" id="mwAVY"> </span><span class="n" id="mwAVc">temp</span><span class="p" id="mwAVg">;</span> <span class="w" id="mwAVk"> </span><span class="p" id="mwAVo">}</span> <span class="w" id="mwAVs"> </span><span class="c1" id="mwAVw">// since we know the right child has the lower s-value,</span> <span class="w" id="mwAV0"> </span><span class="c1" id="mwAV4">// we can just add one to its s-value</span> <span class="w" id="mwAV8"> </span><span class="n" id="mwAWA">a</span><span class="p" id="mwAWE">.</span><span class="na" id="mwAWI">s</span><span class="w" id="mwAWM"> </span><span class="o" id="mwAWQ">=</span><span class="w" id="mwAWU"> </span><span class="n" id="mwAWY">a</span><span class="p" id="mwAWc">.</span><span class="na" id="mwAWg">rightChild</span><span class="p" id="mwAWk">.</span><span class="na" id="mwAWo">s</span><span class="w" id="mwAWs"> </span><span class="o" id="mwAWw">+</span><span class="w" id="mwAW0"> </span><span class="mi" id="mwAW4">1</span><span class="p" id="mwAW8">;</span> <span class="w" id="mwAXA"> </span><span class="p" id="mwAXE">}</span> <span class="w" id="mwAXI"> </span><span class="k" id="mwAXM">return</span><span class="w" id="mwAXQ"> </span><span class="n" id="mwAXU">a</span><span class="p" id="mwAXY">;</span> <span class="p" id="mwAXc">}</span>

Haskell code for merging two min height biased leftist trees

<span id="mwAXs"></span><span class="kr" id="mwAXw">data</span><span class="w" id="mwAX0"> </span><span class="kt" id="mwAX4">LHeap</span><span class="w" id="mwAX8"> </span><span class="n" id="mwAYA">a</span> <span class="w" id="mwAYE"> </span><span class="ow" id="mwAYI">=</span><span class="w" id="mwAYM"> </span><span class="kt" id="mwAYQ">Leaf</span> <span class="w" id="mwAYU"> </span><span class="o" id="mwAYY">|</span><span class="w" id="mwAYc"> </span><span class="kt" id="mwAYg">Node</span><span class="w" id="mwAYk"> </span><span class="n" id="mwAYo">a</span><span class="w" id="mwAYs"> </span><span class="p" id="mwAYw">(</span><span class="kt" id="mwAY0">LHeap</span><span class="w" id="mwAY4"> </span><span class="n" id="mwAY8">a</span><span class="p" id="mwAZA">)</span><span class="w" id="mwAZE"> </span><span class="p" id="mwAZI">(</span><span class="kt" id="mwAZM">LHeap</span><span class="w" id="mwAZQ"> </span><span class="n" id="mwAZU">a</span><span class="p" id="mwAZY">)</span> <span class="nf" id="mwAZc">rank</span><span class="w" id="mwAZg"> </span><span class="ow" id="mwAZk">::</span><span class="w" id="mwAZo"> </span><span class="kt" id="mwAZs">LHeap</span><span class="w" id="mwAZw"> </span><span class="n" id="mwAZ0">a</span><span class="w" id="mwAZ4"> </span><span class="ow" id="mwAZ8">-></span><span class="w" id="mwAaA"> </span><span class="kt" id="mwAaE">Integer</span> <span class="nf" id="mwAaI">rank</span><span class="w" id="mwAaM"> </span><span class="kt" id="mwAaQ">Leaf</span><span class="w" id="mwAaU"> </span><span class="ow" id="mwAaY">=</span><span class="w" id="mwAac"> </span><span class="mi" id="mwAag">0</span> <span class="nf" id="mwAak">rank</span><span class="w" id="mwAao"> </span><span class="p" id="mwAas">(</span><span class="kt" id="mwAaw">Node</span><span class="w" id="mwAa0"> </span><span class="kr" id="mwAa4">_</span><span class="w" id="mwAa8"> </span><span class="kr" id="mwAbA">_</span><span class="w" id="mwAbE"> </span><span class="n" id="mwAbI">r</span><span class="p" id="mwAbM">)</span><span class="w" id="mwAbQ"> </span><span class="ow" id="mwAbU">=</span><span class="w" id="mwAbY"> </span><span class="n" id="mwAbc">rank</span><span class="w" id="mwAbg"> </span><span class="n" id="mwAbk">r</span><span class="w" id="mwAbo"> </span><span class="o" id="mwAbs">+</span><span class="w" id="mwAbw"> </span><span class="mi" id="mwAb0">1</span> <span class="nf" id="mwAb4">merge</span><span class="w" id="mwAb8"> </span><span class="ow" id="mwAcA">::</span><span class="w" id="mwAcE"> </span><span class="kt" id="mwAcI">Ord</span><span class="w" id="mwAcM"> </span><span class="n" id="mwAcQ">a</span><span class="w" id="mwAcU"> </span><span class="ow" id="mwAcY">=></span><span class="w" id="mwAcc"> </span><span class="kt" id="mwAcg">LHeap</span><span class="w" id="mwAck"> </span><span class="n" id="mwAco">a</span><span class="w" id="mwAcs"> </span><span class="ow" id="mwAcw">-></span><span class="w" id="mwAc0"> </span><span class="kt" id="mwAc4">LHeap</span><span class="w" id="mwAc8"> </span><span class="n" id="mwAdA">a</span><span class="w" id="mwAdE"> </span><span class="ow" id="mwAdI">-></span><span class="w" id="mwAdM"> </span><span class="kt" id="mwAdQ">LHeap</span><span class="w" id="mwAdU"> </span><span class="n" id="mwAdY">a</span> <span class="nf" id="mwAdc">merge</span><span class="w" id="mwAdg"> </span><span class="kt" id="mwAdk">Leaf</span><span class="w" id="mwAdo"> </span><span class="n" id="mwAds">h</span><span class="w" id="mwAdw"> </span><span class="ow" id="mwAd0">=</span><span class="w" id="mwAd4"> </span><span class="n" id="mwAd8">h</span> <span class="nf" id="mwAeA">merge</span><span class="w" id="mwAeE"> </span><span class="n" id="mwAeI">h</span><span class="w" id="mwAeM"> </span><span class="kt" id="mwAeQ">Leaf</span><span class="w" id="mwAeU"> </span><span class="ow" id="mwAeY">=</span><span class="w" id="mwAec"> </span><span class="n" id="mwAeg">h</span> <span class="nf" id="mwAek">merge</span><span class="w" id="mwAeo"> </span><span class="n" id="mwAes">h</span><span class="o" id="mwAew">@</span><span class="p" id="mwAe0">(</span><span class="kt" id="mwAe4">Node</span><span class="w" id="mwAe8"> </span><span class="n" id="mwAfA">a</span><span class="w" id="mwAfE"> </span><span class="n" id="mwAfI">l</span><span class="w" id="mwAfM"> </span><span class="n" id="mwAfQ">r</span><span class="p" id="mwAfU">)</span><span class="w" id="mwAfY"> </span><span class="n" id="mwAfc">h'</span><span class="o" id="mwAfg">@</span><span class="p" id="mwAfk">(</span><span class="kt" id="mwAfo">Node</span><span class="w" id="mwAfs"> </span><span class="n" id="mwAfw">a'</span><span class="w" id="mwAf0"> </span><span class="kr" id="mwAf4">_</span><span class="w" id="mwAf8"> </span><span class="kr" id="mwAgA">_</span><span class="p" id="mwAgE">)</span> <span class="w" id="mwAgI"> </span><span class="o" id="mwAgM">|</span><span class="w" id="mwAgQ"> </span><span class="n" id="mwAgU">a</span><span class="w" id="mwAgY"> </span><span class="o" id="mwAgc">></span><span class="w" id="mwAgg"> </span><span class="n" id="mwAgk">a'</span><span class="w" id="mwAgo"> </span><span class="ow" id="mwAgs">=</span><span class="w" id="mwAgw"> </span><span class="n" id="mwAg0">merge</span><span class="w" id="mwAg4"> </span><span class="n" id="mwAg8">h'</span><span class="w" id="mwAhA"> </span><span class="n" id="mwAhE">h</span> <span class="w" id="mwAhI"> </span><span class="o" id="mwAhM">|</span><span class="w" id="mwAhQ"> </span><span class="n" id="mwAhU">rank</span><span class="w" id="mwAhY"> </span><span class="n" id="mwAhc">r'</span><span class="w" id="mwAhg"> </span><span class="o" id="mwAhk">></span><span class="w" id="mwAho"> </span><span class="n" id="mwAhs">rank</span><span class="w" id="mwAhw"> </span><span class="n" id="mwAh0">l</span><span class="w" id="mwAh4"> </span><span class="ow" id="mwAh8">=</span><span class="w" id="mwAiA"> </span><span class="kt" id="mwAiE">Node</span><span class="w" id="mwAiI"> </span><span class="n" id="mwAiM">a</span><span class="w" id="mwAiQ"> </span><span class="n" id="mwAiU">r'</span><span class="w" id="mwAiY"> </span><span class="n" id="mwAic">l</span> <span class="w" id="mwAig"> </span><span class="o" id="mwAik">|</span><span class="w" id="mwAio"> </span><span class="n" id="mwAis">otherwise</span><span class="w" id="mwAiw"> </span><span class="ow" id="mwAi0">=</span><span class="w" id="mwAi4"> </span><span class="kt" id="mwAi8">Node</span><span class="w" id="mwAjA"> </span><span class="n" id="mwAjE">a</span><span class="w" id="mwAjI"> </span><span class="n" id="mwAjM">l</span><span class="w" id="mwAjQ"> </span><span class="n" id="mwAjU">r'</span> <span class="w" id="mwAjY"> </span><span class="kr" id="mwAjc">where</span><span class="w" id="mwAjg"> </span><span class="n" id="mwAjk">r'</span><span class="w" id="mwAjo"> </span><span class="ow" id="mwAjs">=</span><span class="w" id="mwAjw"> </span><span class="n" id="mwAj0">merge</span><span class="w" id="mwAj4"> </span><span class="n" id="mwAj8">r</span><span class="w" id="mwAkA"> </span><span class="n" id="mwAkE">h'</span>

Example

An example of how the merge operation in a leftist tree works is depicted. 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. In this case we swapped the subtrees rooted at nodes with keys 7 and 10.

Insertion into a Min HBLT

Insertion is done using the merge operation. An insertion of a node into an already existing Min HBLT, creates a HBLT tree of size one with that node and merges it with the existing tree.

INSERT (<i id="mwAn8">A</i>, <i id="mwAoA">x</i>) <i id="mwAoE">B</i> := CREATE_TREE(<i id="mwAoI">x</i>) <b id="mwAoM">return</b> MERGE(<i id="mwAoQ">A</i>, <i id="mwAoU">B</i>)

Deletion of Min element from Min HBLT

The Min element in a Min HBLT is the root. Thus, in order to delete the Min, the root is deleted and its subtrees are merged to form the new Min HBLT.

DELETE_MIN(<i id="mwAok">A</i>) <i id="mwAoo">x</i> := <i id="mwAos">A</i>.key <i id="mwAow">A</i> := MERGE (<i id="mwAo0">A</i>.right, <i id="mwAo4">A</i>.left) <b id="mwAo8">return</b> <i id="mwApA">x</i>

Initializing a height biased leftist tree

Initializing a height biased leftist tree is primarily done in one of two ways. The first is to merge each node one at a time into one HBLT. This process is inefficient and takes O(nlogn) time. The other approach is to use a queue to store each node and resulting tree. The first two items in the queue are removed, merged, and placed back into the queue. This can initialize a HBLT in O(n) time. This approach is detailed in the three diagrams supplied. A min height biased leftist tree is shown.

To initialize a min HBLT, place each element to be added to the tree into a queue. In the example (see Part 1 to the left), the set of numbers [4, 8, 10, 9, 1, 3, 5, 6, 11] are initialized. Each line of the diagram represents another cycle of the algorithm, depicting the contents of the queue. The first five steps are easy to follow. Notice that the freshly created HBLT is added to the end of the queue. In the fifth step, the first occurrence of an s-value greater than 1 occurs. The sixth step shows two trees merged with each other, with predictable results.

In part 2 a slightly more complex merge happens. The tree with the lower value (tree x) has a right child, so merge must be called again on the subtree rooted by tree x's right child and the other tree. After the merge with the subtree, the resulting tree is put back into tree x. The s-value of the right child (s=2) is now greater than the s-value of the left child (s=1), so they must be swapped. The s-value of the root node 4 is also now 2.

Part 3 is the most complex. Here, we recursively call merge twice (each time with the right child 's subtree that is not grayed out). This uses the same process described for part 2.

Deletion of an arbitrary element from a Min HBLT

If we have a pointer to a node x in a Min HBLT, we can delete it as follows: Replace the node x with the result of merging its two subtrees and update the s-values of the nodes on the path from x to the root, swapping the right and left subtrees if necessary to maintain the leftist tree property.

The upward traversal is continued until either we hit the root or the s-value does not change. Since we are deleting an element, the S-values on the path traversed cannot be increased. Every node that is already the right child of its parent and causes its parent's s-value to be decreased, will remain on the right. Every node that is its parent's left child and causes the parent's s-value to be decreased has to be swapped with its right sibling if the s-value becomes lower than the current s-value of the right child.

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

When the traversal ends at some node y, the nodes traversed all lie on the rightmost path rooted at node y. An example is shown below. It follows that the number of nodes traversed is at most log(m), m being the size of the subtree rooted at y. Thus, this operation also takes O(lg m) to perform.

Weight biased leftist tree

Leftist trees can also be weight biased. In this case, instead of storing s-values in node x, we store an attribute w(x), the weight of x, denoting the number of nodes in the subtree rooted at x:

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.

A closely related concept, the maxiphobic heap, is just an arbitrary binary tree, where each node tracks its own weight as above, but the merge operation merges the two subtrees with the smallest weights among the three. As such, it differs from WBLT by recomputing the smaller subtree on demand instead of maintaining the w(x.left) ≥ w(x.right) invariant, and allowing recursively merging two children previously had the same parent in the recursive step.

Merging two WBLTs

The merge operation in WBLTs is simplified, because the weight of a merged subtree, and this the decision to swap children, can be computed before the merge is performed. Thus, the merge can be performed in a single top-to-bottom traversal, without recursion. This improves the time complexity of merging by a constant factor.

The merge operation in a Min WBLT is depicted in the graph below.

Other operations on WBLT

Insertions and deletion of the min element are performed in the same matter as for HBLTs, and benefit from the faster merge operation.

However, the O(log n) bound is not guaranteed when deleting an arbitrary element from a WBLT, since θ(n) weights may have to be updated.

If this were an HBLT, then deleting the leftmost leaf node with key 60 would take O(1) time and require no change to any s-value, since the length of the rightmost path for its parent (and thus all of its ancestors) does not change.

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

Variants

Several variations on the basic leftist tree exist, which make only minor changes to the basic algorithm:

The choice of the left child as the taller one is arbitrary; a "rightist tree" would work just as well.
It is possible to avoid swapping children, but instead record which child is the tallest (in, for example, the least significant bit of the s-value) and use that in the merge operation.
The s-value used to decide which side to merge with could use a metric other than height. For example, weight (number of nodes) could be used.