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 ...)

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 E. Black.

Entry modified 14 August 2008.
HTML page formatted Fri Mar 25 16:20:34 2011.

Cite this as:
Paul E. Black, "balanced tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008. (accessed TODAY) Available from:

to NIST home page