写给自己看之三：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;
        }
    }

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

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

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;
    }

写给自己看之一：非递归遍历二叉搜索树（栈）

二叉搜索树的遍历是可以采用非递归方式的，其实所有的递归都可以写成循环的方式，就是简单和复杂，看得懂和看不懂之间的区别。
先看一段代码（本以为看了代码就能理解怎么写这么个循环遍历）：

Status InOrderTraverse(BiTree T, Status ( *Visit)(TElemType e)){
 InitStack(S); p = T;
 while(p || !StackEmpty(S)){
  if (p) { Push(S, p); p = p->lchild; }
  else {
   Pop(S, p);
   if(!Visit(p->data)) return ERROR;
   p = p->rchild;
  }
 }
 return OK
}

应该是一段很简洁高效的C/C++代码，但是看得我瞬间晕倒。我根本没看懂是怎么回事情。
再回头想一想什么才算利用栈写循环遍历呢？
首先，作为中序遍历，必然总要走所有的左子树。

    Stack< Node > stack = new Stack< Node >();

    Node n = this.root;

    while (n != null)
    {
        stack.Push(n);
        n = n.LChild;
    }

这一步必然是这样的。 其次，当栈找完所有的左子树的时候，就要打印出该节点的值（这个没问题）。这个时候其实相当于在访问中间节点，因为如果把空的左节点看成非空，那么其实就是打印一个空值，也就是说正真的打印其实是中节点。那么此时只需要遍历该节点的右子树就可以了。

    while (stack.Count != 0)
    {
        n = stack.Pop();
        _visit(n);
        stack.Push(n);
    }

但是，光这段代码不可能继续去遍历这颗右子树啊！怎么办？这个时候看看原来的C/C++代码，有点感觉了。只要把这两个循环结合在一起就可以解决这个问题。灵感来自最后那句stack.Push，只要重新复制n就解决了，不过这其实是一个揣测的操作，我是一点理论根据也没有，就算对了，我感觉依然没有完全搞懂的样子。

    while (n != null || stack.Count != 0)
    {
        if (n != null)
        {
            stack.Push(n);
            n = n.LChild;
        }
        else
        {
            n = stack.Pop();
            _visit(n);
            n = n.RChild;
        }
    }

ArrayList和Hashtable

最近看数据结构的时候在想为什么.Net的Hashtable的key和value都是object，而且没有泛型的版本。直道自己动手练习，才发觉其中奥妙。没有泛型的原因简而言之就是用泛型的话Collision就不好处理了。（不好处理不等于不能处理，就是处理起来明显太麻烦了。)
为Hashtable做铺垫的ArrayList（这个是我蓄意写的泛型版本）：
一点就能看，不想看别点

    class MyArrayList< T >
    {
        private const int INIT_SIZE = 2;

        public int Length { get; private set; }
        public int Capacity { get; private set; }

        private T[] array;

        public MyArrayList():this(INIT_SIZE)
        {
        }

        private MyArrayList(int size)
        {
            array = new T[size];
            this.Length = 0;
            this.Capacity = size;
        }

        public T this[int i] {
            get
            {
                if (i < 0 || i > this.Length - 1)
                    throw new IndexOutOfRangeException();

                return this.array[i];
            }
        }

        private void CheckCapcity()
        {
            if (this.Length >= this.Capacity)
            {
                if (this.Length == int.MaxValue)
                    throw new OverflowException();

                int i = this.Length - 1;

                if (this.Length < int.MaxValue / 2)
                {
                    this.Capacity *= 2;
                }
                else
                {
                    this.Capacity = int.MaxValue;
                }
                Debug.Print("Expand to {0}", this.Capacity);
                T[] newArray = new T[this.Capacity];
                while (i >= 0)
                {
                    newArray[i] = array[i];
                    i--;
                }
                this.array = newArray;

                GC.Collect();
            }
        }

        public void Add(T t)
        {
            this.CheckCapcity();
            this.array[this.Length++] = t;
        }

        public T[] ToArray()
        {
            T[] a = new T[this.Length];
            for (int i = 0; i < this.Length; i++)
            {
                a[i] = this.array[i];
            }
            return a;
        }

        public void Remove(int position)
        {
            if (position < 0 || position >= this.Length)
            {
                throw new IndexOutOfRangeException();
            }

            for (int i = position; i < this.Length - 1; i++)
            {
                this.array[i] = this.array[i + 1];
            }
            this.Length--;
        }

        public void Clear()
        {
            for (int i = 0; i < this.Length; i++)
            {
                this.array = null;
            }

            this.Length = 0;
        }
    }

以下为一个Hashtable：

    class MyHashtable
    {
        private MyArrayList< object > keys;
        private ValueChain[] values;

        private class ValueChain
        {
            public object Value { get; set; }
            public object Key { get; set; }
            public ValueChain next;

            public ValueChain(object key, object value)
            {
                this.Key = key;
                this.Value = value;
                this.next = null;
            }
        }

        //Apparently this is way too samll, it can ensure that Collision happens.
        private const int SIZE = 4;
        private MyHashtable(int size)
        {
            this.keys = new MyArrayList< object >();
            this.values = new ValueChain[size];
        }

        public object[] Keys
        {
            get
            {
                return this.keys.ToArray();
            }
        }

        public object[] Values
        {
            get
            {
                MyArrayList< object > values = new MyArrayList< object >();
                foreach (object k in this.Keys)
                {
                    values.Add(this[k]);
                }
                return values.ToArray();
            }
        }

        public object this[object k]
        {
            get
            {
                int h = hash(k);
                if (this.values[h] == null)
                {
                    throw new IndexOutOfRangeException();
                }
                else
                {
                    ValueChain p = this.values[h];
                    while (p != null)
                    {
                        if (p.Key == k)
                            return p.Value;
                        p = p.next;
                    }
                    throw new IndexOutOfRangeException();
                }
            }
            set
            {
                this.Add(k, value);
            }
        }

        public MyHashtable()
            : this(SIZE)
        {

        }

        public void Add(object key, object value)
        {
            int h = hash(key);
            ValueChain  v = new ValueChain(key, value);
            if (values[h] == null)
            {
                values[h] = v;
                keys.Add(key);
            }
            else
            {
                ValueChain p = values[h];
                ValueChain q = null;
                while (p != null)
                {
                    if (p.Key == key)
                    {
                        p.Value = value;
                        return;
                    }
                    q = p;
                    p = p.next;
                }
                q.next = v;
                keys.Add(key);
                Debug.Print("Collision: {0}", key);
            }
        }

        private int hash(object key)
        {
            //Obviously, this is a dumb idea.
            return Math.Abs(key.GetHashCode()) % SIZE;
        }
    }

很明显的一点就是在比较Key的时候泛型就不管用了，这个时候要么用IComparable和IComparer两个接口，要么就用object一了百了。显然图省事就是object啦~

2010全国高考作文题目真相