Introduction to 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 type of self-balancing binary search tree. However, a red-black tree is a structure that has to adhere to a very strict set of rules in order to make sure that it stays balanced. A red-black tree is a binary search tree which has the following 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.

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. By property 5, the notion of black-height is well defined, since all descending simple paths from the node have the same number of black nodes.

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.

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)

A red-black tree is binary search tree. Operations that don’t change the structure of a tree won’t affect whether the tree satisfies the red-black tree properties. So the lookup and print operations are identical to lookup and print for binary search trees. A red-black tree with n internal nodes has height at most 2lg (n + 1). So below operations will have time complexity of O(lgn)

• Search for Node
• Find minimum or maximum
• Find successor or predecessor

Node Insertion

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). To restore red-black tree properties use coloring and/or rotation 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.

Reference

• https://pages.cs.wisc.edu/~cs400/readings/Red-Black-Trees
• https://medium.com/basecs/painting-nodes-black-with-red-black-trees-60eacb2be9a5