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

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

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

3、a Mining: Concepts and Techniques4特點特點n在第在第0層，所有的關鍵碼根據(jù)它們第層，所有的關鍵碼根據(jù)它們第0位字符位字符, 被劃分被劃分到互不相交的到互不相交的27個類中。個類中。n因此，因此，rootbrch.linki 指向一棵子指向一棵子Trie樹，該子樹，該子Trie樹上所包含的所有關鍵碼都是以第樹上所包含的所有關鍵碼都是以第 i 個英文字母開頭。個英文字母開頭。n若某一關鍵碼第若某一關鍵碼第 j 位字母在英文字母表中順序為位字母在英文字母表中順序為 i ( i = 0, 1, , 26 ), 則它在則它在Trie樹的第樹的第 j 層分支結(jié)點中從第層分

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

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

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

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

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

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

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

11、查三個結(jié)點沿插入路徑檢查三個結(jié)點A、C和和E。它們處于一條方向為它們處于一條方向為“”的直線上，需要做左單旋轉(zhuǎn)。的直線上，需要做左單旋轉(zhuǎn)。n以結(jié)點以結(jié)點C為旋轉(zhuǎn)軸，讓結(jié)點為旋轉(zhuǎn)軸，讓結(jié)點A反時針旋轉(zhuǎn)。反時針旋轉(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在左子樹在左子樹D D上插入新結(jié)點使其高度增上插入新結(jié)點使其高度增1 1，導致結(jié)點，導致結(jié)點A A的平衡因的平衡因子增到子增到 -2 -2，造成了不平衡。，造成了不平衡。n為使樹恢復平衡，從為使樹恢復平衡，從A A沿插入路徑連續(xù)取沿插入路徑連續(xù)取3 3個結(jié)點個結(jié)點A A、B B和和D D，它們處于一條方向為它們處于一條方向為“/ /”的直線上，需要

13、做右單旋轉(zhuǎn)。的直線上，需要做右單旋轉(zhuǎn)。n以結(jié)點以結(jié)點B B為旋轉(zhuǎn)軸，將結(jié)點為旋轉(zhuǎn)軸，將結(jié)點A A順時針旋轉(zhuǎn)。順時針旋轉(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在子樹在子樹F或或G中插入新結(jié)點，該子樹的高度增中插入新結(jié)點，該子樹的高度增1。結(jié)點結(jié)點A的平衡因子變?yōu)榈钠胶庖蜃幼優(yōu)?-2，發(fā)生了不平衡。，發(fā)生了不平衡。n從結(jié)點從結(jié)點A起沿插入路徑選取起沿插入路徑選取3個結(jié)點個結(jié)點A、B和和E，它它們位于一條形如們位于一條形如“ ”的折線上，因此需要進行先的折線上，因此需要進行先左后右的雙旋轉(zhuǎn)。左后右的雙旋轉(zhuǎn)。n首先以結(jié)點首先以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點為旋轉(zhuǎn)軸，將結(jié)點B反時針旋轉(zhuǎn)，以反時針旋轉(zhuǎn)，以E代替

15、原來代替原來B的位置，做左單旋轉(zhuǎn)。的位置，做左單旋轉(zhuǎn)。n再以結(jié)點再以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)，做右順時針旋轉(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從空樹開始的建樹過程從空樹開始的建樹過程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; /*