10. 平衡搜索树

Goal: get a search tree data structure that we can insert, delete and search in O(log n). That means we want a tree that's guaranteed to be O(log(n)) in height.
Examples:

AVL trees
2-3 trees
2-3-4 trees
B-trees
Red-black trees ------------------ today
Skip lists
Treaps

Red-black trees

BST data structure with an extra color field for each node satisfying Read-black properties.

Every node is either red or black.
The root & leaves (nil's) are black
Every red node has a black parent.
All simple paths from a node x to a descendant leaf of x have same #black nodes = black-height(x).

black-height(x) does not count x itself.

红黑树例子

The first thing we would do is to prove that these properties imply that the tree has to have height O(log(n)). 这样就可以保证搜索是在log(n) time 解决的了。

Then, the hard part will be to make sure these properties stay true if they initially held true. 也就是说，当我们insert或者delete的时候要在O(log(n))里完成对数据的修改，并保持这些properties.

Height of red-black tree:

Red-black tree with n keys has height h $\leq$ 2lg(n+1) = O(lg(n))

Proof sketch

merge each read node into it's black parent 然后就得到 2-3-4 tree

2-3-4 tree

除了leaves之外，每个2-3-4 tree 的Node都有2个，3个或者4个子节点。
由于红黑树的第四个property 这个2-3-4 tree 的 all leaves have the same depth.

设原来红黑树的高为h，由红黑树转换成的2-3-4 tree的高为h'
n为红黑树中的internal node的数量
# leaves = n+1 （由于红黑树是一个binary tree 并且每个internal node有2个子节点可用induction证）
in a 2-3-4 tree 2h' $\leq$ # leaves $\leq$ 4h'
2h' $\leq$ n+1
h' $\leq$ lg(n+1)
h $\leq$ 2h'
h $\leq$ 2lg(n+1)

Corollary

Queries(Search, Min, Max, Successor, Predecessor run in O(lg n))time in a red-black tree)

Updates

Insert & Delete

BST operation
color changes
restructuring of links via rotaions.

rotations

RB-Insert(x): 以在之前的红黑树insert数字15为例
首先是做一个tree insert. Insert 的时候选择红色。

tree insert

如果之前做tree insert的时候insert 到了一个黑色node的下面，就很舒服。然而如果不是的话，我们就打破了红黑树的第三条property。于是我们首先考虑使用这种方法，对上方的node重新上色。
设A,B为两个红色node,且A,B为唯一一对连起来的红色node,B为A的子节点，当A的同parente node 为红色时一般可使用这种方法。使用这种方法后可能消除问题，也可能导致问题向上传递。而且，当A的parent为root时应该不能使用这种方法处理。

上下层换颜色

在这种情况下，刚才那种方法不能用，我们考虑先使用right rotation(18)
rotate之后这个树更加不平衡了，但是不急，这不是我们最终的目的。
rotate之后我们得到的红黑树没有打破第四条property，这是因为进行rotate的两个节点都是红色的。

rotation

接下来我们使用left rotation(7)
由于7和10一黑一红，简单地rotate之后大破了第四条和第二条property。但是在rotation 完成之后将7和10的颜色换过来之后，我们可以得到一个符合4条标准的黑红树。这个黑红树看起来就非常平衡。
在这里也可以理解刚才为什么要先进行right rotation了。如果不进行right rotation，直接进行left rotation，18会变成root，10变成7的子节点。然后18和7换颜色之后，10和7就成了两个连在一起的一对。一定要让两个连着的红色node在同一侧然后再进行第二次rotate。

left rotate 并换颜色

这个例子看到这里我基本已经知道各种情况怎么做了，但对于一种情况有疑问，就是如果第一种办法可以一直用到顶端怎么处理。
看了书发现解决方法是，在最后，无论如何，都将root设为黑色。（即insert有可能使黑色node层数加一，合情合理。）

Insert 代码

具体代码在英文版算法导论的315,316 页。

delete 代码

因为delete部分是自己看书的所以暂时就没有例子了

RB-TRANSPLANT(T, u, v)
    if u.p = T.nil
        T.root = v
    elseif u == u.p.left
        u.p.left = v
    else u.p.right = v
    v.p = u.p

这个TRANSPLANT和之前普通的BST的TRANSPLANT有所不同。本来最后一行v.p = u.p之前是有一行if的。说是，如果v不是T.nil的话v.p = u.p。这样改的原因应该是，红黑树里面的nil不是不同的nil,是key value 为nil的记录了数个variable的object。

RB-DELETE(T, z)
    y = z
    y-original-color = y.color
    if z.left == T.nil
        x =  z.right
        RB-TRANSPLANT(T, z, z.left)
    elseif z.right == T.nil
        x = z.left
        RB-TRANSPLANT(T, z, z.right)
    else y = TREE-MINIMUM(z.right)
        y-original-color = y.color
        x = y.right
        if y.p == z
            x.p = y
        else RB-TRANSPLANT(T, y, y.right)
            y.right = z.right
            y.right.p = y
        RB-TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y
        y.color = z.color
    if y-original-color == BLACK
        RB- DELETE-FIXUP(T, x)

第一个if和elseif中先把需要删除的node左侧为空和右侧为空的情况讨论清楚了。但是其实存在问题。如果需要删除的node本为红色，那这样删除之后，我们依然可以得到一个符合4条规矩的红黑树。但是，如果我们删除的是一个黑色node，那property 4大概率被打破（如果删的不是root），property 3可能被打破（如果p为红，且子节点中带红），property 2可能被打破（如果删除root）。感觉最后修复起来，可以先按是不是root分类，但还是很复杂。
在这前两种情况下，y-original-color是需要删除的节点的初始颜色，x是顶替位置的节点。
在最后一个else里面，y-original-color是顶替位置的节点（右侧最小的节点）的初始颜色，x是y右侧的子节点。整个流程大致和tree-delete是一致的，只是x.p = y一行让我觉得是没有意义的。比较有意思的是最终顶替节点的颜色变成和原节点一致。也就是说，如果y本来的颜色是红色，根据property 4，y本来下面只能跟两个nil，这样一番操作之后，得到的是一个没有任何问题的红黑树。如果y本来是黑色，那右侧可以跟一个红色node（有可能打破3，一定会打破4，但是容易修复，只要把这个红色node最后变成黑色就好），也可以跟一个nil（这种情况一定且仅仅会打破4，不知道怎么修复）。

前两种情况（删除黑节点时）：
如果删的是root，且顶替节点为红，只需将顶替节点变黑就好。如果顶替节点为黑，不用作任何改变。
如果删的不是root，且顶替节点为红，只需将顶替节点变黑就好。如果顶替节点为黑，顶替的一定是nil。等同说其中一条枝干缺了一个黑色node，不知道如何处理。
最后一种情况（删除黑节点时）：
和前两种情况几乎一致，只是修改颜色的node变成了顶替y位置的节点。上面已经分析过了，同样也是有一种十分棘手的情况。

RB-DELETE-FIXUP(T, x)
    while x ≠ T.root and x.color == BLACK
        if x == x.p.left
            w = x.p.right
            if w.color == RED
                w.color = BLACK                                                //case 1
                x.p.color = RED                                                //case 1
                LEFT-ROTATE(T, x.p)                                            //case 1
                w = x.p.right                                                  //case 1
            if w.left.color == BLACK and w.right.color == BLACK
                w.color = RED                                                  //case 2
                x = x.p                                                        //case 2
            else 
                if w.right.color == BLACK
                    w.left.color = BLACK                                       //case 3
                    w.color = RED                                              //case 3
                    RIGHT-TOTATE(T, w)                                         //case 3
                    w = w.p.right                                              //case 3

                w.color = x.p.color                                            //case 4
                x.p.color = BLACK                                              //case 4
                w.right.color = BLACK                                          //case 4
                LEFT-ROTATE(T, x.p)                                            //case 4
                x = T.root                                                     //case 4
    else(same as then clause with "right" and "left" exchanged)
x.color = BLACK

在这个fixup里面没有把之前的两种情况分出来，而是将它看成一个问题解决了。其实也很有道理，因为出问题的总是左边为nil，用右边node顶替的地方。那要出一个general的解法，那一定是先看看有没有问题（被顶替位置不是root就一定有问题，是root的话也要分情况），有问题的话看看能不能靠换颜色解决，如果不能那要解决的问题就变成了以x为末枝的那一条少了一个黑色的node。

看过代码之后发现，没有问题的情况和有情况但简单换颜色能解决的情况不会进入while loop。十分简单的解决了。后面使用loop和4种case都是为了解决x为黑色（nil）,且x这一条少了一个黑色node的问题。

4 cases

对想出红黑树的人表示服气。大方向好好想想也不是不能想到，但能在知道大方向的前提下找到一种切实可行的方法，实在是厉害。