A Software Engineering Space

Deterministic Skip Lists

The Skip List, introduced in 1990 by Pugh[1] is an interesting data structure. Skip lists came in to being as an evolution of the humble linked list. Indeed, skip lists have been described as “linked lists with a fast lane”, which is certainly true, but they are also so, so much more than that. They […]

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

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, characteristics and different methods of implementing them. This last point also required that I have a way of […]