05 - Binary Trees, BST, and AVL Trees

You have a set of keys that changes over time, and you need three things at once: to know whether a key is present, to insert a new one, and to read everything back in order. A sorted list gives you fast search but forces you to shift half the elements on every insertion; a hash table inserts and searches quickly but knows nothing about order. The binary search tree (BST) holds the three operations together, on one condition that the code never writes down anywhere: the tree must stay short. This article builds a BST, breaks it with an unlucky insertion order, and repairs it with the AVL tree, each time measuring how many nodes are examined. You need the O notation from Big-O and complexity and the idea of search from linear, binary and hash search; for the level-by-level queue, the deque from the previous article is enough.

What a binary search tree promises

A binary tree is a structure in which every node has a key and at most two children, one on the left and one on the right. It becomes a search tree when a single rule holds, the invariant: for every node, all the keys in the left subtree are smaller than its own, and all those in the right subtree are greater. Think of a phone book that tells you on every page "before this surname go left, after it go right": at each step you discard a whole branch without looking at it.

It follows that searching, inserting and deleting cost a number of steps proportional to the height h of the tree, that is O(h). If the tree is well filled, h grows like the logarithm of the number of keys n, and the discard at each step halves the work; if the tree is a chain, h equals n and you have rebuilt a list with extra pointers. The rest of the article revolves around this distinction, and we measure it by counting the nodes examined, not seconds, because the count does not change from one machine to another.

The BST in Python, without recursion where possible

The listing below is the structure used by every later experiment; save it as bst.py. insert and search are iterative: they descend with a loop and increment self.compares at every node examined, so they work even on a tree thousands of levels deep. If you made them recursive, a degenerate tree of 4,000 keys would exceed Python's recursion limit (1,000 by default, documented in sys.setrecursionlimit) and would fail with an error, not with a slow answer. delete is recursive because it has to rewrite the links from the bottom up, and it can afford that as long as the tree is short.

class Node:
    __slots__ = ("key", "left", "right")

    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root = None
        self.size = 0
        self.compares = 0  # nodes examined: the measure used in the article

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
            self.size = 1
            return True
        node = self.root
        while True:
            self.compares += 1
            if key == node.key:
                return False  # key already present: the set does not change
            side = "left" if key < node.key else "right"
            child = getattr(node, side)
            if child is None:
                setattr(node, side, Node(key))
                self.size += 1
                return True
            node = child

    def search(self, key):
        node = self.root
        while node is not None:
            self.compares += 1
            if key == node.key:
                return True
            node = node.left if key < node.key else node.right
        return False

    def delete(self, key):
        before = self.size
        self.root = self._delete(self.root, key)
        return self.size < before

    def _delete(self, node, key):  # recursive: depth = height
        if node is None:
            return None
        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            self.size -= 1
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            succ = node.right  # two children: the successor is the minimum on the right
            while succ.left is not None:
                succ = succ.left
            node.key = succ.key
            self.size += 1  # compensates for the decrement the call below would make
            node.right = self._delete(node.right, succ.key)
        return node

    def height(self):  # number of nodes on the longest path, iterative
        best, stack = 0, [(self.root, 1)] if self.root else []
        while stack:
            node, depth = stack.pop()
            best = max(best, depth)
            for child in (node.left, node.right):
                if child is not None:
                    stack.append((child, depth + 1))
        return best

    def in_order(self):
        out, stack, node = [], [], self.root
        while stack or node is not None:
            while node is not None:
                stack.append(node)
                node = node.left
            node = stack.pop()
            out.append(node.key)
            node = node.right
        return out

Deletion has three cases. A node with no children simply disappears; a node with one child is replaced by that child; a node with two children takes the key of its successor, the minimum of the right subtree, and then that successor (which has at most one child) is deleted in turn. The successor is the right choice because it is the immediately next larger key: put in place of the deleted one, it leaves the invariant intact. The line self.size += 1 compensates for a double count: the node is counted as deleted on the first call and again when the successor is removed. Take it out and size is wrong, but the tree stays correct: this is the kind of error that only a test against an independent reference finds.

First test: is it correct?

Before measuring speed you need to know that the tree does what it promises. I compare it with Python's set type, which is an independent reference: 3,000 random sequences of insertions, deletions and searches on keys between 0 and 40 (a narrow range, so keys repeat and are really deleted), with a fixed-seed generator. At the end of each sequence the in-order traversal must match sorted(ref) and the size must match len(ref).

import random
from bst import BST

rng = random.Random(7)
casi = 0
for prova in range(3000):
    t, ref = BST(), set()
    for _ in range(rng.randint(1, 60)):
        k = rng.randint(0, 40)
        op = rng.choice(("ins", "ins", "del", "src"))
        if op == "ins":
            assert t.insert(k) == (k not in ref)
            ref.add(k)
        elif op == "del":
            assert t.delete(k) == (k in ref)
            ref.discard(k)
        else:
            assert t.search(k) == (k in ref)
        casi += 1
    assert t.in_order() == sorted(ref) and t.size == len(ref)
print("trials:", 3000, "operations compared with set():", casi)

# Output:
# trials: 3000 operations compared with set(): 92095

The 92,095 operations agree with set down to the last one. This is not a proof, it is a fine-meshed net: the typical bugs (the wrong successor, a child lost in the one-child case) get many chances to show up on keys that repeat, whereas a test with a single hand-written tree would see few of them.

The worst case: keys in order

The decisive experiment inserts the same n keys in two orders, random and ascending, and then searches for each one once, counting the nodes examined. Ascending order is the worst case, and it is not exotic: sequential identifiers, the dates in a register and timestamps arrive exactly like that.

import math
import random
from bst import BST

rng = random.Random(2026)
print("n      order      height   compares/search    ratio to lg n")
for n in (1000, 4000, 16000):
    for ordine in ("random", "ascending"):
        keys = list(range(n))
        if ordine == "random":
            rng.shuffle(keys)
        t = BST()
        for k in keys:
            t.insert(k)
        t.compares = 0
        for k in range(n):  # search each present key once
            t.search(k)
        media = t.compares / n
        print(f"{n:<6} {ordine:<10} {t.height():<8} {media:<18.2f} {media / math.log2(n):.2f}")

# Output:
# n      order      height   compares/search    ratio to lg n
# 1000   random     22       11.76              1.18
# 1000   ascending  1000     500.50             50.22
# 4000   random     25       13.99              1.17
# 4000   ascending  4000     2000.50            167.19
# 16000  random     34       17.72              1.27
# 16000  ascending  16000    8000.50            572.86

With random order the height stays small (22, 25 and 34 levels for 1,000, 4,000 and 16,000 keys) and the search examines on average 11.76, 13.99 and 17.72 nodes. For a BST built from random keys, the page on BSTs in Algorithms, 4th edition gives as the dominant term about 2 ln n comparisons per search, that is about 1.39 lg n; my values lie below 2 ln n (13.82, 16.59 and 19.36 for these n), as you would expect when the lower-order terms of the formula are negative. One sequence for each n: the comparison is indicative, not a test of the formula. With ascending order the height is n and the search examines on average (n+1)/2 nodes: 500.5 out of 1,000, 8,000.5 out of 16,000. The ratio to lg n goes from 50 to 573, and keeps rising: it is not a constant factor, it is a different complexity class.

The number that matters to a designer is the ratio between the two cases: at 16,000 keys the same structure costs 17.7 or 8,000 nodes per search, over 450 times more, just because of the order in which the data arrived. A plain BST gives you no guarantee: it gives you a hope about the distribution of the inputs, and in real applications the hope breaks now and then.

The four traversals

Traversing a tree means listing all the keys by a fixed rule. The three depth-first traversals differ in the moment at which the root is read: before the children (pre-order), in the middle (in-order), after them (post-order). The fourth, level-order, uses a queue and reads the whole row at depth 0, then the one at depth 1, and so on. The listing applies them to a tree of seven keys, and then checks a useful property: the pre-order list, reinserted in that order, rebuilds exactly the same tree. It depends on the fact that in pre-order every root comes before all its descendants, so every node is reinserted under the same parent.

import random
from collections import deque
from bst import BST, Node

def pre_order(n):
    return [] if n is None else [n.key] + pre_order(n.left) + pre_order(n.right)

def post_order(n):
    return [] if n is None else post_order(n.left) + post_order(n.right) + [n.key]

def level_order(root):
    out, coda = [], deque([root] if root else [])
    while coda:
        n = coda.popleft()
        out.append(n.key)
        coda.extend(c for c in (n.left, n.right) if c is not None)
    return out

def forma(n):  # nested structure: two trees are equal if their shapes are
    return None if n is None else (n.key, forma(n.left), forma(n.right))

t = BST()
for k in (50, 30, 70, 20, 40, 60, 80):
    t.insert(k)
print("pre  ", pre_order(t.root))
print("in   ", t.in_order())
print("post ", post_order(t.root))
print("level", level_order(t.root))

rng = random.Random(11)
for prova in range(2000):
    keys = rng.sample(range(500), rng.randint(1, 40))
    a = BST()
    for k in keys:
        a.insert(k)
    b = BST()
    for k in pre_order(a.root):  # the pre-order alone rebuilds the same tree
        b.insert(k)
    assert forma(a.root) == forma(b.root)
print("rebuilt from the pre-order alone: 2000 identical trees")

# Output:
# pre   [50, 30, 20, 40, 70, 60, 80]
# in    [20, 30, 40, 50, 60, 70, 80]
# post  [20, 40, 30, 60, 80, 70, 50]
# level [50, 30, 70, 20, 40, 60, 80]
# rebuilt from the pre-order alone: 2000 identical trees

The in-order traversal of a BST gives the keys sorted, and that is why a BST sorts "for free" while it fills up. The pre-order is a compact serialization: 2,000 random trees were rebuilt identical from the list alone, without needing the in-order traversal that is required instead for trees without the invariant. The post-order is the traversal of whoever frees memory or computes a value from the children up to the parent, and the level-order traversal is the breadth-first search taken up again in the article on graphs.

AVL: keeping the height under control

The AVL tree (from the initials of Adelson-Velsky and Landis) adds one rule to the ordering invariant: at every node the heights of the two subtrees differ by at most 1. The signed difference is called the balance factor and must be -1, 0 or 1. When an insertion or deletion breaks the rule (the factor becomes 2 or -2), it is repaired with a rotation: a local rearrangement of three nodes that changes the shape but preserves the in-order sequence. There are four cases: left-left and right-right are solved with one rotation, left-right and right-left with two, because the child has to be straightened first.

The listing, to be saved as avl.py, implements it. _rebalance recomputes the height, reads the factor and chooses the case: in the b > 1 branch the check balance(n.left) < 0 tells left-right apart from left-left. _rot_right and _rot_left are the single rotations, and each updates the height of the node that went down before that of the node that went up, because the height of the node that went up depends on the other. The check method verifies the three properties independently: order, stored heights equal to the recomputed ones, factor within range.

class Node:
    __slots__ = ("key", "left", "right", "h")

    def __init__(self, key):
        self.key, self.left, self.right, self.h = key, None, None, 1


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

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

def balance(n):
    return h(n.left) - h(n.right)


class AVL:
    def __init__(self):
        self.root, self.size = None, 0
        self.compares = 0   # nodes examined
        self.rotations = 0  # single rotations performed (a double one counts as two)

    def _rot_right(self, y):
        x = y.left
        y.left, x.right = x.right, y
        update(y)
        update(x)
        self.rotations += 1
        return x

    def _rot_left(self, x):
        y = x.right
        x.right, y.left = y.left, x
        update(x)
        update(y)
        self.rotations += 1
        return y

    def _rebalance(self, n):
        update(n)
        b = balance(n)
        if b > 1:  # leans left
            if balance(n.left) < 0:  # left-right case: rotate the child first
                n.left = self._rot_left(n.left)
            return self._rot_right(n)
        if b < -1:  # leans right
            if balance(n.right) > 0:  # right-left case
                n.right = self._rot_right(n.right)
            return self._rot_left(n)
        return n

    def insert(self, key):
        before = self.size
        self.root = self._insert(self.root, key)
        return self.size > before

    def _insert(self, n, key):
        if n is None:
            self.size += 1
            return Node(key)
        self.compares += 1
        if key < n.key:
            n.left = self._insert(n.left, key)
        elif key > n.key:
            n.right = self._insert(n.right, key)
        else:
            return n
        return self._rebalance(n)

    def delete(self, key):
        before = self.size
        self.root = self._delete(self.root, key)
        return self.size < before

    def _delete(self, n, key):
        if n is None:
            return None
        if key < n.key:
            n.left = self._delete(n.left, key)
        elif key > n.key:
            n.right = self._delete(n.right, key)
        else:
            if n.left is None or n.right is None:
                self.size -= 1
                return n.left or n.right
            succ = n.right
            while succ.left:
                succ = succ.left
            n.key = succ.key
            n.right = self._delete(n.right, succ.key)
        return self._rebalance(n)

    def search(self, key):
        n = self.root
        while n:
            self.compares += 1
            if key == n.key:
                return True
            n = n.left if key < n.key else n.right
        return False

    def in_order(self):
        out, stack, n = [], [], self.root
        while stack or n:
            while n:
                stack.append(n)
                n = n.left
            n = stack.pop()
            out.append(n.key)
            n = n.right
        return out

    def check(self):
        """Checks the three properties: order, stored heights, |balance factor| <= 1."""
        def rec(n, lo, hi):
            if n is None:
                return 0
            assert (lo is None or n.key > lo) and (hi is None or n.key < hi)
            hl, hr = rec(n.left, lo, n.key), rec(n.right, n.key, hi)
            assert abs(hl - hr) <= 1 and n.h == 1 + max(hl, hr)
            return 1 + max(hl, hr)
        return rec(self.root, None, None)

If you swapped the order of the two update calls in a rotation, the tree would stay ordered and all searches would keep working, but the stored heights would be wrong: the defect would show up later, as another wrong rotation. That is why check recomputes everything from scratch instead of trusting the fields. Deletion has the same structure as in the BST and, unlike insertion, rebalances on the way up even beyond the first repaired node: a rotation can shorten a subtree and break the balance further up.

Second test: the invariant holds after every operation

The test for the AVL tree is stricter: it checks not only at the end, but after each operation. In 4,000 random sequences, with 60% insertions and 40% deletions on keys from 0 to 50, check() verifies order, heights and factor, and the final result is compared with set. Note the difference from the BST: in the AVL tree the deletion of a node with two children does not need the size compensation line, because the node is counted only once, when the successor is removed; with that line copied from the BST the tree would stay valid but size would be wrong, and it is the assertion on len(ref) that would reveal it.

import random
from avl import AVL

rng = random.Random(99)
op_totali = 0
for prova in range(4000):
    t, ref = AVL(), set()
    for _ in range(rng.randint(1, 80)):
        k = rng.randint(0, 50)
        if rng.random() < 0.6:
            assert t.insert(k) == (k not in ref)
            ref.add(k)
        else:
            assert t.delete(k) == (k in ref)
            ref.discard(k)
        t.check()  # the three properties hold after EVERY operation
        op_totali += 1
    assert t.in_order() == sorted(ref) and t.size == len(ref)
print("trials: 4000, operations with the invariant checked:", op_totali)

# Output:
# trials: 4000, operations with the invariant checked: 161499

The 161,499 operations always leave a valid tree. The comparison with set proves that no key is lost in the rotations, the check after every step proves that no intermediate step leaves the range, and the choice of many repeated keys in a small range guarantees that deletions and double rotations really happen.

Ascending order on the AVL tree and its worst case

Let us repeat the experiment that broke the BST: keys in ascending order. If the AVL tree works, the height must stay close to lg n and the search cost must collapse. The listing also measures the number of rotations and then builds the worst possible AVL tree, the one with the minimum number of nodes for a given height. A tree of height h with the minimum number of nodes has one subtree of height h-1 and one of height h-2, so the minimum N(h) satisfies N(h) = N(h-1) + N(h-2) + 1, a Fibonacci-type recurrence: the function min_nodi computes it and albero_fibonacci actually builds the tree, which is then verified by check.

import math
from avl import AVL, Node, update

def min_nodi(altezza):  # fewest possible nodes for an AVL tree of that height
    a, b = 0, 1
    for _ in range(altezza - 1):
        a, b = b, a + b + 1
    return b if altezza else 0

def albero_fibonacci(altezza, prossima):
    """Builds the most unbalanced AVL tree allowed: left subtree taller by 1."""
    if altezza == 0:
        return None
    n = Node(None)
    n.left = albero_fibonacci(altezza - 1, prossima)
    n.key = next(prossima)
    n.right = albero_fibonacci(altezza - 2, prossima) if altezza > 1 else None
    update(n)
    return n

print("ascending sequence 1..n inserted into the AVL tree")
print("n        height   minimum  rotations  compares/search")
for n in (1000, 10000, 100000):
    t = AVL()
    for k in range(n):
        t.insert(k)
    rot, t.compares = t.rotations, 0
    for k in range(n):
        t.search(k)
    print(f"{n:<8} {t.check():<8} {math.ceil(math.log2(n + 1)):<8} {rot:<10} {t.compares / n:.2f}")

print()
print("AVL tree of height h with the minimum number of nodes (Fibonacci trees)")
print("h   nodes   height/lg(nodes)")
for hh in (5, 10, 15, 20, 25):
    it = iter(range(10**7))
    t = AVL()
    t.root = albero_fibonacci(hh, it)
    n = min_nodi(hh)
    t.size = n
    assert t.check() == hh and len(t.in_order()) == n
    print(f"{hh:<3} {n:<7} {hh / math.log2(n):.3f}")
print("theoretical limit 1/lg(phi) =", round(1 / math.log2((1 + 5 ** 0.5) / 2), 4))

# Output:
# ascending sequence 1..n inserted into the AVL tree
# n        height   minimum  rotations  compares/search
# 1000     10       10       990        8.99
# 10000    14       14       9986       12.36
# 100000   17       17       99983      15.69
#
# AVL tree of height h with the minimum number of nodes (Fibonacci trees)
# h   nodes   height/lg(nodes)
# 5   12      1.395
# 10  143     1.397
# 15  1596    1.410
# 20  17710   1.417
# 25  196417  1.422
# theoretical limit 1/lg(phi) = 1.4404

Inserted in ascending order, 1,000, 10,000 and 100,000 nodes produce trees 10, 14 and 17 levels high: exactly the minimum possible, ceil(lg(n+1)), because ordered insertion fills the tree level by level. The search examines on average 8.99, 12.36 and 15.69 nodes, against the 500.5 of the BST already at 1,000 keys. The price is the rotations: 990, 9,986 and 99,983, almost one per insertion. It is the work the AVL tree does to keep the height at the minimum: on this input it is what buys the guarantee.

In the second table the Fibonacci tree is the tallest AVL tree for its number of nodes: 12 nodes for height 5, 17,710 for height 20. The height/lg(n) ratio rises with h (1.395, 1.397, 1.410, 1.417, 1.422) towards the limit 1/lg(φ) = 1.4404, which the script computes from the golden ratio. It means that in the worst case an AVL tree is at most about 1.44 times as tall as the logarithmic minimum: the guarantee is O(log n), with a known and small constant. This is not a result I took from a source: it follows from the recurrence above, and the tree that was built respects it.

When it is not enough, and when it is not needed

The AVL tree is not the only road: the red-black tree relaxes the balance in exchange for fewer rotations on writes, and the page on balanced search trees in Algorithms, 4th edition gives for its red-black trees a guaranteed height of no more than 2 lg n; the B-tree keeps many keys per node to reduce disk accesses. I did not implement them here, so I offer no measurements on them. To decide among the options it helps to ask three questions, which the following list puts in order of the cost of a wrong answer.

• Do you need the keys in order, a range, or the successor of a key? If not, a hash table is enough and a tree is excessive.
• Do the keys arrive in an order you do not control? If so, a BST without balancing is a risk, and a structure with a guaranteed height is preferable.
• Does the data fit in memory? If it lives on disk, the height counts in accesses and the B-tree beats the binary one.

The questions are ordered by how much a mistake costs: the first avoids building the wrong structure, the second avoids a degradation that only shows up with certain data in production, the third moves the choice to another family of trees. In Python, for small cases, a sorted list with the bisect module is often still the simplest answer; the tree comes in when insertions are many and frequent, and the order is needed.

What you can do now

You can write a BST with insertion, search and deletion, and you can demonstrate with a measurement (nodes examined, not seconds) that ascending order turns it into a list. You can write an AVL tree with the four rotations, verify its invariant after every operation against an independent reference, and compute its worst case with the Fibonacci recurrence. In the next article the structure stops being a tree: nodes can have cycles, and the work changes.

The same series also includes sorting algorithms and the closing article on dynamic programming.