The experiment · Stage 1 cost
Same businesses, different order, very different tree.
A 2-d tree has no rebalancing: its shape is decided by the order the points arrive in. The 2020 test kit shipped the same 19,117 records in five orders, and the assignment asked what that does to the number of key comparisons per query. Here is the answer, recomputed live from the same files.
The five files
- Original
CLUEdata2018_
original.csv As published by the City of Melbourne: grouped by small area, then by block.
- Random
CLUEdata2018_
random.csv Records shuffled, so locations arrive in random order.
- Random, sorted
CLUEdata2018_
random_ sorted.csv A second shuffle from the test kit; how it was made was not recorded.
- Sorted by x
CLUEdata2018_
sortx.csv West to east. Every x-split sends later points right, so the tree grows tall.
- Median first
CLUEdata2018_
median.csv Each subtree's median arrives first, giving a perfectly balanced tree.
Every count below uses the rebuild's rule (one comparison per node whose key is compared with the query) and is computed by the TypeScript port, which reproduces the C program in coursework/rebuild-2026 exactly on the whole test kit. Want to watch a single search instead? Open the explorer. For the same comparison with intervals, paired tests and ten query sets, see the benchmark.
Building 36 trees and running 85,625 searches…