|
|
|---|
|
|
|
|---|
An implementation of Leftist Trees.
Leftist trees are an efficient implementation of binary heaps. Regular (completely balanced) binary heaps are tricky, and in most cases near impossible, to implement in functional languages because of the need for constant-time access to the last element in the tree (that element being the node in the bottom-most level of the tree, furthest to the right). Leftist trees avoid this by replacing this "balanced" requirement with the requirement that the right-most spine of the tree be small relative to the overal number of elements in the tree. Since the fundamental heap operations (insert, delete-min) only recur on the right spine of the tree in question, this guarantees that these operations are O(log(n)), where n is the size of the tree.
Leftist trees look like this:
(rank root left right)
where "rank" is defined to be the length of the right spine of the tree, "root" is the root element of the tree, "left" is the left sub-tree, and "right" is the right sub-tree.
Leftist trees are heap-ordered, and they are "balanced" in a loose sense. In particular, the size of the tree is at least as big as an exponential function of the rank:
size(tree) >= 2^(rank(tree)) - 1,
or, solving for rank(tree) and noting that the rank is always an integer,
rank(tree) <= floor(log(size(tree) + 1)).
The important tree operations are INSERT-LT, FIND-MIN-LT, and DELETE-MIN-LT. A useful function called BUILD-LT is also provided, which constructs a leftist tree from a list. An important constant is *EMPTY-LT*, which is the empty tree (for this implementation, just NIL).
To learn how to use the trees, see :DOC LEFTIST-TREE-FNS. To see some useful theorems about leftist trees, including the rank bound above, see :DOC LEFTIST-TREE-THMS.
Sources: - Okasaki, Chris. Purely Functional Data Structures. Cambridge, U.K.: Cambridge UP, 1998. 17-20. Print.