256
AVL樹的研究
3 實現算法
3.1 數據結構
template<typename T>struct BSTNode//平衡二叉樹的結點類型結構體
{
T data;//結點數據類型
int bf;//結點的平衡因子，比二叉鏈表結點多此項
BSTNode<T>*lchild,*rchild;//左右孩子指針
};
3.2 算法
3.2．1 遞歸法
遞歸實現AVL樹的節點刪除的思想如下。
在AVL樹T上刪除值為E的節點步驟如下：
（1） 若樹T為空，返回0退出否則到（2）;
（2） 比較T的數據和E，若相等跳到（3），若E小於T->data跳到（4），若E大於T->data則跳到（5）
（3） 分析T節點的類型
(3.1)若T是葉子節點則直接刪除,樹變矮即lower=1；
(3.2)若T隻有右子樹TR則將右子樹節點的值賦給T，刪除TR節點將T->rchild=NULL，lower=1;
(3.3)若T有左子樹，則找到其中序遍曆的前驅節點P，將P節點值用臨時變量temp保存，並且用指針Tptr保存T；遞歸刪除節點P；將Tptr所指節點即原T節點的值更新為temp；
（4）在左子樹T->lchild中遞歸刪除值為E的節點，若刪除成功檢查左子樹是否變矮即lower的值是否為1；若lower=0返回0退出；若lower=1則進行失衡調整各種情況上文有分析
（5）在右子樹T->rchild中遞歸刪除值為E的節點，若刪除成功檢查左子樹是否變矮即lower的值是否為1；若lower=0返回0退出；若lower=1則進行失衡調整，各種情況上文有分析
3.2．2 非遞歸法
非遞歸的算法思想如下。
在AVL樹T上刪除值為E的節點的步驟如下：
初始化一個棧s ;
（1） 若樹T為空則返回0退出否則跳到(2);
（2） p為工作指針p=T;比較p的數據和E，若相等則跳到（3），若E小於p->data則跳到（4），若E大於p->data則跳到（5）
（3） 分析p節點的類型
（3.1）若p是葉子節點則直接刪除，樹變矮，
（3.1.1）若p是其父節點的左子樹則lower=1;
（3.1.2）若p是其父節點的右子樹則lower=2；
（3.2） 若p隻有右子樹pR則將右子樹節點的值賦給p然後刪除刪除pR，樹變矮，lower的值 和（3.1）一樣分析，之後不再特別說明則都和（3.1）處理一樣。
（3.3） 若p有左子樹pL則將p和pL入棧,且用指針tempptr指向p即tempptr=p然後執行
q=TL ; While(q->rchild){q=q->rchild;s.push(q);}之後可以找到p的前驅節點q，將q的值賦給原p節點即tempptr->data=q->data，若q是葉子節點則直接刪除否則將q的左子樹代替q。樹變矮且彈棧s.pop() ；然後執行如下循環體
（3.3.1）若棧不空且lower不為0則執行
a.彈棧 q=s.top();s.pop();及其q的父節點fa=s.top();
若fa=NULL則表明q是根節點則若要執行下麵 b
或c時不用在給lower賦值了。
b.若lower=1 則表明左子樹變矮，執行相應的失衡調整，並且調整過程中若導致q樹變矮也得根據q為fa的左子樹還是右子樹將 lower=1或為lower=2；
c. 若lower=2 則表明右子樹變矮，執行相應的失衡調整，並且調整過程中若導致q樹變矮也得根據q為fa的左子樹還是右子樹將 lower=1或為lower=2；
退出循環後返回0退出；
（4）將p入棧且p=p->lchild;然後跳到（2）；
（5）將p入棧且p=p->rchild;然後跳到（2）；
最後更新：2017-04-02 06:51:17