Pebellslearn by building
0%
RoadmapsMatrixCoursesSandboxSign in
Balanced Trees  ›  Capstone Project

Capstone: Quarry's Index Layer

40 minShuffle a batch of ids into insert order, rebalance an AVL on every insert, then run a batch of searches — measured height, rotations, and search cost, not assumed ones
You're building a piece ofQuarry — the index layer
This piece — index_layer_report(): Runs a real insert/query mix and reports the index's height and how many rotations it took to stay that short.
Scenario Quarry's index layer is about to go live. Before it does, the team wants real numbers under a realistic insert/query mix — not the clean ascending order from lesson 1, and not a hand-picked best case.
Your task
Build index_layer_report(n, seed): with rng = random.Random(seed), shuffle list(range(n)) and insert every key into an AVL tree (rebalancing with rotations after every insert, exactly as in lesson 2), counting total rotations. Then shuffle the same n keys again (continuing to draw from the SAME rng) and run a search for each one, counting the total number of node-visits across all searches. Return {"height": ..., "rotations": ..., "queries": n, "total_search_steps": ..., "avg_search_steps": round(total_search_steps / n, 2) if n else 0.0, "balanced_bound": ceil(log2(n+1)) if n else 0}. Example: index_layer_report(8, 42) -> {"height": 4, "rotations": 2, "queries": 8, "total_search_steps": 21, "avg_search_steps": 2.62, "balanced_bound": 4}.
Additional resources
ArticleB-tree↗ArticleISAM↗

Capstone: Quarry's Index Layer

In short: Every lesson in this section answered the same question a different way: what keeps a search tree short? Rotations are the one move that does it (lesson 1). AVL trees apply that move after every insert using a balance factor (lesson 2); B-trees sidestep the question by widening each node so a disk index stays shallow regardless (lesson 3); treaps and skip lists reach for randomness instead of bookkeeping (lesson 4); k-d trees split on alternating coordinates to prune a plane instead of a line (lesson 5). Quarry's index layer puts the AVL machinery to work on something closer to a real workload: ids that arrive in no particular order, and queries that follow.

What you're building

index_layer_report(n, seed) -> {
    "height": h, "rotations": r, "queries": n,
    "total_search_steps": t, "avg_search_steps": a,
    "balanced_bound": b,
}
index_layer_report(8, 42)
# {"height": 4, "rotations": 2, "queries": 8, "total_search_steps": 21,
#  "avg_search_steps": 2.62, "balanced_bound": 4}
  • height, rotations: the AVL tree's final height after inserting a shuffled batch of n ids, and how many rotations that took.
  • total_search_steps, avg_search_steps: run a search for every id, in a second shuffled order, and add up how many nodes each search visited.
  • balanced_bound: ceil(log2(n + 1)), the height a perfectly packed tree of n nodes would have — the number every other field is measured against.

Lesson 1 inserted ids in sorted order on purpose, to show the worst case. Real index layers rarely get keys that considerate. This capstone shuffles the insert order — and the query order — with a seeded random generator, so the numbers are realistic and exactly reproducible.

Build, then measure, don't assume

python

8 shuffled ids build a tree of height 4, exactly the balanced bound — and it only took 2 rotations to get there, versus 8 if the AVL guarantee didn't hold and lesson 1's chain happened instead. At 100 ids, height 8 sits within AVL's own promise of ~1.44 * log2(n), and the average search (5.84 steps) comes in well under the worst case (8) — most keys aren't sitting at the deepest leaf.

step through it
1import random, math
2 
3class Node:
4 def __init__(self, v):
5 self.v = v
6 self.left = self.right = None
7 self.h = 1
8 
9def h(n):
10 return n.h if n else 0
11 
12def update(n):
13 n.h = 1 + max(h(n.left), h(n.right))
14 
15def bf(n):
16 return h(n.left) - h(n.right)
17 
18def rotate_right(y):
19 x = y.left
20 y.left = x.right
21 x.right = y
22 update(y); update(x)
23 return x
24 
25def rotate_left(x):
26 y = x.right
27 x.right = y.left
28 y.left = x
29 update(x); update(y)
30 return y
31 
32def insert(node, v, rotations):
33 if node is None:
34 return Node(v), rotations
35 if v < node.v:
36 node.left, rotations = insert(node.left, v, rotations)
37 else:
38 node.right, rotations = insert(node.right, v, rotations)
39 update(node)
40 balance = bf(node)
41 if balance > 1:
42 if bf(node.left) < 0:
43 node.left = rotate_left(node.left)
44 node = rotate_right(node)
45 rotations += 1
46 elif balance < -1:
47 if bf(node.right) > 0:
48 node.right = rotate_right(node.right)
49 node = rotate_left(node)
50 rotations += 1
51 return node, rotations
52 
53rng = random.Random(42)
54keys = list(range(8))
55rng.shuffle(keys)
56print("insert order:", keys)
57root = None
58total_rotations = 0
59for k in keys:
60 before = h(root)
61 root, total_rotations = insert(root, k, total_rotations)
62 print(f"inserted {k}: height {before} -> {h(root)}, rotations so far {total_rotations}")
63print("final height:", h(root), "total rotations:", total_rotations)

Why a static index couldn't do this

Before B-trees, disk indexes were often built ISAM-style: sort every key once, lay out a static, perfectly balanced index on disk, and leave it alone. Reads were fast — the index never moved. But writes didn't fit: a new key had nowhere balanced to go, so ISAM systems bolted an unsorted "overflow area" onto each page and let it grow, or rebuilt the entire index offline on a schedule.

What does this print?
def isam_overflow_depth(inserts_since_rebuild):
    # ISAM doesn't rebalance; every insert since the last rebuild
    # just appends to an unsorted overflow chain on its page.
    return inserts_since_rebuild

print(isam_overflow_depth(0), isam_overflow_depth(50))

That's the gap this whole section closes. Every structure in lessons 1–5 rebalances in place, during normal operation, with no separate offline step and no degrading overflow chain: B-trees split a full node and push the median up; AVL and red-black trees rotate or recolour; treaps and skip lists use randomness that never needs "freshening." An index layer that rebalances as it goes never needs a maintenance window — which is exactly why ISAM lost to B-trees, and why Quarry's index layer measures itself under real inserts instead of assuming a clean, pre-sorted load.

Quick practice

What does this print?
import math
print(math.ceil(math.log2(1000001)))

🎯 Your turn

Build index_layer_report(n, seed): with rng = random.Random(seed), shuffle list(range(n)) and insert every key into an AVL tree (rebalancing with rotations after every insert), counting total rotations. Then shuffle the SAME keys again on the SAME rng and search for every one, counting one step per node visited. Return {"height": ..., "rotations": ..., "queries": n, "total_search_steps": ..., "avg_search_steps": round(total_search_steps / n, 2) if n else 0.0, "balanced_bound": ceil(log2(n+1)) if n else 0}.

  • index_layer_report(8, 42) → {"height": 4, "rotations": 2, "queries": 8, "total_search_steps": 21, "avg_search_steps": 2.62, "balanced_bound": 4}

Hint: reuse lesson 2's AVL insert/rotation functions unchanged, just threaded with a counter. Build the query order with a second call to rng.shuffle on the same generator — not a new random.Random(seed).

Press ▶ Run, try the Live App chips, then ✓ Check. Green = every piece of Quarry's index layer is built. ✅

Practice — level up

0/5 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upThe arrival order

Write shuffled_order(n, seed): create random.Random(seed), shuffle list(range(n)) with it, and return the first 5 values of the shuffled list (or fewer, if n < 5).

randomised-algorithms
DrillDoes this insert need fixing?

Write would_need_rotation(balance_factor): return True if an AVL node with this balance factor needs a rotation (lesson 2's rule: |bf| > 1).

balanced-trees
BuildJust the final height

Write final_height(n, seed): shuffle list(range(n)) with random.Random(seed) and insert every key into an AVL tree (rebalancing after every insert, as in lesson 2). Return just the tree's final height.

balanced-treesrandomised-algorithms
BossWhat the shuffle actually cost

Write total_rotations(n, seed): same build as final_height, but return the total number of rotations performed across all n inserts instead of the height.

balanced-treesrandomised-algorithms
CapstoneWhat the index actually costs to read

Write avg_search_cost(n, seed): build the AVL index exactly as in the lesson (shuffle insert order with random.Random(seed), insert with rebalancing), then shuffle the SAME n keys again on the same rng and search for each one, counting one step per node visited. Return {"avg_search_steps": round(total / n, 2) if n else 0.0, "balanced_bound": ceil(log2(n+1)) if n else 0}.

balanced-treescomplexity
index_layer_report.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
index_layer_report(n, seed) → dictThe AVL index's final height and rotation count after n shuffled inserts, plus the total and average search cost over n shuffled queries.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.