Top-Down 2-3-4-5 Trees: The Red/Black Tree time forgot

The 1978 paper "A Dichromatic Framework for Balanced Trees" by Guibas and Sedgewick[1] in which the authors introduced red/black trees to the world, they discuss algorithms for bottom up 2-3 tree's, bottom up 2-3-4 tree's, and bottom up AVL tree's usin

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

Validating Red/Black Trees

Red/Black Trees are ubiquitous in computer science, and anyone who has taken more than a cursory glance at this site will know that I have spent a fair bit of time studying red/black trees, their various properties, characteris

Bottom up Red/Black Trees: The simplicity of LLRB Trees, with none of the penalty.

On my shelf I have books by no less than 7 different authors that contain sections on implementing Red/Black Tree's. Almost all of them begin with an introduction to 2-3-4 tree's. In addition, almost all of them detail algorith

Implementing the Iterator Pattern on Search Tree's without Parent Pointers.

Two Posts on Iterators in a row? I know, I know. But at the risk of sounding like some kind of evangelist: If you're going to insist on implementing your own containers, you must implement iterators for them. I won't repeat my

Search
Recent Posts
Meta