Balanced BSTHow balancing works

01Why it exists

Reach for it when you see:O(log n) even in the worst case, input that may already be sorted, ordered maps, std::map, TreeMap, rotations, AVL, red-black trees, B-trees.

02The core idea

Every BST operation costs O(h), and the trouble is that h can be n. A balanced tree does a little extra work after each modification to keep h at O(log n). The recipe is always the same: define a balance condition, check it on the way back up the modified path, and repair any violation with a rotation. A rotation is an O(1) rearrangement of pointers, and it preserves the in-order sequence, so the BST rule still holds once it is done.

AVL trees take the most direct condition: the two subtrees of every node differ in height by at most 1. When an insert pushes some node's difference to 2, which of four cases applies depends on the direction the new node went: LL needs one right rotation, RR one left rotation, LR rotates the child left and then the node right, and RL is the mirror image. An AVL tree's height is at most about 1.44 log n, which makes lookups the fastest of the lot, but inserts and deletes rotate more often.

Red-black trees loosen the condition: every node is painted red or black, the root must be black, a red node's children must be black, and every root-to-leaf path must contain the same number of black nodes. That guarantees the longest path is no more than twice the shortest, so the height is at most about 2 log n. Lookups are a little slower than in an AVL tree, but each modification costs at most two or three rotations, which is why almost every standard library picks them. B-trees go the other way, packing many keys into each node, designed specifically for disk.

The goal of this lesson is not to memorise the four rotation cases but to understand three things: why balance is needed, why a rotation cannot break the BST property, and that in practice you simply use std::map, TreeMap or SortedList. The occasions on which you have to implement a balanced tree yourself are very rare.

03The algorithm

1. 1Do the ordinary BST insert, and as the recursion returns through each ancestor, update its height and compute the height difference b between its two subtrees.
2. 2If b lies within [−1, 1] nothing is wrong, so return the node unchanged.
3. 3b > 1 (left-heavy): if the new key landed on the right of the left child (LR), rotate the left child left first; then rotate this node right and return the new root.
4. 4b < −1 (right-heavy): if the new key landed on the left of the right child (RL), rotate the right child right first; then rotate this node left.
5. 5After a rotation, remember to update the heights of the two nodes involved, the lower one before the upper one. In practice, use the standard library unless an interviewer asks for more.

04Interactive demo

Inserting 1 through 7 in order, the worst possible input for a BST. The plain BST on the left grows into a chain, while the AVL tree on the right rotates every time it goes out of balance. The b under each node is the difference between its subtree heights.

05Code

Only AVL insertion is implemented; what matters is the two rotation functions and how the four cases are told apart. The end notes which standard-library container to reach for in practice.

# AVL tree: no node's two subtrees differ in height by more than 1. Only insertion is implemented; the point is the rotations.
class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        self.height = 1                      # a leaf counts as height 1, which keeps the arithmetic simple


def h(n):
    return n.height if n else 0

def update(n):
    n.height = 1 + max(h(n.left), h(n.right))

def balance(n):
    return h(n.left) - h(n.right)            # positive means the left side is heavier


def rotate_right(y):
    #      y                x
    #     / \              / \
    #    x   C    -->     A   y
    #   / \                  / \
    #  A   B                B   C
    x = y.left
    y.left = x.right
    x.right = y
    update(y); update(x)                     # update y below first, then x above it
    return x

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update(x); update(y)
    return y


def insert(n, key):
    if n is None:
        return Node(key)
    if key < n.key:
        n.left = insert(n.left, key)
    else:
        n.right = insert(n.right, key)
    update(n)
    b = balance(n)
    if b > 1:                                # left side too heavy
        if key > n.left.key:                 # it landed on the right of the left child (LR): rotate the left child left
            n.left = rotate_left(n.left)
        return rotate_right(n)               # then rotate this node right (LL)
    if b < -1:                               # right side too heavy
        if key < n.right.key:                # RL: rotate the right child right first
            n.right = rotate_right(n.right)
        return rotate_left(n)                # RR
    return n


# In practice, reach for the balanced tree your language ships with instead of writing one:
# Python has none built in, so sortedcontainers.SortedList is the usual choice;
# Java has TreeMap / TreeSet; C++ has std::map / std::set (red-black trees).

06Practice

• LeetCode 110Balanced Binary Tree (check whether it is balanced)Easy
• LeetCode 1382Balance a Binary Search Tree (flatten in order, then rebuild)Medium
• LeetCode 108Convert Sorted Array to Binary Search TreeEasy
• LeetCode 729My Calendar I (use an ordered map to find the neighbouring intervals)Medium
• LeetCode 220Contains Duplicate III (window queries on an ordered set)Hard