數(shù)據(jù)結(jié)構(gòu)高級(jí)樹(shù)形結(jié)構(gòu)課件

1、2022-1-20Data Mining: Concepts and Techniques1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): :高級(jí)樹(shù)形結(jié)構(gòu)高級(jí)樹(shù)形結(jié)構(gòu)Data Structure 主講教師：駱嘉偉主講教師：駱嘉偉Office number:軟件院軟件院503E-mail: 2022-1-20Data Mining: Concepts and Techniques2Trie結(jié)構(gòu)結(jié)構(gòu)當(dāng)關(guān)鍵碼是可變長(zhǎng)時(shí)，當(dāng)關(guān)鍵碼是可變長(zhǎng)時(shí)，Trie樹(shù)是一種特別有用的索引樹(shù)是一種特別有用的索引結(jié)構(gòu)。結(jié)構(gòu)。Trie樹(shù)的定義樹(shù)的定義nTrie樹(shù)是一棵度樹(shù)是一棵度 m 2 的樹(shù)，它的每一層分支不是靠的樹(shù)，它的每一層分支不是靠整個(gè)關(guān)鍵碼

2、的值來(lái)確定，而是由關(guān)鍵碼的一個(gè)分量整個(gè)關(guān)鍵碼的值來(lái)確定，而是由關(guān)鍵碼的一個(gè)分量來(lái)確定。來(lái)確定。n如下圖所示如下圖所示Trie樹(shù)，關(guān)鍵碼由英文字母組成。它包樹(shù)，關(guān)鍵碼由英文字母組成。它包括兩類(lèi)結(jié)點(diǎn)：元素結(jié)點(diǎn)和分支結(jié)點(diǎn)。元素結(jié)點(diǎn)包含括兩類(lèi)結(jié)點(diǎn)：元素結(jié)點(diǎn)和分支結(jié)點(diǎn)。元素結(jié)點(diǎn)包含整個(gè)整個(gè)key數(shù)據(jù)；分支結(jié)點(diǎn)有數(shù)據(jù)；分支結(jié)點(diǎn)有27個(gè)指針，其中有一個(gè)空個(gè)指針，其中有一個(gè)空白字符白字符b，用來(lái)終結(jié)關(guān)鍵碼；其它用來(lái)標(biāo)識(shí)用來(lái)終結(jié)關(guān)鍵碼；其它用來(lái)標(biāo)識(shí)a, b,., z等等26個(gè)英文字母。個(gè)英文字母。2022-1-20Data Mining: Concepts and Techniques32022-1-20Dat

3、a Mining: Concepts and Techniques4特點(diǎn)特點(diǎn)n在第在第0層，所有的關(guān)鍵碼根據(jù)它們第層，所有的關(guān)鍵碼根據(jù)它們第0位字符位字符, 被劃分被劃分到互不相交的到互不相交的27個(gè)類(lèi)中。個(gè)類(lèi)中。n因此，因此，rootbrch.linki 指向一棵子指向一棵子Trie樹(shù)，該子樹(shù)，該子Trie樹(shù)上所包含的所有關(guān)鍵碼都是以第樹(shù)上所包含的所有關(guān)鍵碼都是以第 i 個(gè)英文字母開(kāi)頭。個(gè)英文字母開(kāi)頭。n若某一關(guān)鍵碼第若某一關(guān)鍵碼第 j 位字母在英文字母表中順序?yàn)槲蛔帜冈谟⑽淖帜副碇许樞驗(yàn)?i ( i = 0, 1, , 26 ), 則它在則它在Trie樹(shù)的第樹(shù)的第 j 層分支結(jié)點(diǎn)中從第層分

4、支結(jié)點(diǎn)中從第 i 個(gè)指針向下找第個(gè)指針向下找第 j+1 位字母所在結(jié)點(diǎn)。當(dāng)一棵子位字母所在結(jié)點(diǎn)。當(dāng)一棵子Trie樹(shù)上只有一個(gè)關(guān)鍵碼時(shí)，就由一個(gè)元素結(jié)點(diǎn)來(lái)代替。樹(shù)上只有一個(gè)關(guān)鍵碼時(shí)，就由一個(gè)元素結(jié)點(diǎn)來(lái)代替。在這個(gè)結(jié)點(diǎn)中包含有關(guān)鍵碼，以及其它相關(guān)的信息，在這個(gè)結(jié)點(diǎn)中包含有關(guān)鍵碼，以及其它相關(guān)的信息，如對(duì)應(yīng)數(shù)據(jù)對(duì)象的存放地址等。如對(duì)應(yīng)數(shù)據(jù)對(duì)象的存放地址等。 2022-1-20Data Mining: Concepts and Techniques5Trie樹(shù)的搜索樹(shù)的搜索n函數(shù)函數(shù) Search 設(shè)定設(shè)定 current = NULL, 表示表示不指示任何一個(gè)分支結(jié)點(diǎn)不指示任何一個(gè)分支結(jié)點(diǎn), 如果如

5、果 current 指向一個(gè)元素結(jié)點(diǎn)指向一個(gè)元素結(jié)點(diǎn) elem，則則 currentelem.key 是是 current 所指結(jié)點(diǎn)中所指結(jié)點(diǎn)中的關(guān)鍵碼。的關(guān)鍵碼。n為了在為了在Trie樹(shù)上進(jìn)行搜索，要求樹(shù)上進(jìn)行搜索，要求把關(guān)鍵碼把關(guān)鍵碼分解成一些字符元素分解成一些字符元素, 并并根據(jù)這些字符向根據(jù)這些字符向下進(jìn)行分支下進(jìn)行分支。2022-1-20Data Mining: Concepts and Techniques6平衡樹(shù)平衡樹(shù)AVL樹(shù)樹(shù) 高度平衡的二叉搜索樹(shù)高度平衡的二叉搜索樹(shù) AVL樹(shù)的定義樹(shù)的定義:一棵一棵AVL樹(shù)或者是空樹(shù)，或者是具有下列性質(zhì)樹(shù)或者是空樹(shù)，或者是具有下列性質(zhì)的二叉搜

6、索樹(shù)：的二叉搜索樹(shù)：它的左子樹(shù)和右子樹(shù)都是它的左子樹(shù)和右子樹(shù)都是AVL樹(shù)，且左子樹(shù)樹(shù)，且左子樹(shù)和右子樹(shù)的高度之差的絕對(duì)值不超過(guò)和右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1。 高度不平衡的二叉搜索樹(shù)高度不平衡的二叉搜索樹(shù) 高度平衡的二叉搜索高度平衡的二叉搜索2022-1-20Data Mining: Concepts and Techniques7結(jié)點(diǎn)的平衡因子結(jié)點(diǎn)的平衡因子 (balance factor)n每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)右子樹(shù)的高度減每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)右子樹(shù)的高度減去左子樹(shù)的高度所得的高度差。這個(gè)數(shù)字即為結(jié)點(diǎn)的去左子樹(shù)的高度所得的高度差。這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子平衡因

7、子balance 。n根據(jù)根據(jù)AVL樹(shù)的定義，任一結(jié)點(diǎn)的平衡因子只能取樹(shù)的定義，任一結(jié)點(diǎn)的平衡因子只能取 -1，0和和 1。n如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則這棵二叉，則這棵二叉搜索樹(shù)就失去了平衡，不再是搜索樹(shù)就失去了平衡，不再是AVL樹(shù)。樹(shù)。n如果一棵二叉搜索樹(shù)是高度平衡的，它就成為如果一棵二叉搜索樹(shù)是高度平衡的，它就成為 AVL樹(shù)。樹(shù)。如果它有如果它有 n 個(gè)結(jié)點(diǎn)，其高度可保持在個(gè)結(jié)點(diǎn)，其高度可保持在O(log2n)，平均搜平均搜索長(zhǎng)度也可保持在索長(zhǎng)度也可保持在O(log2n)。2022-1-20Data Mining: Concepts and

8、Techniques8平衡化旋轉(zhuǎn)平衡化旋轉(zhuǎn)n如果在一棵平衡的二叉搜索樹(shù)中插入一個(gè)新結(jié)點(diǎn)，如果在一棵平衡的二叉搜索樹(shù)中插入一個(gè)新結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹(shù)的結(jié)構(gòu)，使之平造成了不平衡。此時(shí)必須調(diào)整樹(shù)的結(jié)構(gòu)，使之平衡化。衡化。n平衡化旋轉(zhuǎn)有兩類(lèi)：平衡化旋轉(zhuǎn)有兩類(lèi)：n 單旋轉(zhuǎn)單旋轉(zhuǎn) ( (左旋和右旋左旋和右旋) )n 雙旋轉(zhuǎn)雙旋轉(zhuǎn) ( (左平衡和右平衡左平衡和右平衡) )n每插入一個(gè)新結(jié)點(diǎn)時(shí)，每插入一個(gè)新結(jié)點(diǎn)時(shí)，AVLAVL樹(shù)中相關(guān)結(jié)點(diǎn)的平衡狀樹(shù)中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會(huì)發(fā)生改變。因此，在插入一個(gè)新結(jié)點(diǎn)后，需態(tài)會(huì)發(fā)生改變。因此，在插入一個(gè)新結(jié)點(diǎn)后，需要要從插入位置沿通向根的路徑回溯從插入位置沿通向

9、根的路徑回溯，檢查各結(jié)點(diǎn)檢查各結(jié)點(diǎn)的平衡因子的平衡因子( (左、右子樹(shù)的高度差左、右子樹(shù)的高度差) )。n如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。2022-1-20Data Mining: Concepts and Techniques9平衡化旋轉(zhuǎn)n從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。層的結(jié)點(diǎn)。n如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其中

10、一個(gè)是另一個(gè)的鏡像，其方向與不平衡的形狀相關(guān)。中一個(gè)是另一個(gè)的鏡像，其方向與不平衡的形狀相關(guān)。n如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類(lèi)。雙旋轉(zhuǎn)分為先左后右和先右后左兩類(lèi)。平衡化旋轉(zhuǎn)平衡化旋轉(zhuǎn)2022-1-20Data Mining: Concepts and Techniques10左單旋轉(zhuǎn) (RotateLeft )n如果在子樹(shù)如果在子樹(shù)E中插入一個(gè)新結(jié)點(diǎn)，該子樹(shù)高度增中插入一個(gè)新結(jié)點(diǎn)，該子樹(shù)高度增1導(dǎo)致結(jié)點(diǎn)導(dǎo)致結(jié)點(diǎn)A的平衡因子變成的平衡因子變成+2，出現(xiàn)不平衡。，出現(xiàn)不平衡。n沿插入路徑檢

11、查三個(gè)結(jié)點(diǎn)沿插入路徑檢查三個(gè)結(jié)點(diǎn)A、C和和E。它們處于一條方向?yàn)樗鼈兲幱谝粭l方向?yàn)椤啊钡闹本€上，需要做左單旋轉(zhuǎn)。的直線上，需要做左單旋轉(zhuǎn)。n以結(jié)點(diǎn)以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)。反時(shí)針旋轉(zhuǎn)。hhhACEBD(a) (b) (c)hhh+1BACEDhhh+1CEABD平衡化旋轉(zhuǎn)平衡化旋轉(zhuǎn)2022-1-20Data Mining: Concepts and Techniques11void AVLTree :RotateLeft( AVLNode *Tree, AVLNode * &NewTree ) / NewTree = Treeright; Treeright = N

12、ewTreeleft; NewTreeleft = Tree; 左單旋轉(zhuǎn)左單旋轉(zhuǎn) (RotateLeft )2022-1-20Data Mining: Concepts and Techniques12右單旋轉(zhuǎn)右單旋轉(zhuǎn) (RotateRight )n在左子樹(shù)在左子樹(shù)D D上插入新結(jié)點(diǎn)使其高度增上插入新結(jié)點(diǎn)使其高度增1 1，導(dǎo)致結(jié)點(diǎn)，導(dǎo)致結(jié)點(diǎn)A A的平衡因的平衡因子增到子增到 -2 -2，造成了不平衡。，造成了不平衡。n為使樹(shù)恢復(fù)平衡，從為使樹(shù)恢復(fù)平衡，從A A沿插入路徑連續(xù)取沿插入路徑連續(xù)取3 3個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)A A、B B和和D D，它們處于一條方向?yàn)樗鼈兲幱谝粭l方向?yàn)椤? /”的直線上，需要

13、做右單旋轉(zhuǎn)。的直線上，需要做右單旋轉(zhuǎn)。n以結(jié)點(diǎn)以結(jié)點(diǎn)B B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A A順時(shí)針旋轉(zhuǎn)。順時(shí)針旋轉(zhuǎn)。hhhACEB(a) (b) (c)hh+1BACEDhhh+1CEABDh2022-1-20Data Mining: Concepts and Techniques13void AVLTree:Rotateright ( AVLNode *Tree, AVLNode * &NewTree) / NewTree = Treeleft; Treeleft = NewTreeright; NewTreeright = Tree;右單旋轉(zhuǎn)右單旋轉(zhuǎn) (RotateRight )202

14、2-1-20Data Mining: Concepts and Techniques14先左后右雙旋轉(zhuǎn)先左后右雙旋轉(zhuǎn) (RotationLeftRight)n在子樹(shù)在子樹(shù)F或或G中插入新結(jié)點(diǎn)，該子樹(shù)的高度增中插入新結(jié)點(diǎn)，該子樹(shù)的高度增1。結(jié)點(diǎn)結(jié)點(diǎn)A的平衡因子變?yōu)榈钠胶庖蜃幼優(yōu)?-2，發(fā)生了不平衡。，發(fā)生了不平衡。n從結(jié)點(diǎn)從結(jié)點(diǎn)A起沿插入路徑選取起沿插入路徑選取3個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)A、B和和E，它它們位于一條形如們位于一條形如“ ”的折線上，因此需要進(jìn)行先的折線上，因此需要進(jìn)行先左后右的雙旋轉(zhuǎn)。左后右的雙旋轉(zhuǎn)。n首先以結(jié)點(diǎn)首先以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)為旋轉(zhuǎn)軸，將結(jié)點(diǎn)B反時(shí)針旋轉(zhuǎn)，以反時(shí)針旋轉(zhuǎn)，以E代替

15、原來(lái)代替原來(lái)B的位置，做左單旋轉(zhuǎn)。的位置，做左單旋轉(zhuǎn)。n再以結(jié)點(diǎn)再以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)，做右順時(shí)針旋轉(zhuǎn)，做右單旋轉(zhuǎn)。使之平衡化。單旋轉(zhuǎn)。使之平衡化。2022-1-20Data Mining: Concepts and Techniques152022-1-20Data Mining: Concepts and Techniques16void AVLTree:LeftBalance( AVLNode * &Tree, int & taller ) / AVLNode *leftsub = Treeleft, *rightsub; switch ( leftsub

16、balance ) case -1 : Treebalance = leftsubbalance = 0; RotateRight ( Tree, Tree ); taller = 0; break; case 0 : cout “.n; break; 2022-1-20Data Mining: Concepts and Techniques17case 1 : rightsub = leftsubright; switch ( rightsubbalance ) case -1: Treebalance = 1; leftsubbalance = 0; break; case 0 : Tre

17、ebalance = leftsubbalance = 0; break; case 1 : Treebalance = 0; leftsubbalance = -1; break; 2022-1-20Data Mining: Concepts and Techniques18 rightsubbalance = 0; RotateLeft ( leftsub, Treeleft ); RotateRight ( Tree, Tree ); taller = 0; 2022-1-20Data Mining: Concepts and Techniques19先右后左雙旋轉(zhuǎn)先右后左雙旋轉(zhuǎn) (Ro

18、tationRightLeft)2022-1-20Data Mining: Concepts and Techniques202022-1-20Data Mining: Concepts and Techniques21void AVLTree:RightBalance ( AVLNode * &Tree, int & taller ) / AVLNode *rightsub = Treeright, *leftsub; switch ( rightsubbalance ) case 1 : Treebalance = rightsubbalance = 0; RotateLeft ( Tre

19、e, Tree ); taller = 0; break; case 0 : cout “.n; break; case -1 : leftsub = rightsubleft;2022-1-20Data Mining: Concepts and Techniques22 switch ( leftsubbalance ) case 1 : Treebalance = -1; rightsubbalance = 0; break; case 0 : Treebalance = rightsubbalance = 0; break; case -1 : Treebalance = 0; righ

20、tsubbalance = 1; break; leftsubbalance = 0; RotateRight ( rightsub, Treeleft ); RotateLeft ( Tree, Tree ); taller = 0; 2022-1-20Data Mining: Concepts and Techniques231616316377316731173161611937169371126916112022-1-20Data Mining: Concepts and Techniques24181831631673918261173261611997161471126269112

21、022-1-20Data Mining: Concepts and Techniques25151831816731171491615112626149從空樹(shù)開(kāi)始的建樹(shù)過(guò)程從空樹(shù)開(kāi)始的建樹(shù)過(guò)程2022-1-20Data Mining: Concepts and Techniques26int AVLTree :Insert ( AVLNode* &tree, Type x, int &taller ) / int success; if ( tree = NULL ) tree = new AVLNode (x); success = tree != NULL ? 1 : 0; if ( su

22、ccess ) taller = 1; else if ( x treedata ) success = Insert ( treeright, x, taller ); if ( taller ) switch ( treebalance ) 2022-1-20Data Mining: Concepts and Techniques28 case -1 : treebalance = 0; taller = 0; break; case 0 : treebalance = 1; break; case 1 : RightBalance ( tree, taller ); break; ret

23、urn success;2022-1-20Data Mining: Concepts and Techniques29AvlTree Insert( ElementType X, AvlTree T ) if ( T = NULL ) /* Create and return a one-node tree */ T = malloc( sizeof( struct AvlNode ) ); if ( T = NULL ) FatalError( Out of space! ); else T-Element = X; T-Height = 0; T-Left = T-Right = NULL; /*