Red–Black Trees
Here's the trick: While a node can have more than one outgoing edge, every node has exactly one incoming edge!
We'll use the node itself to store what kind of edge was pointing to it.
-
To make that easier to visualize, let's color-in our nodes.
Node Coloring
If a node had a red “super edge” pointing to it, we'll color it red.
Otherwise, we'll color the node black to remember that it had a normal old black line pointing to it.
(In our encoding, we can just put a bool in our Node class to represent the color).
We left off with this representation of our 2–3–4 tree:
Moving the edge type into the nodes they point to gives us this representation of our original 2–3–4 tree:
-
And that, my friends, is our second self-balancing tree for today: The Red–Black tree!
Meh. Is that really even a different kind of tree?
-
Well, sort of! A Red–Black tree is a binary representation of a 2–3–4 Tree!
-
In practice, Red–Black trees are far more common than 2–3–4 trees. They are both a bit tricky to implement, but Red–Black trees are at least simple to encode!
Red–Black Tree Operations
-
We won't ask you to implement a Red–Black tree structure.
Omigoshthankyou! *pant*; *pant* I was so stressed I stopped breathing three pages ago!
-
Well, breathe easy. Still, we want you to know that you could implement one.
The main thing you need to take away from this page is how to convert from a 2–3–4 tree to a Red–Black tree and vice-versa.
If you understand how to perform 2–3–4 tree operations, and you understand this conversion, then you can also perform Red–Black tree operations! We'll practice this shortly.
For the purposes of this class we'll expect you to be able to perform 2–3–4 tree operations and to understand their equivalence to Red–Black tree operations.
A Word of Warning
-
If you keep the 2–3–4 equivalence in mind, Red–Black trees aren't particularly scary at all!
-
But a lot of times, you'll come across definitions of Red–Black trees that define them on their own. Those definitions include a bunch of seemingly arbitrary rules, such as
No Adjacent Red Nodes
If you think about the 2–3–4 tree, this rule makes sense! Every red node was attached to the side of a 3-node or a 4-node. The node(s) below it must all either be 2-nodes or be the center of a 3-node or a 4-node. That means the node below every red node has to be a black node!
The Root Is Always Black
Again, this rule makes sense in a 2–3–4 tree: Either the root was a 2-node in the first place, in which case it's a black node, or the root was a 3-node or a 4-node. But when we convert a 3-node or a 4-node to its binary “mini tree” representation, the top node is always black.
Every Path from the Root to a Leaf Goes Through the Same Number of Black Nodes
And again, this rule makes sense if we remember the corresponding 2–3–4 tree. We had one black node for every node in our original 2–3–4 tree. So this rule is just telling us that in the corresponding 2–3–4 tree, all the leaves were the same distance from the root!
-
However, if you just start implementing a Red–Black tree from these rules, it's easy (really, really easy!) to end up with a tangled mess of code that's full of conditionals and edge cases.
-
That means that the internet is full of really hard-to-understand Red–Black tree implementations! Proceed with caution!
(When logged in, completion status appears here.)