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. Usually "balanced"
means "height balanced". Called an "admissible tree" by Adelson-
Velskii and Landis. [Knuth98, 3:459, Sect. 6.2.3] 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: http://www.nist.gov/dads/HTML/balancedtree.html