Insert and delete

insert 的整个思路很简单。其实只能加在最下面。所以从root开始，每次比较当前node的值和需要insert的值进行比较，决定是要insert在左边还是右边，下一次是和左边的node比较还是右边的node进行比较。知道有一次当前的node是NIL，我们即可将新的value insert在这里。

y = NIL
x = T.root
while x ≠ NIL
    y = x
    if z.key < x.key
        x = x.left
    else x = x.right
z.p = y
if y = Nil
    T.root = z   //tree T was empty
elseif z.key < y.key
    y.left = z
else y.right = z

在这段伪代码里面x指的是当前node。由于我们insert新值的时候需要知道这个位置的parent是哪个node，才使用了y。

delete的思路稍为复杂。如果我们需要删除的node下面的两个node都是NIL, 直接将当前node改成Nil就好。如果我们需要删除的node下面的两个node只有一个是有效的，那直接用那个有效node代替当前node就好。如果两边都是有效node则需要在右侧找最小的node，将它放在当前位置。（这个树的设置是左侧小于，而右侧是大于等于）
为了简化代码，我们设置了一个method TRANSPLANT(T, u, v)。该方法用node v以及其subtree代替u以及u的subtree。

TRANSPLANT(T, u, v)
    if u.p == NIL
        T.root = v
    elseif u == u.p.left
        u.p.left = v
    else u.p.right = v
    if v ≠ NIL
        v.p = u.p

if和elseif里的代码都很容易懂。但最后那个else，我真的就觉得它在简洁代码的时候放弃了代码的可读性。很精巧，但读起来也比较难受。不过比较好的是，else里面的内容完完全全就是之前分析的第三种情况。知道了目的之后，读这样的代码也可以接受。

if z.left == NIL
    TRANSPLANT(T, z, z.right)
elseif z.right == NIL
    TRANSPLANT(T, z, z.left)
else 
    y = TREE-MINIMUM(z.right)
    if y.p ≠ z
        TRANSPLANT(T, y, y.right)
        y.right = z.right
        y.right.p = y
    TRANSPLANT(T, z, y)
    y.left = z.left
    y.left.p = y