A Software Engineering Space

Bottom-up 2-3 Red/Black Trees: Let your red nodes lean how they want

Well, It appears January is the month of the Red/Black tree, because here I am with yet more Red/Black tree content! Since their introduction in 1978[1] the study of red/black trees generally focused on their isomorphism with 2-3-4 trees. And, while it was recognized that 2-3 tree’s could be made to fit the red/black framework […]

Roll your own String type

Anyone who has ever had the pleasure of working with ‘C style’ strings aka NULL terminated character arrays. Has at some point stopped and remarked about the terrible choice of implementation when it came to representing strings in C. Indeed, almost every serious security vulnerability for a long time could be traced back to a […]

The Heapsort algorithm

Ahh, Heaps.  Heaps are one of those data structures that turn up everywhere. They serve a humble purpose: find the maximum value (depending on if you’re using min or max ordering) of a set efficiently. It is this very purpose that imbues them with the ability to implement a very simple, efficient sorting algorithm. To […]

Randomized Meldable Heaps: An alternative tree structure for the implementation of priority queue

Randomized Meldable Heaps When it comes to priority queues, the binary heap is the go-to data structure when it comes to implementation, and with good reason. Binary heaps offer worst-case logarithmic complexity for all operations that it supports. Despite its popularity, it does have some draw backs. The upheap/downheap operations that drive binary heaps while […]

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

Simple Binary Tree Visualization

Visualizing Trees If you’ve ever implemented a tree based data structure, chances are when it came time to display the tree, you were left scratching your head. Sure, different tree traversal algorithms allow us to print the contents in different orders, but what about an aesthetically pleasing visualization of the tree structure its self? It […]