Lesson 13: Advanced Trees — AVL, B-Trees, and Segment Trees

Lesson 7 ended with a warning: a plain BST degenerates into a chain on sorted input, and its O(log n) becomes O(n). This lesson presents three professional answers. AVL trees keep a BST balanced by rotating after every insert. B-trees widen the tree — hundreds of keys per node — so databases can keep indexes on disk shallow. Segment trees store aggregates over intervals so range queries and point updates both cost O(log n). Each is traced at the level of individual pointer and array changes.

AVL trees: balance by rotation

For each node define the balance factor: height of left subtree minus height of right. AVL requires it to stay in {-1, 0, 1} for every node, everywhere. Insertions can push a node to +/- 2, and the fix is a rotation: a constant-time rewiring that preserves in-order sequence while shortening the tall side. Trace the simplest case (left-left): insert 30, 20, 10 into an empty tree.

After rotation the tree is 20 with children 10 and 30: height 1 instead of 2, in-order sequence (10, 20, 30) unchanged. There are four cases — left-left, right-right (single rotations) and left-right, right-left (double rotations: rotate the child one way, then the node the other) — but all implement the same idea: demote the unbalanced node, promote its child on the heavy side. With balance enforced after every update, height is guaranteed at most about 1.44 log2(n), so search/insert/delete are O(log n) guaranteed — the property a plain BST could not promise. (Red-black trees, used in Java's TreeMap and C++'s std::map, relax the rule to "roughly balanced" for cheaper inserts; the concept is sibling, not stranger.)

def right_rotate(y):
    x = y.left
    middle = x.right
    x.right = y               # promote x, demote y
    y.left = middle           # x's old right subtree becomes y's left
    return x                  # new subtree root

B-trees: balance for the disk age

Databases store data on disk in pages (say 16 KB) and reading a page costs roughly as much whether it holds 1 key or 500. A B-tree node fills a whole page with hundreds of sorted keys and child pointers, so the tree's fan-out is enormous and its height tiny: with 500-way branching, three levels index 500^3 = 125,000,000 keys, and any lookup costs at most 3-4 page reads. Inserts split full nodes (pushing a median key up), deletes rebalance by borrowing or merging — the invariant is simply "all leaves at the same depth, every node at least half full". This is why Lesson 3's "database index" is a B-tree (technically a B+ tree, keys and records in the leaves, linked left-to-right for range scans): the binary-search idea, re-engineered for a world where the expensive unit is a disk read, not a comparison. In-memory analog: whenever your cost unit is a *batch* (cache lines, network packets), wider nodes win the same way.

Segment trees: aggregates over intervals

A segment tree answers questions like "sum of elements 3..7" with point updates, both in O(log n) — the job arrays do in O(1)/O(n) split across the two operations (Lesson 2's trade, inverted). Store the array's intervals as a binary tree in an array tree of size 4n: node 1 covers [0, n), its children cover the halves, leaves are single elements, and every internal node stores the sum of its segment:

Build one concretely for a = [5, 2, 7, 1, 4] (indices 0..4), splitting each interval at its midpoint, half-open intervals throughout. The root covers [0, 5) and stores 19. Its children split at 2: [0, 2) stores 7 (5 + 2) and [2, 5) stores 12. Continuing down: [0, 2) splits into [0, 1) = 5 and [1, 2) = 2; [2, 5) splits at 3 into [2, 3) = 7 and [3, 5) = 5; and [3, 5) splits into [3, 4) = 1 and [4, 5) = 4. Query — sum of indices 1..3, i.e. the half-open interval [1, 4), which should be 2 + 7 + 1 = 10: the interval decomposes into stored nodes [1, 2) = 2, [2, 3) = 7 and [3, 4) = 1, three nodes summing to 10. Any interval decomposes into at most 2 log2(n) stored nodes — that is the query guarantee. Update sets a leaf and recomputes the O(log n) nodes on its path back to the root.

class SegTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n)

    def _build(self, data, node, lo, hi):       # covers [lo, hi)
        if hi - lo == 1:
            self.tree[node] = data[lo]
            return
        mid = (lo + hi) // 2
        self._build(data, 2 * node, lo, mid)
        self._build(data, 2 * node + 1, mid, hi)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, node, lo, hi, ql, qr):      # sum over [ql, qr)
        if ql <= lo and hi <= qr:
            return self.tree[node]
        mid = (lo + hi) // 2
        total = 0
        if ql < mid:
            total += self.query(2 * node, lo, mid, ql, qr)
        if qr > mid:
            total += self.query(2 * node + 1, mid, hi, ql, qr)
        return total

    def sum(self, l, r):
        return self.query(1, 0, self.n, l, r)

Swap sums for min, max or GCD and the identical skeleton answers range-minimum or range-GCD queries — the aggregate must be *combinable from halves*, which is the only requirement. (A Fenwick/binary-indexed tree does prefix sums with less code and memory; it is the specialist cousin worth knowing by name.)

Choosing among the three

In the real world

PostgreSQL and MySQL indexes are B+ trees. The Linux kernel's virtual memory areas live in a red-black tree (now a maple tree — same balancing family). Segment trees power range analytics in trading systems, booking engines ("how many seats free between dates X and Y"), and image editors computing region statistics. If you use bisect on a Python list with heavy updates, you are simulating a B-tree one element at a time — the libraries sortedcontainers and databases exist to spare you.

Common mistakes

• Rotating without updating heights. AVL correctness lives in the stored height fields; recompute them bottom-up after every rotation.
• Confusing B-tree order with degree. "Order" counts children; the fan-out is what buys the shallow height — always reason in page reads.
• Building segment tree queries with wrong interval conventions. Mixing inclusive [l, r] and half-open [l, r) is the number-one source of off-by-one bugs. Pick half-open everywhere (as above).
• Rebuilding a segment tree per query. Build once O(n); if you rebuild per query you have re-invented the O(n) scan.

Real-World Challenge

Problem: hotel bookings — is any night over capacity? A hotel has C rooms. Booking requests arrive as [check_in, check_out, rooms_wanted) intervals (half-open: the guest leaves on check_out morning). Each request must be accepted only if, on every night of the stay, total booked rooms stay within C. With up to 10^5 requests over a 365-night season, checking every night of every request naively costs 365 x 10^5 operations and gets worse with longer seasons. Make each request O(log n).

Worked solution. Model nights as an array occupancy[0..364], initially zero. A booking is a range add (add rooms_wanted to every night in [in, out)) plus a range maximum query (the busiest night in the interval) to test feasibility. A segment tree storing per-segment maximum, augmented with lazy propagation (a pending "add this to my whole segment" tag pushed down only when visited), performs both in O(log n):

class BookingTree:
    def __init__(self, nights):
        self.n = nights
        self.mx = [0] * (4 * nights)
        self.lazy = [0] * (4 * nights)

    def _push(self, node):
        if self.lazy[node]:
            for child in (2 * node, 2 * node + 1):
                self.mx[child] += self.lazy[node]
                self.lazy[child] += self.lazy[node]
            self.lazy[node] = 0

    def range_add(self, node, lo, hi, ql, qr, delta):
        if ql <= lo and hi <= qr:
            self.mx[node] += delta
            self.lazy[node] += delta
            return
        self._push(node)
        mid = (lo + hi) // 2
        if ql < mid:
            self.range_add(2 * node, lo, mid, ql, qr, delta)
        if qr > mid:
            self.range_add(2 * node + 1, mid, hi, ql, qr, delta)
        self.mx[node] = max(self.mx[2 * node], self.mx[2 * node + 1])

    def range_max(self, node, lo, hi, ql, qr):
        if ql <= lo and hi <= qr:
            return self.mx[node]
        self._push(node)
        mid = (lo + hi) // 2
        best = 0
        if ql < mid:
            best = max(best, self.range_max(2 * node, lo, mid, ql, qr))
        if qr > mid:
            best = max(best, self.range_max(2 * node + 1, mid, hi, ql, qr))
        return best

Booking flow: query range_max over [in, out); if max + rooms_wanted exceeds C, reject; otherwise range_add the rooms and accept. The lazy tag is the key invention: a booking covering a node's *entire* segment updates just that node in O(1) instead of descending to every night, and tags accumulate until a later query needs finer detail. This exact structure (segment tree beats / lazy segment trees) sits inside real reservation, bandwidth-allocation and calendar systems.

Extension. Cancellation must subtract rooms from an interval — confirm the same code handles it with a negative delta, and identify which line makes that safe. Then discuss: why does a plain array with a per-night loop still win when the season is only 30 nights and requests are 100?

The Fenwick tree: segment tree's lean cousin

For the special case of prefix sums with point updates, a Fenwick (binary indexed) tree does the segment tree's job with a smaller constant and a dozen lines. It stores in tree[i] the sum of a range whose length is the lowest set bit of i; a prefix sum is accumulated by repeatedly clearing the lowest set bit, and an update propagates by adding it. For array [5, 2, 7, 1, 4], prefix_sum(3) (first three elements) reads tree[3] (covers just index 3: value 7) then tree[2] (covers indices 1..2: 5 + 2 = 7), totalling 14 — correct, in O(log n) hops over a plain list of n integers:

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)          # 1-indexed internally

    def add(self, i, delta):              # add delta at position i (0-indexed)
        i += 1
        while i <= self.n:
            self.bit[i] += delta
            i += i & -i                   # climb by the lowest set bit

    def prefix_sum(self, i):              # sum of positions 0..i
        i += 1
        total = 0
        while i > 0:
            total += self.bit[i]
            i -= i & -i                   # strip the lowest set bit
        return total

    def range_sum(self, l, r):            # sum over [l, r)
        return self.prefix_sum(r - 1) - (self.prefix_sum(l - 1) if l > 0 else 0)

The bit tricks (i & -i isolates the lowest set bit) are the entire data structure — which is why Fenwick trees are beloved in competitive programming and feared in code reviews. Rule of thumb: range *aggregates beyond sums* (min, max, GCD) or range *updates* need the segment tree; prefix sums with point updates can take the Fenwick and its smaller memory footprint (n entries, versus the segment tree's 4n).