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).

The Gap Buffer is a popular data structure for text editors to represent files and editable buffers. The most famous of them probably being GNU Emacs.

This time, let’s talk about the Trie, which is a tree-based mapping structure most often used for string keys.

To kickoff the series of posts about algorithms and data structures I find interesting, I will be talking about my favorite one: the Disjoint Set. Also known as the Union-Find data structure, so named because of its two main operations: ds.union(lhs, rhs) and ds.find(elem).