写给自己看之三：AVL树的插入

当初没有学会，考试似乎也不考，所以没放在心上。但是心血来潮一下，搞了一下这个东西。
AVL树（平衡树）的定义：

每个节点左子树的高度和右子树的高度差的绝对值小于2.即：| h(left[x]) - h(right[x]) | < 2。

这样做的好处就是把二叉树的树高严格控制在log(N)上。从而杜绝成为链表的情况。
如何才能做到这点呢？
我读的教材所采用的方法是多设一个节点信息叫BF(Balance Factor)作为枚举类型。三个值分别为：LH(Left High)，EH(Equal High)和RH(Right High)并采用递归插入。说实话，作者能写出这么牛的递归并且保证正确相信难倒了不少学生（包括我）。
还有一本经典教材，采取不同的方法解决这个问题：节点增设高度信息。然后对插入路径进行高度平衡。我比较青睐这种做法。
然而这种做法却需要一个额外的节点来表示空节点，否则无法正确处理高度差。所以自然而然想到了null object这个模式。
好了，现在开始解决插入中最麻烦的问题：平衡高度。
一共4中情况（OMG！）但是都只需要知道失去平衡的最小的祖先节点就可以了（这就是回溯插入路径）：

1. 受影响的节点从1增加到2，左子树的树高是1。也就是插入的这个左子树的左边。这种情况只要对高度差为2的节点进行一次向右旋转就可以了。
2. 受影响的节点从-1增加到-2，右子树的树高是-1。也就是插入这个右子树右边。这种情况需要对高度差为2的节点进行一次向左的旋转。
3. 受影响的节点从1增加到2，左子树的树高是-1.也就是插入的是这个左子树的右边。这种情况比较复杂。为了保持中序遍历的正确性（很重要），需要先对这个左子树做一次向左的旋转。然后问题转化为1的情况。
4. 受影响的节点从-1增加到-2，右子树树高是1.也就是插入这个右子树的左边。这种情况需要对这个右子树做一次向右的旋转，转化为情况2。

晕了么？我是晕了。但是通过画图就知道是怎么回事了。还有就是看教材上的图片，教材上的图应该能解释一下问题。还有一点非常好的地方就是不存在别的情况（教材上说了就那么4种，再多就是不正常的了）。
现在的问题是怎么旋转？
先看图:

对这种情况下的x节点做一次向左的旋转。
结果图：

从结果可以看出唯一一个需要变动的字节点就是q，别的节点原来在什么位置现在还在什么位置。一开始听到旋转我马上就晕眩了。现在把图画出来自己研究一下，也就只需要变动一个节点，这样的操作显然不是很困难。但是边界检查很重要。这时有两种情况：

1. x的父节点是空。也就是x本身是root，那么把root指向y就可以了。
2. q是个空节点。这是不需要对q的parent节点进行操作。

左旋转的代码：

private void Rotate_to_Left(Node x)
{
    Node y = x.RChild;
    Node z = x.Parent;
    Node q = y.LChild;

    if (z == NULL_NODE)
    {
        this.root = y;
    }
    else
    {
        if (z.LChild == x)
        {
            z.LChild = y;
        }
        else
        {
            z.RChild = y;
        }
    }
    y.Parent = z;

    y.LChild = x;
    x.Parent = y;

    x.RChild = q;
    if (q != NULL_NODE)
    {
        q.Parent = x;
    }
}

右旋转也一样只有一个子节点需要改变，代码如下：

    private void Rotate_to_Right(Node x)
    {
        Node y = x.LChild;
        Node z = x.Parent;
        Node q = y.RChild;

        if (z == NULL_NODE)
        {
            this.root = y;
        }
        else
        {
            if (z.LChild == x)
            {
                z.LChild = y;
            }
            else
            {
                z.RChild = y;
            }
        }
        y.Parent = z;

        y.RChild = x;
        x.Parent = y;

        x.LChild = q;
        if (q != NULL_NODE)
        {
            q.Parent = x;
        };
    }

接着的关键问题就是如何计算节点的高度了，问题不难，但是注意我有一个null object: NULL_NODE。这个节点没有父，左，右和高度信息。

    public int Height
    {
        get
        {
            if (this == NULL_NODE)
            {
                return 0;
            }

            List< Node > nodes = new List< Node >() { this };
            List< List < Node > > height = new List< List< Node > >() { nodes };

            while (true)
            {
                nodes = new List< Node >();
                foreach (Node n in height[height.Count - 1])
                {
                    if (n.LChild != NULL_NODE)
                    {
                        nodes.Add(n.LChild);
                    }
                    if(n.RChild != NULL_NODE)
                    {
                        nodes.Add(n.RChild);
                    }
                }

                if (nodes.Count != 0)
                {
                    height.Add(nodes);
                }
                else
                {
                    break;
                }
            }

            return height.Count;
        }
    }

下面处理如何使这颗树回复平衡：

    private void balance(Node x)
    {
        int balance_factor = x.LChild.Height - x.RChild.Height;
        //There are 4 cases:
        //1. balance factor increased form 1 to 2; do a roatation toward right can address the problem
        //2. balance factor increased from -1 to -2; do a rotation toward left can address the problem

        if (balance_factor == 2)
        {
            if (x.LChild.LChild.Height < x.LChild.RChild.Height)
            {
                this.Rotate_to_Left(x.LChild);
            }
            this.Rotate_to_Right(x);
        }

        if (balance_factor == -2)
        {
            if (x.RChild.LChild.Height > x.RChild.RChild.Height)
            {
                this.Rotate_to_Right(x.RChild);
            }
            this.Rotate_to_Left(x);
        }
    }

和二叉搜索树插入唯一不同的一点就是在插入结束的时候回溯到根节点：

    public void Add(Node n)
    {
        Node p = this.root;
        Node q = NULL_NODE;

        if (p == NULL_NODE)
        {
            this.root = n;
        }
        else
        {
            while (p != NULL_NODE)
            {
                q = p;
                if (n.Key > p.Key)
                {
                    p = p.RChild;
                }
                else
                {
                    p = p.LChild;
                }
            }

            if (n.Key > q.Key)
            {
                q.RChild = n;
            }
            else
            {
                q.LChild = n;
            }
            n.Parent = q;
        }
        n = n.Parent;
        while (n != NULL_NODE)
        {
            balance(n);
            n = n.Parent;
        }
    }