## 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:

- 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.

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

Some examples of Red Black Trees

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 4^{th} and 5^{th}, 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) |

**The subtree rooted at any node x contains at least 2 ^{bh(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) |

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) = 2^{0}+2^{1}+2^{2}…..+2^{n-1}

S(n) = 2S(n) – S(n)

= 2(2^{0}+2^{1}+2^{2}…..+2^{n-1}) – (2^{0}+2^{1}+2^{2}…..+2^{n-1})

= 2^{1}+2^{2}+2^{3}…..+2^{n} – (2^{0}+2^{1}+2^{2}…..+2^{n-1})

= 2^{n} – 1

Thus, replacing n with bh(x), we get, S(bh(x)) = 2^{bh(x)} – 1

**Mathematical Induction**

Lets try to prove S(bh(x)) = 2^{bh(x)} – 1 by mathematical induction (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. 2
^{bh(x)}– 1 = 2^{0}– 1 = 0 - 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 2
^{bh(x-1)}– 1 internal nodes. Thus, the subtree rooted at x will contain at least ( 2^{bh(x)-1}– 1 ) + ( 2^{bh(x)-1}– 1 ) + 1 internal nodes = 2.2^{bh(x)-1}-1 = 2^{bh(x)-1+1 }-1 = 2^{bh(x)-1}-1 which proves the claim