(data structure)
Definition: A binary tree where no leaf is more than a certain amount farther from the root than any other. After inserting or deleting a node, the tree may rebalanced with "rotations."
Generalization (I am a kind of ...)
binary tree.
Specialization (... is a kind of me.)
AVL tree, red-black tree, B-tree, balanced binary search tree.
Aggregate child (... is a part of or used in me.)
left rotation, right rotation.
See also BB(α) tree, height-balanced tree.
Author: PEB
AVL tree explanation and example
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 27 October 2005.
HTML page formatted Mon Sep 11 09:46:00 2006.
Cite this as:
Paul E. Black, "balanced binary tree", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 27 October 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/balancedbitr.html