# 13.1 Properties of red-black trees

A red-black tree is a binary search tree that satisfies the following red-black properties:

1. Every node is either red or black.
给 BST 的结点添加颜色属性，用以维持平衡
2. The root is black.
这条性质可不可以删除呢？(Exercise 13.1-3)
那将变成 relaxed red-black tree ，也是可以平衡的
令根为黑色只是为了方便（比如后面的插入操作）
3. Every leaf (NIL) is black.
否则根据性质4，最下一层非空结点将不能为红色
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.
简称，黑高一致，保证了黑色结点在横向上分布均匀
又因为黑色结点在纵向上至少占一半，所以整棵树至少有一半结点在横向上大致平衡

## Balance

Red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced. (Exercise 13.1-5)
We call the number of black nodes on any simple path from, but not including, a node x down to a leaf the black-height of the node, denoted bh(x).

# 13.3 Insertion

## Fixup

• 如果 z 为根节点，则性质2被破坏（小问题）
• 如果 z 的父亲为红色， 则性质4被破坏（主要矛盾）

CLRS中用了一大段循环不变量来证明程序的正确性：

The while loop above maintains the following three-part invariant at the start of each iteration of the loop:
a. Node z if red.
b. If z.p if the root, then z.p is the black.
c. If the tree violates any of the red-black properties, then it violates at most one of them, and the violation is of either property 2 or property 4. If the tree violates property 2, it is because z is the root and is red. If the tree violates property 4, it is because both z and z.p are red.

1. z’s uncle y is red
把锅（红色）甩给爷爷，进入下一重循环
然后爷爷或者进入case 2/3，终止循环
或者再次进入case 1，再次甩锅
最坏情况下会一直甩到根节点，所以时间复杂度为O(lg n)
2. z’s uncle y is black and z is a right child
直接通过旋转转化成case 3
3. z’s uncle y is black and z is a left child
这里用了一种常用的操作：
父亲把家产（黑色）传给儿子（原本为红色），自己就没钱了（变成红色），然后让儿子继承自己的位置（通过旋转），以此维持社会和谐（黑高一致）
更一般地，可以写个子函数叫“换色旋转”，在下面的删除里也会用上

# 13.4 Deletion

The procedure RB-T RANSPLANT differs from T RANSPLANT in two ways.
First, line 1 references the sentinel T.nil instead of NIL.
Second, the assignment to v.p in line 6 occurs unconditionally:
we can assign to v.p even if v points to the sentinel.
In fact, we shall exploit the ability to assign to v.p when v = T.nil.

（一个小细节：第12、13行看似没用（ x本来就是 y的孩子，为什么还要 x.p = y？），实则有用（为什么呢？因为 x有可能为 T.nil，那么 x.p就不一定是 y））

• y是对于颜色来说被删除的点
怎么理解这句话呢？
在 case 1/2 里， y等于 z
在 case 3 里， y等于 z的后继
首先是 z被它的后继 y覆盖，但 y要继承 z的颜色，所以对于颜色来说， z并没有被删除
然后是把 y从原来的位置删除掉，即转化成了 case 1/2（因为后继最多只有一个孩子）所以对于颜色来说，真正被删除的是 y
• x是代替了 y的点（ x有可能为 T.nil，但是无所谓（再次体现了 T.nil的优势））

• 如果 y为根， x为红，则破坏性质2（小问题）
• 如果 y-original-color为黑，则破坏性质5
• 如果 xx.p都为红，则破坏性质4
首先注意到，此时 y-original-color一定为黑，同时也破坏了性质5
所以再用插入那里的套路处理双红是不妥当的
然后注意到，只要让 x继承 y的黑色，就可以了
所以这也是小问题

## Fixup

(The extra black on a node is reflected in x’s pointing to the node rather than in the color attribute)

The key idea is that in each case, the transformation applied preserves the number of black nodes (including x’s extra black) from (and including) the root of the subtree shown to each of the subtrees $$\alpha ,\beta ,\dots ,\zeta$$.

1. x’s sibling w is red
通过上面提到换色旋转（B、D 之间）转化成 case 2/3/4
2. x’s sibling w is black, and w’s right children is black, and w’s left children is black
因为 w的两个孩子都是黑色，所以 w可以变成红色，所以可以甩锅给父亲（类似于插入的套路）
3. x’s sibling w is black, and w’s right children is black, and w’s left children is red
通过上面提到的换色旋转（C、D 之间）转化成 case 4
4. x’s sibling w is black, and w’s right children is red
首先是换色旋转（B、D 之间），然后把 E 染黑