Red-Black Trees

Definition

• 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

Lemma

• A red-black tree with n internal nodes has height at most \(2\ln(N+1)\)
• Proof $$ \begin{aligned} {\rm sizeof}(x) &= 1+2{\rm sizeof}(child)\ &\ge 1+2\cdot2^{bh(child)}\ &\ge 1+2\cdot2^{bh(x)-1}\ &\ge 1+2\cdot2^{h(x)/2-1}\ h(x)/2-1 &\le\ln(({\rm sizeof}(x)-1)/2) \le\ln({\rm sizeof }(x))\ h(x) &\le 2\ln({\rm sizeof(x)})+1 \end{aligned} $$

Insert

• the initial color of the node is red

Delete

• Delete a leaf node: Reset its parent link to NIL
• Delete a degree 1 node: Replace the node by its single child
• Delete a degree 2 node: Replace the node by the largest one in the left subtree or the smallest one in the right subtree.
• the number of rotations in the DELETE operation is \(O(1)\).红黑树在Insert中旋转次数不超过2，删除的过程中旋转次数不超过3

How to Replace

Accoring to the three situations, the second and third situation can be transfomed into situation 1. Therefore, we only need to care about situation1 -- how to delete a leaf node. Unfortunately, we can't delete leaf node directly, for the existence of external nodes.

• case1
• case2
• case3
• case4