Red-Black trees, oh my (part 1)

Anything new this time?

Have you ever really tried understanding red-black trees? I don’t mean  reading a description of their properties, glancing over some pseudo-code, and calling it a day. I mean taking the time necessary to study the basis of the abstraction, and develop and refine several implementations. I did, oh did I ever.

Why did I feel it necessary to devote so much time to this particular data structure, especially one so popular, and hence, covered? There are two reasons. First, I was lazy in college and did not take the the time to understand the why behind the what. This led to a void in my brain I’ve been meaning to fill for years. Second, a lot of the explanations and implementations I’ve seen online are lacking in conciseness, accuracy, and are just plain confusing. I felt the need to create a red-black tree implementation that was concise, accurate, and showcased the algorithm with obvious semantics.

What I produced was a red-black tree implementation that differs from those I’ve seen, and different in a good way. Since I wrote it I have to admit some bias, even if unintended. At the same time, I’m my own worst critic and there is most definitely some room for improvement.

What’s wrong with what we’ve got?

I’m a firm believer that a program should be readable above all else. I always try and make the semantics obvious from the syntax. I try my best to showcase the algorithm in as concise a way as possible and try not to let other considerations, such as optimization, get in the way of conciseness. This can be a slippery slope though since the lines-of-code metric sucks and can lead a developer into thinking their code is not concise because it appears to be long. I suppose this is a subjective art, but since I’m my own critic here I think I did a fine job (remind me to disable comments).

Some people feel that conciseness and obvious semantics are not readily compatible. This has some truth in it, circumstantial of course. I feel this is born from the notion that more words are able to express more meaning than fewer words. This is wrong and can be dispelled with a larger vocabulary and better choice of words. When attempting to convey some meaning, it’s important to choose the right words; the quality is not justified by the quantity.

Enough poetic waxing. What does conciseness have to do with anything? By definition, communication is concise when it expresses much in few words. When using less but more accurate words, less room exists for interpretation. The less your words can be misinterpreted, the more easily your words can be understood as intended. And that is my goal; write code that concisely describes the intention of the algorithm with as much code as required, no less, no more.

I want this series to be a resource for others curious about red-black trees. Every move I make will be justified and explained. The algorithms presented will be clear in their meaning. This is not an implementation of a check-list. This is a wonderful and complicated data structure and is a joy to understand. This series is a result of my studies, and I would love to share what I learned along the way.

What’s next?

I would like to structure this series as follow:

1. Introduction (you are here)
2. Explanation
3. Insertion
4. Deletion
5. Validation and testing.

Although I retain the right to call an audible at any time.