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.

# Tag: Python

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.