balanced binary tree

(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

Implementation

red-black tree analysis, explanation, examples, and code (C). Ben Pfaff's AVL tree explanation (C).

More information

AVL tree explanation and example

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 Thu Oct 27 09:59:18 2005.
HTML page formatted Thu Oct 27 10:13:08 2005.

Cite this as:
Paul E. Black, "balanced binary tree", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/balancedbitr.html