I thought a lot about why red-black trees are red and black, and I thought a lot about it, because I’ve never seen a red-black tree. Today I read an article (hats off to the author, a man who drew nearly 100 pictures, very detailed, if you don’t know what a red black tree is, I suggest you read the article “I drew nearly 100 pictures to understand a red black tree”).
I can see that the red and black are used to quickly determine whether the tree satisfies the condition of equilibrium.
Let’s take a look at the five characteristics of red-black trees:
- Property 1: The root node is always black.
- Property 2: Each node is either red or black.
- Property 3: All leaf nodes are null and are black.
- Property 4: Two children of each red node are black. (There are no two consecutive red nodes on the path from each leaf to the root.)
- Property 5: The path from any node to every leaf node in the subtree contains the same number of black nodes (I call it black paths).
I’m just going to show you why I want to color it, but I’m just going to use 4 and 5 properties and a little bit of code. This algorithm is implemented by assuming that every new node inserted is red, because red does not affect the number of black nodes on the path, and therefore does not change the length of the black path. If its parent node is black, then everyone is happy, and the condition is perfectly satisfied to insert a node without affecting the length of the black path. But what if its father is red? Condition 4 says that there can’t be two consecutive red nodes, so OK, I can change its father to black, but this change, there is a black node on the path, so the black path will be longer, may cause imbalance. To see if there is an imbalance, you need to look more broadly.
Suppose we really want to change the color of the parent node now, let’s look at its sibling (I’ll call it uncle node). If father and uncle node as red, then the two brothers have become black, left and right subtrees black path length increase at the same time, then grandfather new node is balanced, then you can rest assured to see grandpa node’s father (progenitor grandpa nodes) are two sons of balance is ok, this is a recursive process. But what if the uncle node is black? This time just unilaterally the father node into a black, so on this side of the father node subtree is taller than uncle node there a layer, this time is out of balance, will let grandpa node can’t accept it, and sure, at this point cannot be balanced by changing the color, so this time will rotate.
The language of color is daddy’s black, everybody’s happy. Dad and uncle are red, just change to black. Dad is red, uncle is black, need to be rotated. So that’s what it means to label a tree red or black, and just by looking at the color, you can figure out how to adjust it.
Extension, only two kinds of color, red and black as the worst case is subtree are all black, but on the other side subtree is black and red, the nature and properties of 3 1 shows that the both ends of this tree is black, so black and red subtree can only is twice as tall as completely black subtree (black path is on the other side of the two times). This is the approximate equilibrium that red-black trees are after.
Next, the above code, adapted from TreeMap tweaks in Java8, is easy to read, if not easy to understand.
Private static <K,V> Boolean colorOf(Entry<K,V> p) {return(p == null ? BLACK : p.color); } private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {private static <K,V> Entry<K,V> preturn(p == null ? null: p.parent); } private static <K,V> voidsetColor(Entry<K,V> p, boolean c) {
if(p ! = null) p.color = c; } private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {private static <K,V> Entry<K,V> preturn(p == null) ? null: p.left; } private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {private static <K,V> Entry<K,V> preturn(p == null) ? null: p.right; } private void fixAfterInsertion(Entry<K,V> x) {// Set the new node to RED. // Condition: the current node is not empty, not root, and the parent is red, if it is black then everyone is happywhile(x ! = null && x ! = root &&x.parent.color == RED) {// The father is the left subtree of the grandfather. The left and right subtrees affect the rotation operation and the method of retrieving the uncle subtreeif(parentOf(x) == leftOf(parentOf(x)))) {K,V> y = rightOf(parentOf(parentOf(x))); // Red, ok, the same color as dad, directly change them to black, to the next loopif (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK); Grandpa / / the node to red (because the father node is red, according to the condition of 4, grandpa node must be black) / / black fathers, grandparents red, virtually no increase black path length / / and then see if grandpa between the node and the node progenitor grandpa is 4 the damage condition, well, into the next cyclesetColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } // If it is not red, it needs to be rotated, as explained in the above articleelse{// Parent is left subtree, say the formula: left left insert right rotate, left left insert left rotate. (This formula can be searched and applies to various balance trees)if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); }} // If the parent is the right subtree, do the reverse of the above logic.else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); }} // Rule No.1: root = BLACK; }Copy the code