Red Black Tree (TreeMap-2)


Red Black Rules

When inserting (or deleting) a new node, certain rules must be followed. If they’re followed, the Binary Tree will be balanced.
Rules are:

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

A tree with the above properties is called a Red-Black tree.

Some examples of Red Black Trees

Red Black Tree (TreeMap-2)
Red Black Tree (TreeMap-2)

Black Height

Number of black nodes on any path from, but not including a node x to a leaf is called the black height of x and is denoted by bh(x).
No path from the root to a leaf is more than twice as long as any other path from the root to a leaf.
Applying rules 4th and 5th, shortest path will have all nodes black and the longest path will have alternate red and black nodes as a red node can only have black nodes as children.

Red Black Tree (TreeMap-2)
Red Black Tree (TreeMap-2)

The subtree rooted at any node x contains at least 2bh(x) – 1 internal nodes.
A Red Black tree has least number of internal nodes when it is made up of ONLY the black nodes. Like the below tree.

Red Black Tree (TreeMap-2)
Red Black Tree (TreeMap-2)

Total internal nodes for bh(x)=5 is 1+2+4+8+16=31
For bh(x)=n, Total internal nodes would be:
S(n) = 20+21+22…..+2n-1
S(n) = 2S(n) – S(n)
= 2(20+21+22…..+2n-1) – (20+21+22…..+2n-1)
= 21+22+23…..+2n – (20+21+22…..+2n-1)
= 2n – 1
Thus, replacing n with bh(x), we get, S(bh(x)) = 2bh(x) – 1
Mathematical Induction
Lets try to prove S(bh(x)) = 2bh(x) – 1 by mathematical induction (1).

  1. Suppose height of x is 0 then x must be a leaf. The subtree rooted at x indeed contains at least 0 internal nodes. 2bh(x) – 1 = 20 – 1 = 0
  2. Now consider x has positive height and is an internal node with two children. Each child will have a black-height of either bh(x) or bh(x-1), depending on whether its color is red or black, respectively. If the child node is black, its bh(child node) would be bh(x)-1. Now applying (1), we can say, it will have least 2bh(x-1) – 1 internal nodes. Thus, the subtree rooted at x will contain at least ( 2bh(x)-1 – 1 ) + ( 2bh(x)-1 – 1 ) + 1 internal nodes = 2.2bh(x)-1 -1 = 2bh(x)-1+1 -1 = 2bh(x)-1 -1 which proves the claim

Leave A Reply