Red-Black Tree(1)

Introduction to Red-Black Tree

Red-Black Tree is a kind of BST (Binary Search Tree). It support high efficiency search (log n), although it required more storage space. As we know that time can be saved by using more space.

It is quite similar to BST, the only diffence is that each node has its own color. There are five rules to judge whether the tree is a legal Red-Black Tree:

1. Each node is either==black #060606== or ==red #FC1E00==
2. The root node is ==black #060606==
3. Each leaves is ==black #060606==
4. Each path from leaves to root should have same amount of ==black #060606== nodes
5. If a node is ==red #FC1E00==, its children are ==black #060606==

Provements of time complexity Red-Black Tree

Theorem (to be prove): The maximum height of a N nodes BRTree is 2log(N+1)

The inverse negative proposition of original theorem is: A tree has a height of h, it has at least $2^(\frac{h}{2}) -1$ nodes. If we can prove the inverse negative proposition is true, the original one is also true.

Define bh(x) as the amount of black nodes of each path from node x to leaves. According to BRTree rule(4),
each path has same amount of black nodes, which means that the value of bh(x) is constant.According to BRTree rule(5), the red nodes is more than black nodes in each path: bh(x) > h/2.

In that case, the theorem we need to prove is equal to ‘A tree has a height of h, it has at least 2^bh(x)-1 ==black #060606== nodes. ‘

Then we can prove it by mathematical induction:
Basic situation: when the height of tree is 0:
The amount of black nodes is 0 and bh(x) = 0,2^bh(x) -1 is 0, so the proposition is True.
Assumption: Assume when the height of tree is h-1, it has at least 2^bh(x)-1-1.
Induction: when the height of tree is h, for root, bh(root). For lc and rc of root, bh (lc) and bh (rc) can equal to bh(x) or bh(x)-1. From our assumption, lc tree and rc tree of root include at least 2^bh(x)-1-1. As for the whole tree, the amount of nodes is: 2^bh(x)-1-1 + 2^bh(x)-1-1 +1 = 2^bh(x)-1

Thus we prove that the inverse negative proposition is True. The original thorem is also True.