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

Entry modified 23 May 2011.

HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:

Paul E. Black, "balanced binary tree", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 23 May 2011. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/balancedbitr.html