Context
The test kit ships one balanced file, CLUEdata2018_median.csv, in which each subtree's median arrives first. It builds a perfectly balanced tree of 13 levels for the 4,181 locations, but only for the full data. Its prefixes are not balanced in the same sense: the first 250 locations already reach the final 13 levels, where 8 would be the minimum. The benchmark (DR-004) needs a balanced tree for any subset of locations, to compare with shuffled and sorted insertion at sizes from 125 to 4,181.
The file's maker was not recorded, so I first tried to recover the rule it used. The full tree has 1,619 subtrees with an odd number of locations, and every one of them has its exact median at the root. The 514 even-sized subtrees use the lower middle key 253 times and the upper one 261 times. The chosen key is never the one further from the average of the two middle keys: it is strictly nearer in 251 cases (where floating-point rounding separates them) and exactly as near in the other 263. That is consistent with "take the point nearest to the mean of the two middle keys", but nothing I tested (input order, record counts, position in the random file) decides the 263 exact ties.
Decision
Build a balanced tree with a deterministic recursive median, and insert the points in that order through the same KdTree.insert every other tree uses (web/src/lib/balanced.ts):
- sort the subtree's points on its split axis, breaking ties by the other axis and then by input position;
- take the lower median, at index ⌊(m − 1) / 2⌋ of m points;
- if keys equal to it sit before it, move to the first of them, so that every point on the left is strictly smaller, as the insertion rule requires (DR-002);
- insert the medians in pre-order (each subtree's median before its descendants).
Options considered
- Prefixes of the kit's median-first file. Rejected. They are not balanced for any size below 4,181, and the file only covers the full data.
- Replicate the kit's generator exactly. Rejected. Odd-sized subtrees agree, but the even-sized choice is undecided in 263 cases, so any replica would be a guess presented as a recovery.
- Link the nodes directly from sorted arrays, without insert. Rejected. It would be a second code path whose comparison counts would need their own parity checks.
- Lower median, inserted through the ordinary insert. Chosen.
Why
Insertion through the shared code means a balanced tree is searched and counted by exactly the code that the parity tests check against the C program, so any difference in cost comes from the shape alone. The lower median plus the "move to the first equal key" step is the simplest rule that agrees with "equal goes right".
What happened
- On the full data, the build gives 13 levels, mean depth 10.044 and the same number of nodes at every depth as the kit's file. It is not the same tree: 2,382 of the 4,181 locations have the same parent as in the kit's tree. That difference comes from the even-sized subtrees.
- For distinct keys the build always reaches the smallest possible shape (⌊log₂ n⌋ + 1 levels and the mean depth of a complete tree), which the unit tests check for sizes from 1 to 1,000.
- Ties cost something. At n = 2,000, 4 of the 20 seeded subsets came out one level taller than the minimum (12 instead of 11), because moving the median to the first equal key leaves the right side bigger. The mean depth stayed within a thousandth of a level of the minimum.
- The benchmark (DR-004) compares the kit's median-first file, which has the same depth profile as this build, with the other kit orders. It is the cheapest kit order for queries near businesses. For queries spread uniformly over the city it has a heavier tail than the kit's shuffled files, which gives them a lower mean, but over 20 seeded shuffles there is no clear difference. The cost comparison does not run this build itself.
What I'd change
Split ties three ways (less, equal, greater) when building, or allow equal keys on both sides with a search that checks both, so that a balanced build stays minimal with tied keys. I would also record the generator script with any test file I make, so the next person does not have to infer it.