Red-Black Tree Rules
- Every node is either red or black.
- The root is black.
- Every leaf (NIL) is black.
- If a node is red, then both its children are black.
- For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
We insert node into the tree T as if it were an ordinary Binary Search Tree, and then we fix the tree to preserve the red-black properties.
We will try to understand using few examples how insertion of new nodes cause violation of red-black tree rules and how we can fix these violation as they arise.
- Add 24, 17, 13
- Add 24, 17, 20
- Add 24, 17, 28, 13, 15, 20, 22, 23
Add nodes 24, 17, 13.
Since tree is initially empty, the first node 24 will become the root node. Its color would be black as it is the root node (See rule 2). A node can be linked to a left child and/or a right child. If it is not linked to a child node, we will consider it linked to a leaf node. Since root node 24 is not yet linked to any child nodes, it will have two leaf nodes.
Next we add 17. Since it is lesser than 24, it will add itself as the left child. According to rule 1, the color could be red or black. If the color of the node is black, it will violate rule 5 as we will end up with paths of different black heights 2 (17->left leaf), 2 (17->right leaf) and 1(root’s right leaf). If the color is red, we won’t be violating any rules so we will add it as a red node.
New node is RED
When we add a node, we would like to keep the no. of violations minimum. If the color of the new node is red as it is less likely that it will violate the red-black rules compared to the case where the new node is black. This is because if the new red node is attached to a black one, no rule is broken. It doesn’t change the black height in any of the paths (Rule 4) as the color is red. If we attach a new red node to a red node, rule 3 will be violated. However, this will only happen half the time as at least half of the nodes will be black as we are dealing with a balanced tree. If the new node is black in color, it would always change the black height for its path, violating Rule 4. It’s easier to fix violations of Rule 3 (parent and child are both red) than Rule 4 (black heights differ) which will always involve rotations. This is the reason why we will add the new node as red node. Next we add 13. Since it is lesser than 17, it will add as the left child to 17. Since the color of the node is red, it will violate rule 4 as 13′s parent 17 is also a red node. To fix this we flip the color of its parent and grandparent. It is important that we flip the color of grandparent also so that rule 5 of the tree above it is not violated. Since 17 becomes a black node, we end up with lesser black nodes on the right side branch thus violating rule 5. It also violates rule 2 as the root node 24 is red. To fix this, we right rotate the grandparent 24 so that the tree is balanced.
Add nodes 24, 17, 20.
This is similiar to example 1, except that instead of adding 13 we add 20 so that it adds as the right child of 17. Since the new node’s color is red, it violates rule 4. We end up with two red nodes linked to each other. To fix this we left rotate 17 so that the child node and its parent, both are on the same side of its grandparent. In this example, after left rotation, we end up with 17 and 20 on left side of 24. Now the tree structure is exactly same as example 1 and to fix the tree we apply the same set of changes as in example 1.
Add 24, 17, 28, 13, 15, 20, 22, 23.
In example 3, we will first deal with the new node 28. Since 28 > 24, it will be add as the right child to root node 24.
Next we add 13.
It will add as left child to node 17. It now violates rule 4. Nodes 17 and 13 both are red. If we flip the color of 17 to black, we must also do it for the grandparent 24 and the uncle 28 else we will be violationg rule 5 as we will end up with different black heights. After the flip, root node 24 gets red color and violates rule 2 so we change its color back to black.
Add 15 to the above tree.
Since 13<15<17, it will add as the right child to 13. Since the new node is red, it now violates rule 4. The current tree structure is similar to example 2. We left rotate 13 so that the child node and its parent, both fall on the same side of its grandparent 17. Now we flip colors of the parent and grandparent so that rule 4 is restored. Since the parent node’s 15 color is now black, there is a difference in the number of black nodes int the paths originating from its grandparent 17. The left subtree of the grandparent 17 has now two black nodes since 15′s color is flipped to black whereas the right subttree still has one black node. This violates rule 5. To fix this we right rotate at the grandparent node 17.
Add 20 to the above tree.
Since 20>17, it adds as right child to node 17. This results in violation of rule 4. We flip the color of its parent and grandparent nodes. Since the color of its uncle, node 13, is red. We flip its color to black so that rule 5 is not broken.
Add 22 to the above tree.
Since 22>20, it adds as right child to node 20. This results in violation of rule 4. We flip the color of its parent (20) and grandparent (17). Since the uncle is a leaf node here, its color will be black so we don’t have to flip its color. The paths originating from the grandparent 17 will now have different number of black nodes. The right path will have an extra black node because of the flip. This violates rule 5. To fix it we left rotate at node 17.
Add 23 to the above tree.
Since 23>22, it adds as right child to node 22. This results in violation of rule 4. To resolve this we need to flip the colors of parent and grandparent. Since the uncle of node 23, node 17 is red in color, we need to flip its color too to black. Now the grandparent 20 becomes the node in context for further verification. Since its parent 15 is red, it violates rule 4. Before we flip the colors, we need to make sure node 20 is in the same side of the tree as its parent. Its parent 15 is on left side of grandparent 24 but 20 is in right side of the parent 15. To fix this, we left rotate node 15 so that both 15 and 20 are on the left side of grandparent 24.
Now we flip the colors of the parent and grandparent. Since color uncle 24 is black, we don’t have to flip its color. This results in violation of rule 5 as the black height of node 24 will differ on the right side path. Note that the flip operation performed resulted in an extra black node in the left path. To fix this we right rotate node 24. Now 20 becomes the new root node.