Back to Basics — Data Structures Vol II: Red-Black Search Trees
Let’s Talk Trees
For the last volume of the Back to Basics — Data Structures blog, we talked about Binary Search Trees. Fortunately, we covered a lot of ground in the previous blog, so this one will not be as long as the previous one. Of course, if you need a refresher about some terms that we will be using, refer to the previous volume before continuing with this one. Having said that, welcome to the introduction on Red-Black (RB) Search Trees!
In this blog, we will be talking about what an RB tree is, what it actually looks like, the rules that are involved in implementing an RB search tree, and finally, why it is better than a normal Binary Search Tree. There will also be an example of how you can implement this data structure programmatically!
What Does it Look Like?
To start off, we need to know what an RB search tree looks like. Judging from the name, there will be leaf color-coding involved, and we will get to understand the importance of that specific type of color-coding and why it is vital to the tree implementation. Now, here is a picture of a lovely RB search tree!
There Are Rules
As you have already guessed, if we were to do this programmatically, there would have to be some order to it. It would be easy if we had to add these nodes manually, but as the nodes increase, there are a set of rules that need to be fed to our beloved codebase.
First Rule of Binary Trees, you don’t talk abo… oh, wrong article. But joking aside, the first rule you have to keep in mind is, aside from the list of rules I will note down, the RB search tree still follows the main rule of Binary search trees which is: Every node to the right is larger than the parent node, and every node to the left is smaller than the parent node [As seen above]. With that in mind, prepare to be overwhelmed.
The Five Rules:
1- Roots are black: We elaborated in the last blog what the root of a tree is. In our case, the root of the tree has to be black. This makes it so that the tree can have a self-organizing and rotating mechanism to make it a well-balanced tree.
2- Nodes are either Black or Red: The second rule is that every single node in the middle of the tree has the possibility of being either red or black, as opposed to other components in the tree where they can only be one color, aka the root. With that in mind, it is not just the case where it can be, but it is the case where it has to be. Every single node in the middle of the tree needs to have one of these color codings.
3- All red nodes have to have two black children: Every single red node in the tree needs to have two black children underneath it. In the process of adding more nodes, one of two things happens to ensure this rule is being met. Either the tree rotates to accommodate the main rule of binary trees, or the color of the nodes change!
4- All leaves have to be black: Leaves are the nodes at the end of the tree. These leaves are required to be black. In the diagram above you can see that we add NIL nodes at the end of the tree which are important to this rule and the following one. The NIL leaves are always there at the end but are not necessarily visualized when the tree is output.
5- Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes: If you look at the diagram above, you will see that every path a node can take has the same number of black nodes. Let’s take an example for nodes 8 and 13:
Paths node 8 can take:
- 1 → NIL (Two Black Nodes) ⚫️ ⚫️
- 1 → 6 → NIL (Two Black Nodes) ⚫️ 🔴 ⚫️
- 11 → NIL (Two Black Nodes) ⚫️ ⚫️
Paths node 13 can take:
- 8 → 1 → NIL (Two Black Nodes) 🔴⚫️️⚫️️
- 8 → 1 → 6 → NIL (Two Black Nodes) 🔴 ⚫️ 🔴 ⚫️
- 17 → 25 → 22 → NIL (Two Black Nodes) 🔴 ⚫️ 🔴 ⚫️
- etc…
As you can see, for any node, any path it can take has the same number of black nodes. This is vital because it maintains a well-balanced tree which in turn helps us avoid having a degenerate binary search tree, which we discussed in the previous blog. With this mechanism, we are presented with heaps of opportunities to explore!
The Code
Since there was a lot of traction when I provided sample code in the Bellman-Ford blog that I wrote, I decided to reference a sample code on how you would implement the RB search tree! The example provided is a C++ implementation (my preferred language with data structures) of the RB trees and is naturally more extensive than the Bellman-Ford code. You can find the implementation here! Here you can see a tree in action if you were to use that code!
Why Red-Black?
Self-balancing. That is all I am going to say about RB trees. We already mentioned all the benefits and use cases we can have with Binary search trees in the last blog, now imagine having all these possibilities and advantages, in addition to having a tree that will always stay optimal whenever you add or delete nodes to it.
The main downside of an RB tree is how much time it takes to implement. The implementation of all the rules that were mentioned above can get very complicated and is really hard to perfect. And I do mean perfecting the implementation. Unless there is a flawless execution of these rules, the RB tree becomes useless because the rotating mechanism would not work as intended. Consider it a long-term investment. If you are willing to put the time and effort into doing it, re-using it will bring you a much more efficient outcome. To put it in retrospect, here are the run times of both the Binary Search Tree and the RB Search Tree :
- Binary Search Tree: O(logN) Best Case, O(N) Worst Case
- Red Black Tree: O(logN) Best Case, O(logN) Worst Case
So, in both the best and worst cases, it is more efficient to use an RB Tree!
What Now?
Consider this as an introduction to self-balancing data structures. The possibilities from this point forward are incredible. You just learned about a data structure that fixes itself in order to have the optimal form possible! It might sound trivial but it is actually quite impressive.
I hope you enjoyed this blog, and as usual, I provided a hint in the article about what the next topic will be about. Let me know if you have any feedback, comments, or suggestions, on incredible data structures you want to learn about! Till next time!
