NIST

balanced tree

(data structure)

Definition: A tree where no leaf is much farther away from the root than any other leaf. Different balancing schemes allow different definitions of "much farther" and different amounts of work to keep them balanced.

Generalization (I am a kind of ...)
tree.

Specialization (... is a kind of me.)
BB(α) tree, height-balanced tree, B-tree, AVL tree, full binary tree, red-black tree.

See also balance, relaxed balance.

Note: Usually "balanced" means "height balanced".
Called an "admissible tree" by Adelson-Velskii and Landis.

Author: PEB

More information

[Knuth98, 3:459, Sect. 6.2.3]


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 14 August 2008.
HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:
Paul E. Black, "balanced tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 14 August 2008. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/balancedtree.html