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在平衡前是左兒子，平衡後也應該成為左兒子)。