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 12 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "leftist tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/leftisttree.html