In a standard Binary Search Tree (BST), the structure depends entirely on the order of insertion. If you insert sorted numbers like 1, 2, 3, 4, 5, the tree becomes a long, skinny chain. Searching this tree is no better than searching a linked list, with a worst-case time complexity of $O(n)$. This defeats the purpose of using a tree in the first place.

Balanced trees solve this problem. They are self-balancing BSTs that automatically adjust their structure during insertions and deletions to ensure the tree remains “bushy.” By keeping the height of the tree minimal, they guarantee that operations like search, insert, and delete consistently perform at a much faster $O(\log n)$ time.

Named after their inventors, Adelson-Velsky and Landis, AVL trees were the first self-balancing binary search trees. They maintain balance by adhering to a simple, strict rule.

To enforce this, each node keeps track of its balance factor, calculated as:

Balance Factor = height(left subtree) - height(right subtree)

In a valid AVL tree, every node must have a balance factor of -1, 0, or 1. A factor of -1 means the right subtree is taller, 1 means the left subtree is taller, and 0 means they are equal in height.

When an insertion or deletion causes a node's balance factor to become -2 or 2, the tree is out of balance. To fix this, the tree performs rotations, which are simple operations that restructure the nodes to restore the balance property.

A Left Rotation is performed when a node becomes unbalanced because of an insertion into its right subtree's right child (a right-right case). There's a corresponding Right Rotation for a left-left case. Sometimes, a single rotation isn't enough. If the imbalance is caused by an insertion into the right subtree's left child (a right-left case), we need a Right-Left Rotation, which is just a right rotation on the child followed by a left rotation on the parent. Similarly, there's a Left-Right Rotation.

While AVL trees are perfectly balanced, this strictness means they can require many rotations to maintain balance after insertions and deletions, which can be slow.

Red-Black trees offer a compromise. They are slightly less balanced than AVL trees but are faster for insertions and deletions because they require fewer rotations. This performance advantage makes them one of the most common balanced trees used in practice, for example in C++'s std::map and std::set.

Red-Black trees maintain balance using five specific properties:

These rules together guarantee that the longest path from the root to any leaf is no more than twice as long as the shortest path. This keeps the tree approximately balanced and ensures $O(\log n)$ performance.

When inserting a new node, it is typically colored Red. If this violates any of the rules (for example, creating two adjacent red nodes), the tree fixes itself using two main operations: recoloring nodes and performing rotations. These fixes are propagated up the tree until all properties are restored.

Splay trees are an interesting and adaptive type of self-balancing tree. They don't have strict height rules like AVL or Red-Black trees. Instead, they have one simple, powerful mechanism: whenever a node is accessed (for a search, insertion, or deletion), it is moved to the root of the tree through a series of rotations. This operation is called splaying.

This self-adjusting behavior makes splay trees excellent for applications where some elements are accessed much more frequently than others, such as in caching or network routing.

The splaying process uses three types of rotations:

1. Zig: A simple rotation when the accessed node's parent is the root.
2. Zig-Zig: A pair of rotations in the same direction, performed when the node and its parent are both left children or both right children.
3. Zig-Zag: A pair of rotations in opposite directions, performed when the node is a right child and its parent is a left child (or vice versa).

While a single operation on a splay tree can be slow ($O(n)$ in the worst case), a sequence of operations is guaranteed to be fast. This is known as amortized analysis. Over a series of M operations, the total time will not exceed $O(M \log n)$, making the average time per operation $O(\log n)$.

With these powerful tree structures, we can manage dynamic sets of data with the assurance of consistently fast performance, a crucial requirement for databases, operating systems, and countless other applications.

Time to check your understanding of these self-balancing trees.