Height-Biased Leftist Trees

Definitions

An external node is an imaginary node in a location of a missing child.

Notation. Let the s-value of a node be the shortest distance from the node to an external node.

• An external node has the s-value of 0.
• An internal node has the s-value of 1 plus the minimum of the s-values of its internal and external children.

In a height-biased leftist tree the s-value of a left child of a node is not smaller than the s-value of the right child of the node.

height-biased	non height-biased

Merging Height-Biased Leftist Trees

Recursive algorithm

• Consider two nonempty height-biased leftist trees A and B, and a relation (e.g., smaller than) on the values of the keys.
• Assume the key-value of A is not bigger than the key-value of B
• Let the root of the merged tree have the same left subtree as the root of A
• Let the root of the merged tree have the right subtree obtained by merging B with the right subtree of A.
• If in the merged tree the s-value of the left subtree is smaller than the s-value of the right subtree, interchange the subtrees.

For the following example, assume the key-value of each node equals its s-value.

Time complexity

• Linear in the rightmost path of the outcome tree.
• The rightmost path of the the outcome tree is a shortest path
• A shortest path can’t contain more than log n nodes.
  Proof If the shortest path can contain more than log n nodes, then the first 1 + log n levels should include 2⁰ + 2¹ +  + 2^log n = 2^1+log n - 1 = 2n - 1 nodes. In such a case, for n > 1 we end up with n > 2n - 1.

Application: Priority Queues

A data type which elements may be added in arbitrary order, but can be removed in order that fits a priority function.

Assumption for the examples of this section: priority goes for the largest value.

Merge

Use general keys, instead of the s-values, for determining the roots.

Time Complexity O(log n)

Add

The added element is treated as a height-biased leftist tree to be merged with the tree representing the queue.

Delete

Delete the root then merge the two subtrees.

Initialization

Brute Force: Use the add operation repeatedly. Time complexity O(n log n)

Specialized Approach:

1. Insert the given elements into a queue, taking each of them to be a height-biased leftist tree.
2. As long as the queue contains more than one tree, remove the next pair of trees from the queue, merge these tree, and insert the outcome to the queue.

Time complexity: (n/2)  O(1) + (n/4)  O(2) + (n/8)  O(3) +  = O(n)

Weight-Biased Leftist Trees

A variant of the height-biased leftist tree, in which the s-value of a node is the number of nodes in the subtree defined by the node.