Bloom Filters Bloom filters have been around for a while, 1970 to be exact. They’re not exactly the star of any university data structures class. There are much “sexier” (yeah, i know.) data structures like self balancing search trees, hash tables, and graphs. But hidden away in the depths of Algorithms and Data Structures books […]
Part 2: expanding the collision resolution repertoire Welcome back for part two of my articles on hash tables. In my previous article i covered the basics of linear probing. In this article i will discuss another popular collision resolution technique: separate chaining. While open address tables contain just one item per bucket, choosing instead a […]
In part one of my article on open address hash tables i discuss hash functions, initializing the table and buckets, as well as insertion and searching via linear probing.
Red Black Trees Balanced binary search trees are pervasive in modern software. Providing worst case performance of O(logN) red black trees are by far the most pervasive choice when it comes to their implementation. They are famously complicated to implement, and a quick look in Cormen et. al. “Introduction to Algorithms” will back this up. […]
Exploring binary heaps for efficiently implementing the Priority Queue ADT.
Displaying Binary Search Trees Despite the various methods for traversing a tree, displaying the actual structure visually is a more difficult task than one would think. We know that a pre-order traversal gives us some idea of the structure, and Breadth First Traversal gives another view into how the tree is organized. But converting a list of […]