leftist tree

(data structure)

Definition: A priority queue implemented with a variant of a binary tree. Every node has a count which is the distance to the nearest leaf. In addition to the heap property, leftist trees are kept so the right descendant of each node has the shorter distance to a leaf.

Generalization (I am a kind of ...)
priority queue.

Aggregate child (... is a part of or used in me.)
binary tree, heap property.

Note: These are called "leftist" because the left subtrees are usually taller than the right subtrees.

Author: PEB

Implementation

merge and delete (C and Pascal) which use distance (C and Pascal), insert (C and Pascal)

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 16 November 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "leftist tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 16 November 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/leftisttree.html