A Software Engineering Space

Bloom Filters: A probabilistic data structure for testing set membership

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 […]

Hash Tables part 2: Separate Chaining.

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 […]

Iterative Red Black Trees

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. […]

Pretty(er) Tree Printing with Breadth First Traversal

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 […]