Leftist Tree

A height-balanced binary tree that is sufficiently ordered that the highest priority node is guaranteed to be at the root. Balance is maintained by rotating the tree so that the root's left or right node becomes the new root. The root can be removed and the left and right subtrees merged into a new leftist tree.

See http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch8.html

Just curious: why are they called leftist trees? I assume this has nothing to do with readers of The Nation :-)

At first, I thought "leftist tree" was another name for the following "tree stored in linear array" data structure, but after I read http://en.wikipedia.org/wiki/Leftist_tree, it seems to be something completely different (?).

"tree stored in linear array" data structure. (Is there another name for this?)

Some people store a tree in a packed, consecutive, linear array (rather than as independent little nodes linked with pointers).

An array with addresses (offsets)

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

can hold a tree.

the "left child" of the node at address N is at address 2*N.
"right child" of the node at address N is at address (2*N)+1.
The "parent" of the node at address N is at address floor(N/2).

If the entire array is packed solid with nodes, the array can be thought of as a tree something like this:

                   1
          2                    3
      4        5           6       7
   8     9   10 11       12 13   14 15
 16 17

Not only is this tree as balanced as a 17-node binary tree can possibly be (all leaf nodes are either 3 or 4 hops from the root node), but also the leaves on the bottom row are all packed "to the left" ("leftist"?).

When a binary tree has this sort of structure, packing it into a linear array takes less storage than the traditional "independent nodes linked with pointers", because no pointers have to be stored.

When the array is packed solid with nodes from 1 to N, the array has

non-leaf nodes from 1 to floor(N/2).
leaf nodes from 1+floor(N/2) to N.

When the array is not packed solid, there are "holes" in the array. If the tree is balanced, no more than half the array is "wasted" by these empty holes - the non-leaf nodes are still packed, followed by the leaf nodes, but there may be gaps between the leaves. If the tree is unbalanced, even more of the tree can be "wasted" by these empty holes - in that case, the traditional "independent nodes linked with pointers" might take less storage.

Compare and contrast with a HeapDataStructure.