Balanced Trees

Definition of balanced-trees

• Height balanced
• Null-path-length balanced
• Weight balanced

Note: If a tree satisfies the definition of any of such definitions, its height is $\Theta(\ln n)$

Height balancing: AVL-trees

Null-path-length balancing: Red-black Trees

Red-black trees maintain balanced by coloring the nodes red/black (0,1).

Red-black trees are null-path-length balanced. Null-path length going through a subtree must not be greater than another subtree.

Coloring Requirements:

• Root must b black
• All children of a red node must b black
• Any path from the root node to an empty node must have the same number of black nodes

Weight-balanced Trees

• A null subtree/empty node is any position in a binary tree that a new node can be inserted.

• The fraction of empty nodes in the left subtree and the right subtrees

• $BB(\alpha)$: if the fraction on both sides (left and right) remains with the range $[\alpha, 1-\alpha]$