写给自己看之二：二叉搜索树的删除操作

删除操作比较搞脑子，需要仔细考虑。

1. 被删除节点n没有孩子。这种情况直接删除就可以。把n.Parent的左或右设成空就可以了。
2. 被删除节点n只有一个孩子。需要区分左右，然后穿越就可以了。
3. 被删除节点n有两个孩子。最麻烦了，这个情况下有两种策略，也就是用前驱或后继替换这个节点，然后删除这个前驱或后继。不同的教材使用不同的策略，但是普遍都采用替换数据的方法。我也觉得替换链接要考虑的东西太多了，还容易出错，不如直接替换节点。再说，树的建立本身就不是为了频繁的插入和删除，而是为了快速的访问节点。

好了，看完这三种情况我发毛了。这么多情况怎么实现？一个一个实现的话会累死的。找来MIT的书看之后发觉其中的确有奥妙。MIT的书强调一点：一个有两个孩子的节点的后继节点不可能有左孩子，同理前驱没有右孩子。这是为什么呢？
答案很简单：假设这个有两个孩子的节点的后继节点有左子树，那么必然可以在这个左子树中找到一个比该后继更小但是又比原节点大的节点，这样就矛盾了。同理证明前驱没有右子树。（这个结论是MIT里面的一个证明题，国内的教材似乎没有强调这一点，导致我看得很晕乎）。
好了现在再回过头看这算中情况，第一第二种情况下，n最多只有一个子节点。在看情况三，也是只有一个字节点。那么这两个有相同的地方了。
其实这个时候只要能把握住总共只有一个子节点这个问题，就可以比较简单的处理这个问题了。

    Node p, child;
    //This block set p as the node to be deleted.
    if (n.LChild == null || n.RChild == null)
    {
        p = n;
    }
    else
    {
        p = Successor(n);
    }

    //In all 3 cases, there will be at most one child for n
    if (p.LChild != null)
    {
        child = p.LChild;
    }
    else
    {
        child = p.RChild;
    }

    //Set the parent of the child
    if (child != null)
    {
        child.Parent = p.Parent;
    }

    //Is the node to be deleted a root?
    if (p.Parent == null)
    {
        this.root = child;
    }
    else
    {
        if (p.Parent.LChild == p)
        {
            p.Parent.LChild = child;
        }
        else
        {
            p.Parent.RChild = child;
        }
    }

    //If the node to be deleted is not the paramter,
    //this means an extra content replacement needs to be made.
    if (p != n)
    {
        n.Key = p.Key;
    }