Balanced Binary Trees
We have seen that searching a binary tree is very efficient, O(log(n));
however, this is only true if the tree is balanced, i.e. the two
branches of a node have approximately the same height. If the tree is
unbalanced, search time could be worse, perhaps even O(n).
There are several clever algorithms that maintain self-balancing
binary trees; these algorithms re-balance the tree as needed.
- AVL Tree: heights of subtrees differ by at most 1. A node
contains a balance value of -1, 0, or 1, which is the difference
in height of its subtrees. If the balance goes out of this range, the
tree is rebalanced.
- Red-Black Tree: nodes are colored red or black. The
longest path from root to a leaf is no more than twice the length of the
- Splay Tree: the tree is rebalanced so that recently accessed
elements can be accessed quickly the next time.