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: Data Structures

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.

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.

The *Bloom Filter* is a probabilistic data structure for set membership.

The filter can be used as an inexpensive first step when querying the actual data is quite costly (e.g: as a first check for expensive cache lookups or large data seeks).