Introduction
A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black. We also need to keep track of the parent of each node, so that a red-black tree’s node structure would be:
enum Colour{ red, black }; class RB_Node { Colour clr; int val; RB_Node left; RB_Node right; RB_Node parent; }
A red-black tree is a binary search tree which has the following red-black properties:
- The root is black.
- Every node is either red or black.
- Every leaf (NULL) is black.
- If a node is red, then both its children are black.
- Every simple path from a node to a descendant leaf contains the same number of black nodes. Number of black nodes on any simple path from, but not including, a node x down to a leaf is called Black-height of the node.
Implementations of the red-black tree algorithms will usually include the sentinel nodes as a convenient means of flagging that you have reached a leaf node. They are the NULL black nodes of property 2.
Operations
As with the binary search tree, we will want to be able to perform the following operations on red-black trees:
- insert a key value (insert)
- determine whether a key value is in the tree (lookup)
- remove key value from the tree (delete)
- print all of the key values in sorted order (print)
Because a red-black tree is a binary search tree and operations that don’t change the structure of a tree won’t affect whether the tree satisfies the red-black tree properties, the lookup and print operations are identical to lookup and print for binary search trees.
Node insert
The goal of the insert operation is to insert key K into tree T, maintaining T’s red-black tree properties. A special case is required for an empty tree. If T is empty, replace it with a single black node containing K. This ensures that the root property is satisfied. If T is a non-empty tree, then we do the following:
- use the BST insert algorithm to add K to the tree
- color the node containing K red
- restore red-black tree properties (if necessary)
Recall that the BST insert algorithm always adds a leaf node. Because we are dealing with a non-empty red-black tree, adding a leaf node will not affect T’s satisfaction of the root property. Moreover, adding a red leaf node will not affect T’s satisfaction of the black property. However, adding a red leaf node may affect T’s satisfaction of the red property, so we will need to check if that is the case and, if so, fix it (step 3). Property 1 is violated if K is the root, and property 4 is violated if K’s parent is red. In fixing a red property violation, we will need to make sure that we don’t end up with a tree that violates the root or black properties.
For step 3 for inserting into a non-empty tree, what we need to do will depend on the color of K’s parent. Let P be K’s parent. We need to consider two cases:
- Case 1: K’s parent P is black
If K’s parent P is black, then the addition of K did not result in the red property being violated, so there’s nothing more to do.