Red Black Tree

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:

1. The root is black.
2. Every node is either red or black.
3. Every leaf (NULL) is black.
4. If a node is red, then both its children are black.
5. 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.

Basic red-black tree with the sentinel nodes added

Operations

As with the binary search tree, we will want to be able to perform the following operations on red-black trees:

1. insert a key value (insert)
2. determine whether a key value is in the tree (lookup)
3. remove key value from the tree (delete)
4. 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:

1. use the BST insert algorithm to add K to the tree
2. color the node containing K red
3. 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.