AVL树

AVL树的节点声明：

下面只是写出了Insert函数以及它调用的函数的程序：

在上面的Insert程序中，if(X < T->Element) 和 else if(X > T->Element)的内容是我没有写出来的，也就是几乎整个程序都没写出来。这个函数是需要谨记的！！！

仔细看这个程序的话，就会发现不是表面上看上去的那么简单！

递归调用Insert函数，接下来如果调整树。最先调整的是，距离插入节点到根的路径上，最先出现不平衡的那个子树。然后检验往上的路径中的子树是否是平衡的。

以上是书上的一个递归Insert程序。

下面是我自己写的一个非递归Insert程序：

这个非递归程序的思想是这样的：

创建一个Position节点q，将Insert函数参数中的X放进去。

先判断函数的参数T是否为NULL，若是，那就返回q。

查找AVL树T中是否有元素X，若有，返回T；

第18行到33行，查找元素X的位置。从根到元素位置的路径上经过的每个节点p(包括根节点，但不包括元素X所在的节点)：如果元素在它左边，这个节点的p->Height=0；如果元素在它右边，这个节点的p->Height=1， p入栈。

第35到43行，将元素X插入到正确位置，它的父节点为p，且p->Height=1。

从45行到98行，将栈s中的指针依次出栈。用i表示出栈的对应节点p的Height的值，first=0表示元素X在p的左子树上，first=1表示元素X在p的右子树上。second=0表示元素X在p的儿子的左子树上，second=1表示元素X在p的儿子的右子树上。 对于出栈的每个节点p，检查是否平衡。如果不平衡，根据first和second调用相应的单旋转或双旋转使子树p平衡。并且，根据节点p的父亲的Height值，使平衡后的子树p重新成为它父亲的对应儿子( p的父亲的Height=0，那么p在平衡前是左儿子，平衡后也应该成为左儿子)。