Red Black Tree

定义：

1 二分查找树

2 每个node有一个额外的存储：color （红，黑）

3 root 是黑

4 原本在BST中指向NULL的pointer，在RBT中，全部指向了NIL,每个NIL是黑

5 如果一个node是红，它的孩子都是黑。

6 任意node开始，到NIL的所有路径中，包含了相同的黑node。

image-20180820170413020

###

Fix Up

什麼情況需要對InsertRBT()做修正？ 當新增node接在紅色的node的child pointer，形成紅色與紅色相連時。

  • node(X)為其parent，顏色為紅色；
  • node(Y)為其uncle，其顏色可能為紅色或黑色。
  • node(Z)為其grandparent，顏色必定為黑色(因為node(X)是紅色)

image-20180820193242724

###

根據uncle的顏色是紅色或者黑色，可以將修正(FixUp)分成三種情形(case)：

  1. Case1：uncle是紅色，不論新增的node是node(X)的leftchild或rightchild；
  2. Case2：uncle是黑色，而且新增的node為node(X)的rightchild；
  3. Case3：uncle是黑色，而且新增的node為node(X)的leftchild。

旋转（Rotation）

搜索树的操作：Tree-Insert 和 Tree-Delete，会改变树的结构，通过旋转进行恢复。

image-20180815004944884

有左和右两种方式。

插入（Insertion）

We can insert a node into an n-node red-black tree in O(lg n) time.

TODO

参考

http://alrightchiu.github.io/SecondRound/red-black-tree-introjian-jie.html

http://alrightchiu.github.io/SecondRound/red-black-tree-insertxin-zeng-zi-liao-yu-fixupxiu-zheng.html