Balanced Trees (Intro)

Prev Next

The Binary Search Tree lesson showed that O(log n) search, insert, and delete are only true if the tree stays roughly balanced — height close to log₂(n). Feed a plain BST already-sorted data and there's no balancing at all: you get a skewed tree that behaves exactly like a linked list. This lesson explains why that happens, the general idea behind self-balancing trees, and — importantly for Python — what the standard library does and doesn't give you here.

The Skewed-Tree Problem

Insert 10, 20, 30, 40, 50 — already sorted — into a plain BST. Every new value is bigger than everything already there, so each node only ever grows a right child:

This is still technically a valid BST, but its height is n, not log n. Searching for 50 means walking every single node — the exact O(n) behavior a BST exists to avoid.

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Inserting 10, 20, 30, 40, 50 in order into a plain BST
# produces a right-skewed chain -- height n, not log n.
def contains(root, target):
    curr = root
    while curr:
        if curr.val == target:
            return True
        curr = curr.left if target < curr.val else curr.right
    return False

Time complexity: O(h) where h is the tree's height — this becomes O(n) on the skewed tree above, but O(log n) on a balanced one. Space complexity: O(1) for this iterative search, since no extra structure grows with the input.

The core issue: a plain BST only ends up balanced by accident of insertion order. A self-balancing tree actively restructures itself after every insert/delete so its height stays close to log n regardless of the order data arrives in.

The Balance Concept

"Balanced" doesn't mean perfectly symmetric — it means the height difference between a node's left and right subtrees is bounded by a small constant, so the tree's overall height stays proportional to log n. Different self-balancing trees enforce this rule differently:

Structure	How it stays balanced
AVL Tree	Tracks a balance factor per node; rebalances with rotations the instant it's violated
Red-Black Tree	Colors nodes red/black and enforces coloring rules that bound height to roughly 2·log n

AVL Trees: Balance Factor

An AVL tree defines the balance factor of a node as:

balance_factor(node) = height(node.left) - height(node.right)

A node is balanced if its balance factor is -1, 0, or 1. The moment an insert or delete pushes any node's balance factor outside that range, the tree performs a rotation to restore it — before the imbalance can compound further up the tree.

Rotation, Worked on 3 Nodes

The simplest case: insert 10, then 20, then 30 into an empty AVL tree. After inserting 30 the tree is right-skewed, and the root's balance factor is -2:

Before rotation (unbalanced):

  10
   \
    20
     \
      30

Root (10): balance factor = 0 - 2 = -2   <- violation (right-heavy)

This is a "right-right" case, fixed with a single left rotation around the root. The middle node (20) becomes the new root, the old root (10) becomes its left child, and 30 stays the right child:

After a left rotation around 10:

      20
     /  \
    10   30

Balance factor of 20: 1 - 1 = 0   <- balanced

The mirror image — inserting 30, then 20, then 10 (left-left case) — is fixed with a single right rotation instead, and again the middle value (20) ends up as the new root. When the imbalance zig-zags (left-right or right-left), AVL trees perform two rotations back to back to straighten it out. The mechanics differ slightly, but the goal never changes: pull the middle value up to become the new subtree root so both sides come out roughly equal in height.

Practical takeaway: you will almost never be asked to implement AVL insert/delete with rotations from scratch in an interview — the bookkeeping is fiddly and easy to get subtly wrong under pressure. What matters is understanding why rotations exist (to stop a skewed tree from decaying to O(n)) and being able to reason about balance factors if asked conceptually.

Python-Specific Note: No Built-In Balanced BST

Here's a genuine difference from Java worth calling out explicitly: Java's TreeMap and TreeSet are backed by a Red-Black tree right in the standard library, so you get sorted-order key iteration and O(log n) guarantees for free. Python's standard library has no built-in balanced BST at all. A plain dict keeps insertion order (not sorted order), and there's no TreeMap equivalent in collections.

When real Python code needs sorted-order storage with fast insert/search — the same role Java's TreeMap/TreeSet play — the common third-party choice is the sortedcontainers package, which implements SortedList and SortedDict using a balanced internal structure (a list of sorted sublists, tuned to be fast in practice, not a classic AVL/Red-Black implementation, but the same practical guarantee: sorted order maintained automatically with good-enough complexity for insert/search/delete).

# pip install sortedcontainers
from sortedcontainers import SortedList, SortedDict

scores = SortedList()
scores.add(50)
scores.add(20)
scores.add(70)
scores.add(10)

print(scores)          # SortedList([10, 20, 50, 70]) -- always kept in order
print(scores[0])       # 10 -- smallest, O(log n) to find

ages = SortedDict()
ages["bob"] = 30
ages["amy"] = 25
print(list(ages.items()))  # [('amy', 25), ('bob', 30)] -- keys iterate in sorted order

Time complexity: O(log n) for add/contains/discard on a SortedList, and O(log n) for get/set on a SortedDict — comparable to a balanced BST's guarantees, though implemented differently under the hood. Space complexity: O(n) to hold n elements.

Also note: since Python 3.7, a plain dict preserves insertion order, which people sometimes confuse with sorted order — they are not the same thing. If you need keys in sorted order, you need SortedDict (or sorting explicitly), not a plain dict.

Next up: we leave trees behind for a while and cover Dict & Set — the O(1)-average structures you'll reach for constantly in Python, and exactly why they're faster than a balanced tree for lookups that don't need ordering.

Prev Next