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

Cache Friendly Linked Data Structures: Pool Allocators and Free Lists

As Bob Dylan once said “The times they are a-changing”, and changing they are. Modern computer architectures are making heavier use of more cores and ever increasing levels of cache. The order in which instructions are executed can no longer be reasonably speculated about due to things like instruction pipelining, multiple cores, and branch prediction. […]

Comparing Balanced Search Tree Algorithms

There is a long standing debate amongst developers on which Self Balancing Binary Search Tree is better: AVL Trees or Red Black Trees. It’s one of those age old debates the inspires religious like fervor in those which choose a side. The situation only became more complicated with the introduction of Left Leaning RedBlack trees, […]

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