After giving it a bit of thought, I’ve found a way to simplify the nearest neighbour search (i.e: the closest method) for the KdTree I implemented in my previous post.

The k-d Tree is a useful way to map points in space and make them efficient to query.

I ran into them during my studies in graphics, as they are one of the possible acceleration structures for ray-casting operations.

Reservoir Sampling is an online, probabilistic algorithm to uniformly sample $k$ random elements out of a stream of values.

It’s a particularly elegant and small algorithm, only requiring $\Theta(k)$ amount of space and a single pass through the stream.

My last post about the Treap showed an implementation using tree rotations, as is commonly done with AVL Trees and Red Black Trees.

But the Treap lends itself well to a simple and elegant implementation with no tree rotations. This makes it especially easy to implement the removal of a key, rather than the fiddly process of deletion using tree rotations.

The Treap is a mix between a Binary Search Tree and a Heap.

Like a Binary Search Tree, it keeps an ordered set of keys in the shape of a tree, allowing for binary search traversal.

Like a Heap, it associates each node with a priority, making sure that a parent’s priority is always higher than any of its children.