Will Stephen ← All projects Software engineer in London.
Final year CS at UCL, Intelligent Systems.

Self-balancing search trees

Year
2025

Role
Group coursework, team of three

Built with
Python, Jupyter, Matplotlib

Team
Group of three, UCL COMP0005 Algorithms

Links
Repository

An illustration: a red-black tree, a B-tree and a scapegoat tree drawn as one botanical tree. Three strands twist into a single trunk and fork into branches, with dark and red-ringed nodes, multi-key boxes and outlined nodes as the fruit, and red links as red twigs.
An illustration Three self-balancing trees grown from the same keys: a red-black tree (dark nodes, red links), a B-tree (multi-key boxes) and a scapegoat tree (outlined nodes). The exact trees our code builds are drawn further down. Read the notebook

A red-black tree, a B-tree and a scapegoat tree all promise the same thing: finding or adding a key takes O(log n) time for n keys. On paper they are equivalent. That doesn’t help much if you have to choose one, so for an Algorithms group coursework at UCL we wrote implementations of all three in Python and benchmarked them, to understand the different advantages each one offers.

Left-leaning red-black tree

Height 4, root 09, with 1, 2, 4, 4 nodes on successive levels. 3 red nodes (03, 23, 28), drawn with a red ring and a thick red link to its parent; every other node black. 2 left rotations, 3 right rotations and 5 colour flips kept it balanced. 03 05 06 07 09 12 23 26 27 28 30

B-tree

Branching factor 3, height 2: a root holding 07 and 26 above 3 nodes holding 03 05 06; 09 12 23; 27 28 30. 2 node splits. 0726 030506 091223 272830

Scapegoat tree

Alpha 0.7, height 6, root 30, with 1, 1, 2, 2, 2, 3 nodes on successive levels. 0 partial rebuilds. 03 05 06 07 09 12 23 26 27 28 30
The same 11 keys inserted into each tree in a random order: 30, 27, 09, 03, 26, 06, 07, 28, 23, 12, 05. Read the notebook

What we built

The notebook holds a left-leaning red-black tree, a B-tree and a scapegoat tree behind one shared interface, a generator for test data, and a framework that times every insert and every search. The B-tree takes a branching factor and the scapegoat tree takes an alpha, so we could sweep both. We used four kinds of input, each 10,000 five-character strings: random, sorted, “balanced” (median first) and “unbalanced”. Every run was repeated 1,000 times and averaged position by position, with outliers filtered out and a moving average drawn in Matplotlib.

What our results showed

On random strings the B-tree was the quickest to insert into and the slowest to search. The red-black tree was the reverse, and the scapegoat tree sat in the middle both times. Every time on these charts is a few microseconds, so the gaps are small.

Time to insert one random string into each tree as it grows to 10,000 keys. 151-point moving average.
Line chart of insert time against tree size up to 10,000 for three trees on random strings. The B-tree is lowest, the scapegoat tree in the middle and the red-black tree highest, all between about 1 and 4 microseconds.

In memory, smaller branching factors were faster to search: 35 and 50 were clearly slower than 5 and 20.

Time to search a B-tree of up to 10,000 random strings at four branching factors. 151-point moving average.
Line chart of search time against tree size for B-trees with branching factors 5, 20, 35 and 50. Factors 5 and 20 sit near 2 microseconds; 35 and 50 sit higher, near 3 and 3.7.

For the scapegoat tree, alphas of 0.5 and 0.6 were the slowest to insert with, and 0.7 to 0.9 ran close together. A higher alpha tolerates a deeper tree, so it rebuilds less often.

Time to insert into a scapegoat tree at five alpha values. 151-point moving average.
Line chart of insert time against tree size for scapegoat trees with alpha from 0.5 to 0.9. Alpha 0.5 is highest, 0.6 next, and 0.7, 0.8 and 0.9 lie close together below.

On the red-black tree, the four kinds of input gave almost the same insert times.

Red-black insert time on the four kinds of input: the lines overlap. 151-point moving average.
Line chart of red-black tree insert time against tree size for four kinds of input. The four lines lie almost on top of each other.

Each chart’s footnote says the moving average is plus or minus 200. The code smooths over 151 points, 75 either side, so read them that way.

What we concluded

On paper the three trees are equivalent. In our Python versions they weren’t, and no tree won outright. On random strings the B-tree suited insert-heavy work and the red-black tree suited lookups, with the scapegoat tree in between and an alpha to tune. Every operation took a few microseconds at 10,000 keys, so it was the constant factors, how much work each insert or search does, that decided the order, not the O(log n) they all share.

My takeaway

The theory behind an algorithm and its implementation often isn’t reflected in reality, because it can’t account for the deep complexity of a modern computer: scheduling, the memory hierarchy and how memory is managed. So it’s important to test several options on your real use case and make algorithm decisions empirically.