Little Red Riding Hood & the k-d tree forest
summary
Builds a working k-d tree in C++ and shows which design changes actually matter: starts with pointer-based recursive nodes and a naive O(n^2) pairwise radius check, then implements a radius (range) search with axis check to prune branches, moves from unique_ptr nodes to array-backed storage, and finally uses offsets instead of pointers stored in three vectors (points, left, right) so the structure is cheap to copy, relocatable and serializable. Copies and destruction become far faster (about 10x faster destruction after node consolidation) and queries run logarithmically on balanced data.
AI-written summary · about
chapters (7)
- 0:00Start
- 2:40Disclaimers
- 10:46Inventing the Kd Tree
- 21:55Effective Abstractions
- 32:46Rule of Three
- 38:31The Essential Properties of a Pointers
- 48:27Implicit Edge Representation
related talks
01h 04mBetter Code: Data Structures
40mImmutable Data Structures in C++
01h 39m“Leak-Freedom in C++... By Default.”
13mMissing Optimizations on Node-based Containers
01h 01mRecipes for Reducing Allocations by C++ Containers
01h 20mBetter Code: Relationships
30m“Esoteric Data Structures and Where to Find Them”
01h 12mConcept Maps using C++23 Library Tech - Indirection to APIs for a Concept