7.6 AVL樹(shù)
讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名申請(qǐng)、虛擬主機(jī)、營(yíng)銷(xiāo)軟件、網(wǎng)站建設(shè)、梅州網(wǎng)站維護(hù)、網(wǎng)站推廣。
7.6.1 AVL樹(shù)的定義
高度平衡的二叉搜索樹(shù)
一棵AVL樹(shù)或者是空樹(shù)，或者是具有下列性質(zhì)的二叉搜索樹(shù)：它的左子樹(shù)和右子樹(shù)都是AVL樹(shù)，且左子樹(shù)和右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1。
高度不平衡的二叉搜索樹(shù) 高度平衡的二叉搜索樹(shù)
結(jié)點(diǎn)的平衡因子balance (balance factor)
1、每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)右子樹(shù)的高度減去左子樹(shù)的高度所得的高度差。這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子balance 。
2、根據(jù)AVL樹(shù)的定義，任一結(jié)點(diǎn)的平衡因子只能取 -1，0和 1。
3、如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則這棵二叉搜索樹(shù)就失去了平衡，不再是AVL樹(shù)。
4、如果一棵二叉搜索樹(shù)是高度平衡的，它就成為 AVL樹(shù)。如果它有n個(gè)結(jié)點(diǎn)，其高度可保持在O(log2n)，平均搜索長(zhǎng)度也可保持在O(log2n)。
AVL樹(shù)的類(lèi)定義
template class Type class AVLTree {
public:
struct AVLNode {
Type data;
AVLNode *left, *right;
int balance;
AVLNode ( ) : left (NULL), right (NULL), balance (0) { }
AVLNode ( Type d, AVLNode *l = NULL, AVLNode *r = NULL )
: data (d), left (l), right (r), balance (0) { }
};
protected:
Type RefValue;
AVLNode *root;
int Insert ( AVLNode* tree, Type x, int taller );
void RotateLeft ( AVLNode *Tree, AVLNode* NewTree );
void RotateRight ( AVLNode *Tree, AVLNode* NewTree );
void LeftBalance ( AVLNode* Tree, int taller );
void RightBalance(AVLNode* Tree, int taller);
int Depth ( AVLNode *t ) const;
public:
AVLTree ( ) : root (NULL) { }
AVLNode ( Type Ref ) : RefValue (Ref), root (NULL) { }
int Insert ( Type x ) {
int taller;
return Insert ( root, x, taller );
}
friend istream operator ( istream in, AVLTreetype Tree );
friend ostream operator ( ostream out, const AVLTreetype Tree );
int Depth ( ) const;
}
7.6.2 平衡化旋轉(zhuǎn)
1、如果在一棵平衡的二叉搜索樹(shù)中插入一個(gè)新結(jié)點(diǎn)，造成了不平衡。
此時(shí)必須調(diào)整樹(shù)的結(jié)構(gòu)，使之平衡化。
2、平衡化旋轉(zhuǎn)有兩類(lèi)：
單旋轉(zhuǎn) (左旋和右旋) 雙旋轉(zhuǎn) (左平衡和右平衡)
3、每插入一個(gè)新結(jié)點(diǎn)時(shí)，AVL樹(shù)中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會(huì)發(fā)生改變。因此，在插入一個(gè)新結(jié)點(diǎn)后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點(diǎn)的平衡因子(左、右子樹(shù)的高度差)。
4、如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。
5、從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。
6、 如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其中一個(gè)是另一個(gè)的鏡像，其方向與不平衡的形狀相關(guān)。
7、如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類(lèi)。
右單旋轉(zhuǎn)
左單旋轉(zhuǎn)
左右雙旋轉(zhuǎn)
右左雙旋轉(zhuǎn)
1、左單旋轉(zhuǎn) (RotateLeft )
(1)如果在子樹(shù)E中插入一個(gè)新結(jié)點(diǎn)，該子樹(shù)高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成+2，出現(xiàn)不平衡。
(2)沿插入路徑檢查三個(gè)結(jié)點(diǎn)A、C和E。它們處于一條方向?yàn)椤癨”的直線上，需要做左單旋轉(zhuǎn)。
(3)以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)。
左單旋轉(zhuǎn)的算法
template class Type void AVLTreetype:: RotateLeft ( AVLNode *Tree, AVLNode* NewTree ) {
NewTree = Tree→right;
Tree→right = NewTree→left;
NewTree→left = Tree;
}
2、右單旋轉(zhuǎn) (RotateRight )
(1)在左子樹(shù)D上插入新結(jié)點(diǎn)使其高度增1，導(dǎo)致結(jié)點(diǎn)A的平衡因子增到 -2，造成了不平衡。
(2) 為使樹(shù)恢復(fù)平衡，從A沿插入路徑連續(xù)取3個(gè)結(jié)點(diǎn)A、B和D，它們處于一條方向?yàn)椤?”的直線上，需要做右單旋轉(zhuǎn)。
(3) 以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。
右單旋轉(zhuǎn)的算法
template class Type void AVLTreetype:: RotateRight( AVLNode *Tree, AVLNode* NewTree) {
NewTree = Tree→left;
Tree→left = NewTree→right;
NewTree→right = Tree;
}
3、先左后右雙旋轉(zhuǎn) (RotationLeftRight)
(1)在子樹(shù)F或G中插入新結(jié)點(diǎn)，該子樹(shù)的高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?-2，發(fā)生了不平衡。
(2) 從結(jié)點(diǎn)A起沿插入路徑選取3個(gè)結(jié)點(diǎn)A、B和E，它們位于一條形如“?”的折線上，因此需要進(jìn)行先左后右的雙旋轉(zhuǎn)。
(3)首先以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)B反時(shí)針旋轉(zhuǎn)，以E代替原來(lái)B的位置，做左單旋轉(zhuǎn)。
(4) 再以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)，做右單旋轉(zhuǎn)。使之平衡化。
左平衡化的算法
template class Type void AVLTreetype:: LeftBalance ( AVLNode * Tree, int taller ) {
AVLNode *leftsub = Tree→left, *rightsub;
switch ( leftsub→balance ) {
case -1 :
Tree→balance = leftsub→balance = 0;
RotateRight ( Tree, Tree );
taller = 0;
break;
case 0 :
cout “樹(shù)已經(jīng)平衡化.\n";
break;
case 1 :
rightsub = leftsub→right;
switch ( rightsub→balance ) {
case -1:
Tree→balance = 1;
leftsub→balance = 0;
break;
case 0 :
Tree→balance = leftsub→balance = 0;
break;
case 1 :
Tree→balance = 0;
leftsub→balance = -1;
break;
}
rightsub→balance = 0;
RotateLeft ( leftsub, Tree→left );
RotateRight ( Tree, Tree );
taller = 0;
}
}
4、先右后左雙旋轉(zhuǎn) (RotationRightLeft)
(1)右左雙旋轉(zhuǎn)是左右雙旋轉(zhuǎn)的鏡像。
(2) 在子樹(shù)F或G中插入新結(jié)點(diǎn)，該子樹(shù)高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?，發(fā)生了不平衡。
(3) 從結(jié)點(diǎn)A起沿插入路徑選取3個(gè)結(jié)點(diǎn)A、C和D，它們位于一條形如“?”的折線上，需要進(jìn)行先右后左的雙旋轉(zhuǎn)。
(4)首先做右單旋轉(zhuǎn)：以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)C順時(shí)針旋轉(zhuǎn)，以D代替原來(lái)C的位置。
(5) 再做左單旋轉(zhuǎn)：以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)，恢復(fù)樹(shù)的平衡。
右平衡化的算法
template class Type void AVLTreetype:: RightBalance ( AVLNode * Tree, int taller ) {
AVLNode *rightsub = Tree→right, *leftsub;
switch ( rightsub→balance ) {
case 1 :
Tree→balance = rightsub→balance = 0;
RotateLeft ( Tree, Tree );
taller = 0;
break;
case 0 :
cout “樹(shù)已經(jīng)平衡化.\n";
break;
case -1 :
leftsub = rightsub→left;
switch ( leftsub→balance ) {
case 1 :
Tree→balance = -1;
rightsub→balance = 0;
break;
case 0 :
Tree→balance = rightsub→balance = 0;
break;
case -1 :
Tree→balance = 0;
rightsub→balance = 1;
break;
}
leftsub→balance = 0;
RotateRight ( rightsub, Tree→left );
RotateLeft ( Tree, Tree );
taller = 0;
}
}
7.6.3 AVL樹(shù)的插入和刪除
AVL樹(shù)的插入:
1、在向一棵本來(lái)是高度平衡的AVL樹(shù)中插入一個(gè)新結(jié)點(diǎn)時(shí)，如果樹(shù)中某個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值 |balance| 1，則出現(xiàn)了不平衡，需要做平衡化處理。
2、在AVL樹(shù)上定義了重載操作“”和“”，以及中序遍歷的算法。利用這些操作可以執(zhí)行AVL樹(shù)的建立和結(jié)點(diǎn)數(shù)據(jù)的輸出。
3、 算法從一棵空樹(shù)開(kāi)始，通過(guò)輸入一系列對(duì)象的關(guān)鍵碼，逐步建立AVL樹(shù)。在插入新結(jié)點(diǎn)時(shí)使用了前面所給的算法進(jìn)行平衡旋轉(zhuǎn)。
例，輸入關(guān)鍵碼序列為 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，插入和調(diào)整過(guò)程如下。
從空樹(shù)開(kāi)始的建樹(shù)過(guò)程
1、下面的算法將通過(guò)遞歸方式將新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入并逐層修改各結(jié)點(diǎn)的平衡因子。
2、 在發(fā)現(xiàn)不平衡時(shí)立即執(zhí)行相應(yīng)的平衡化旋轉(zhuǎn)操作，使得樹(shù)中各結(jié)點(diǎn)重新平衡化。
3、 在程序中，用變量success記載新結(jié)點(diǎn)是否存儲(chǔ)分配成功，并用它作為函數(shù)的返回值。
4、算法從樹(shù)的根結(jié)點(diǎn)開(kāi)始，遞歸向下找插入位置。在找到插入位置(空指針)后，為新結(jié)點(diǎn)動(dòng)態(tài)分配存儲(chǔ)空間，將它作為葉結(jié)點(diǎn)插入，并置success為1，再將taller置為1，以表明插入成功。在退出遞歸沿插入路徑向上返回時(shí)做必要的調(diào)整。
template class Type int AVLTreetype:: Insert ( AVLNode* tree, Type x, int taller ) {
int success;
if ( tree == NULL ) {
tree = new AVLNode (x);
success = tree != NULL ? 1 : 0;
if ( success ) taller = 1;
}
else if ( x tree→data ) {
success = Insert ( tree→left, x, taller );
if ( taller )
switch ( tree→balance ) {
case -1 :
LeftBalance ( tree, taller );
break;
case 0 :
tree→balance = -1;
break;
case 1 :
tree→balance = 0;
taller = 0;
break;
}
}
else {
success = Insert ( tree→right, x, taller );
if ( taller )
switch ( tree→balance ) {
case -1 :
tree→balance = 0;
taller = 0;
break;
case 0 :
tree→balance = 1;
break;
case 1 :
RightBalance ( tree, taller );
break;
}
}
return success;
}
AVL樹(shù)的重載操作 、 和遍歷算法的實(shí)現(xiàn) :
template class Type istream operator ( istream in, AVLTreetype Tree ) {
Type item;
cout “構(gòu)造AVL樹(shù) :\n";
cout “輸入數(shù)據(jù)(以" Tree.RefValue “結(jié)束): ";
in item;
while ( item != Tree.RefValue ) {
Tree.Insert (item);
cout “輸入數(shù)據(jù)(以" Tree.RefValue “結(jié)束): ";
in item;
}
return in;
}
template class Type void AVLTree type
:: Traverse ( AVLNode *ptr, ostream out ) const { //AVL樹(shù)中序遍歷并輸出數(shù)據(jù)
if ( ptr != NULL ) {
Traverse ( ptr→left, out );
out ptr→data ' ';
Traverse ( ptr→right, out );
}
}
template class Type ostream operator ( ostream out, const AVLTreetype Tree ) {
out “AVL樹(shù)的中序遍歷.\n";
Tree.Traverse ( Tree.root, out );
out endl;
return out;
}
AVL樹(shù)的刪除
1、如果被刪結(jié)點(diǎn)x最多只有一個(gè)子女，那么問(wèn)題比較簡(jiǎn)單。如果被刪結(jié)點(diǎn)x有兩個(gè)子女，首先搜索 x 在中序次序下的直接前驅(qū) y (同樣可以找直接后繼)。再把 結(jié)點(diǎn)y 的內(nèi)容傳送給結(jié)點(diǎn)x，現(xiàn)在問(wèn)題轉(zhuǎn)移到刪除結(jié)點(diǎn) y。 把結(jié)點(diǎn)y當(dāng)作被刪結(jié)點(diǎn)x。
2、 將結(jié)點(diǎn)x從樹(shù)中刪去。因?yàn)榻Y(jié)點(diǎn)x最多有一個(gè)子女，我們可以簡(jiǎn)單地把x的雙親結(jié)點(diǎn)中原來(lái)指向x的指針改指到這個(gè)子女結(jié)點(diǎn)；如果結(jié)點(diǎn)x沒(méi)有子女，x雙親結(jié)點(diǎn)的相應(yīng)指針置為NULL。然后將原來(lái)以結(jié)點(diǎn)x為根的子樹(shù)的高度減1，
3、必須沿x通向根的路徑反向追蹤高度的變化對(duì)路 徑上各個(gè)結(jié)點(diǎn)的影響。
4、 用一個(gè)布爾變量 shorter 來(lái)指明子樹(shù)的高度是否被縮短。在每個(gè)結(jié)點(diǎn)上要做的操作取決于 shorter 的值和結(jié)點(diǎn)的 balance，有時(shí)還要依賴(lài)子女的 balance 。
5、 布爾變量 shorter 的值初始化為T(mén)rue。然后對(duì)于從 x 的雙親到根的路徑上的各個(gè)結(jié)點(diǎn) p，在 shorter 保持為 True 時(shí)執(zhí)行下面的操作。如果 shorter 變成False，算法終止。
6、case 1 : 當(dāng)前結(jié)點(diǎn)p的balance為0。如果它的左子樹(shù)或右子樹(shù)被縮短，則它的 balance改為1或-1，同時(shí) shorter 置為False。
7、case 2 : 結(jié)點(diǎn)p的balance不為0，且較高的子樹(shù)被縮短，則p的balance改為0，同時(shí) shorter 置為T(mén)rue。
8、case 3 : 結(jié)點(diǎn)p的balance不為0，且較矮的子樹(shù)又被縮短，則在結(jié)點(diǎn)p發(fā)生不平衡。需要進(jìn)行平衡化旋轉(zhuǎn)來(lái)恢復(fù)平衡。令p的較高的子樹(shù)的根為 q (該子樹(shù)未被縮短)，根據(jù)q的balance ，有如下3種平衡化操作。
9、case 3a : 如果q的balance為0，執(zhí)行一個(gè)單旋轉(zhuǎn)來(lái)恢復(fù)結(jié)點(diǎn)p的平衡，置shorter為False。
10、 case 3b : 如果q的balance與p的balance相同，則執(zhí)行一個(gè)單旋轉(zhuǎn)來(lái)恢復(fù)平衡，結(jié)點(diǎn)p和q的balance均改為0，同時(shí)置shorter為T(mén)rue。
11、case 3c : 如果p與q的balance相反，則執(zhí)行一個(gè)雙旋轉(zhuǎn)來(lái)恢復(fù)平衡，先圍繞 q 轉(zhuǎn)再?lài)@ p 轉(zhuǎn)。新的根結(jié)點(diǎn)的balance置為0，其它結(jié)點(diǎn)的balance相應(yīng)處理，同時(shí)置shorter為T(mén)rue。
12、 在case 3a, 3b和3c的情形中，旋轉(zhuǎn)的方向取決于是結(jié)點(diǎn)p的哪一棵子樹(shù)被縮短。
7.6.4 AVL樹(shù)的高度
1、設(shè)在新結(jié)點(diǎn)插入前AVL樹(shù)的高度為h，結(jié)點(diǎn)個(gè)數(shù)為n，則插入一個(gè)新結(jié)點(diǎn)的時(shí)間是O(h)。對(duì)于AVL樹(shù)來(lái)說(shuō)，h多大？
2、設(shè) Nh 是高度為 h 的AVL樹(shù)的最小結(jié)點(diǎn)數(shù)。根的一棵子樹(shù)的高度為 h-1，另一棵子樹(shù)的高度為 h-2，這兩棵子樹(shù)也是高度平衡的。因此有 N-1 = 0 (空樹(shù)) N0 = 1 (僅有根結(jié)點(diǎn)) Nh = Nh-1 + Nh-2 +1 , h 0
3、可以證明，對(duì)于 h ? 0，有 Nh = Fh+3 -1 成立。
4、有n個(gè)結(jié)點(diǎn)的AVL樹(shù)的高度不超過(guò)
5、在AVL樹(shù)刪除一個(gè)結(jié)點(diǎn)并做平衡化旋轉(zhuǎn)所需時(shí)間為 O(log2n)。
6、 二叉搜索樹(shù)適合于組織在內(nèi)存中的較小的索引(或目錄)。對(duì)于存放在外存中的較大的文件系統(tǒng)，用二叉搜索樹(shù)來(lái)組織索引不太合適。
7、 在文件檢索系統(tǒng)中大量使用的是用B_樹(shù)或B+樹(shù)做文件索引。
你自己拋的異常....
把throw 那行刪了
用下面的
return?x.SubString(0,p2)
這可以理解，bottom,right代表控件底和右部邊界的坐標(biāo)值，而非高度和寬度。移動(dòng)的話對(duì)邊的邊界自然同步移動(dòng)的了。
重慶分公司
重慶分公司
