Balanced Trees

Overview

A balanced binary search tree keeps its height at O(log n) by rotating nodes on insert and delete, so search, insert, and delete are all O(log n) worst case — unlike a plain BST that can degrade to O(n) when data arrives sorted. Common variants are AVL trees (strict height balance) and red-black trees (looser balance, used in most standard libraries). The example below implements an AVL tree, which rebalances whenever a node's subtree heights differ by more than one.

Syntax / Usage

Track each node's height and rotate when the balance factor exceeds one.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1


def height(node):
    return node.height if node else 0


def balance_factor(node):
    return height(node.left) - height(node.right)


def update_height(node):
    node.height = 1 + max(height(node.left), height(node.right))


def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update_height(y)
    update_height(x)
    return x


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

Examples

Insert keys while rebalancing so the tree stays O(log n) tall:

def insert(node, key):           # O(log n)
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    update_height(node)
    bf = balance_factor(node)

    if bf > 1 and key < node.left.key:        # left-left
        return rotate_right(node)
    if bf < -1 and key > node.right.key:      # right-right
        return rotate_left(node)
    if bf > 1 and key > node.left.key:        # left-right
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1 and key < node.right.key:      # right-left
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

Inserting sorted data stays shallow, where a plain BST would become a linked list:

root = None
for key in [1, 2, 3, 4, 5, 6, 7]:
    root = insert(root, key)

print(root.key)      # 4  -> balanced root, not 1
print(root.height)   # 3  -> log2(7) rounded up

Common Mistakes

• Forgetting to update node heights after rotations, which corrupts later balance checks
• Mixing up the four rotation cases (left-left, right-right, left-right, right-left)
• Rebalancing only on insert but not on delete, letting the tree slowly skew
• Assuming any BST is balanced — insertion order alone can produce O(n) height
• Reaching for a hand-rolled tree when a sorted list plus bisect would suffice

See Also

data-structures-trees data-structures-heaps data-structures-tries