第二十六講-2 平衡二叉樹B樹B+樹

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)系內(nèi)數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)網(wǎng)站：系內(nèi)數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)網(wǎng)站：00:8080/ds2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系第九章第九章 查查 找找 平衡二叉樹平衡二叉樹2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系本講內(nèi)容本講內(nèi)容l平衡二叉樹平衡二叉樹l概念概念l基本操作基本操作l查找查找l插入插入l建立建立l性能分析性能分析lB-樹樹l概念概念l查找查找2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系平衡二叉樹平衡二叉樹l何謂何謂“二叉平衡樹二叉平衡樹”？l二叉平衡樹的查找性能分析二叉平衡樹的查找性能分析l如何建立如何建立“二叉平衡樹二叉平衡樹”？2022-3-10濱州學(xué)院

2、計(jì)算機(jī)科學(xué)技術(shù)系平衡二叉樹（平衡二叉樹（AVL樹）的定義樹）的定義一棵一棵AVLAVL樹或者是空樹，或者是具有下列性質(zhì)的樹或者是空樹，或者是具有下列性質(zhì)的二叉樹：二叉樹：它的左子樹和右子樹都是它的左子樹和右子樹都是AVLAVL樹，且左子樹，且左子樹和右子樹的高度之差的絕對值不超過樹和右子樹的高度之差的絕對值不超過1 1。 高度不平衡的二叉排序樹高度不平衡的二叉排序樹 高度平衡的二叉排序樹高度平衡的二叉排序樹2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系 二叉平衡樹的特點(diǎn)為：二叉平衡樹的特點(diǎn)為： 樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差的樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差的絕對值不大于絕對值不大于1 l 給每

3、個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，為該結(jié)點(diǎn)左子給每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，為該結(jié)點(diǎn)左子樹的高度減去右子樹的高度所得的差。這個(gè)樹的高度減去右子樹的高度所得的差。這個(gè)數(shù)字即為結(jié)點(diǎn)的數(shù)字即為結(jié)點(diǎn)的平衡因子平衡因子(Balance Factor )。l根據(jù)根據(jù)AVL樹的定義，任一結(jié)點(diǎn)的平衡因子樹的定義，任一結(jié)點(diǎn)的平衡因子只能取只能取 -1，0和和 1。2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系如何建立平衡二叉樹？如何建立平衡二叉樹？l如果一棵二叉排序樹是高度平衡的，它如果一棵二叉排序樹是高度平衡的，它就成為就成為 AVL樹。如果它有樹。如果它有 n 個(gè)結(jié)點(diǎn)，其個(gè)結(jié)點(diǎn)，其高度可保持在高度可保持在O(logn)，平均查找長

4、度也，平均查找長度也可保持在可保持在O(logn)。2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系平衡化旋轉(zhuǎn)平衡化旋轉(zhuǎn)-1l如果在一棵平衡的二叉排序樹中插入一個(gè)新如果在一棵平衡的二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹的結(jié)結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。構(gòu)，使之平衡化。l平衡化旋轉(zhuǎn)有兩類：平衡化旋轉(zhuǎn)有兩類：l 單旋轉(zhuǎn)單旋轉(zhuǎn) ( (左旋和右旋左旋和右旋) )l 雙旋轉(zhuǎn)雙旋轉(zhuǎn) ( (左平衡和右平衡左平衡和右平衡) )2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系l每插入一個(gè)新結(jié)點(diǎn)時(shí)，每插入一個(gè)新結(jié)點(diǎn)時(shí)，AVL樹中相關(guān)結(jié)樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會發(fā)生改變。因此，在插點(diǎn)的平

5、衡狀態(tài)會發(fā)生改變。因此，在插入一個(gè)新結(jié)點(diǎn)后，需要入一個(gè)新結(jié)點(diǎn)后，需要從插入位置沿通從插入位置沿通向根的路徑回溯向根的路徑回溯，檢查各結(jié)點(diǎn)的平衡因檢查各結(jié)點(diǎn)的平衡因子子( (左、右子樹的高度差左、右子樹的高度差) )。如果在某一如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。平衡化旋轉(zhuǎn)平衡化旋轉(zhuǎn)-22022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系l從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。路徑取直接下兩層的結(jié)點(diǎn)。l如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單單旋轉(zhuǎn)旋轉(zhuǎn)進(jìn)行平衡化進(jìn)行平衡化。單旋轉(zhuǎn)可按其方

6、向分為左。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其中一個(gè)是另一個(gè)的鏡單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其中一個(gè)是另一個(gè)的鏡像，其方向與不平衡的形狀相關(guān)。像，其方向與不平衡的形狀相關(guān)。l如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙雙旋轉(zhuǎn)旋轉(zhuǎn)進(jìn)行平衡化進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。右后左兩類。平衡化旋轉(zhuǎn)平衡化旋轉(zhuǎn)-32022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系左單旋轉(zhuǎn)左單旋轉(zhuǎn) (RotateLeft )hhhACEBD(a) (b) (c)hhh+1BACEDhhh+1CEABDl如果在子樹如果在子樹E中插入一個(gè)新結(jié)點(diǎn)，該子樹高度增中插入一個(gè)新

7、結(jié)點(diǎn)，該子樹高度增1導(dǎo)致導(dǎo)致結(jié)點(diǎn)結(jié)點(diǎn)A的平衡因子變成的平衡因子變成+2，出現(xiàn)不平衡。，出現(xiàn)不平衡。l沿插入路徑檢查三個(gè)結(jié)點(diǎn)沿插入路徑檢查三個(gè)結(jié)點(diǎn)A、C和和E。它們處于一條方。它們處于一條方向?yàn)橄驗(yàn)椤啊钡闹本€上，需要做左單旋轉(zhuǎn)。的直線上，需要做左單旋轉(zhuǎn)。l以結(jié)點(diǎn)以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)。反時(shí)針旋轉(zhuǎn)。2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系右單旋轉(zhuǎn)右單旋轉(zhuǎn) (RotateRight )hhhACEBD(a) (b) (c)hh+1BACEDhhh+1CEABDl在左子樹在左子樹D上插入新結(jié)點(diǎn)使其高度增上插入新結(jié)點(diǎn)使其高度增1，導(dǎo)致結(jié)點(diǎn)，導(dǎo)致結(jié)點(diǎn)A的平衡的平衡因子增到因

8、子增到 -2，造成了不平衡。，造成了不平衡。l為使樹恢復(fù)平衡，從為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取沿插入路徑連續(xù)取3個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)A、B和和D，它們處于一條方向?yàn)?，它們處于一條方向?yàn)椤?”的直線上，需要做右單旋轉(zhuǎn)。的直線上，需要做右單旋轉(zhuǎn)。l以結(jié)點(diǎn)以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。順時(shí)針旋轉(zhuǎn)。h2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系先左后右雙旋轉(zhuǎn)先左后右雙旋轉(zhuǎn) (RotationLeftRight)l在子樹在子樹F或或G中插入新結(jié)點(diǎn)，該子樹的高度增中插入新結(jié)點(diǎn)，該子樹的高度增1。結(jié)點(diǎn)結(jié)點(diǎn)A的平衡因子變?yōu)榈钠胶庖蜃幼優(yōu)?-2，發(fā)生了不平衡。，發(fā)生了不平衡。l從結(jié)點(diǎn)從結(jié)點(diǎn)A

9、起沿插入路徑選取起沿插入路徑選取3個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)A、B和和E，它們位于一條形如它們位于一條形如“ ”的折線上，因此需要的折線上，因此需要進(jìn)行進(jìn)行先左后右先左后右的雙旋轉(zhuǎn)。的雙旋轉(zhuǎn)。l首先以結(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代替原來代替原來B的位置，做左單旋轉(zhuǎn)。的位置，做左單旋轉(zhuǎn)。l再以結(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-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系先右后左雙旋轉(zhuǎn)先右后左雙旋轉(zhuǎn) (RotationRightLeft)l右左雙旋轉(zhuǎn)是左右雙旋轉(zhuǎn)的鏡像。右左雙旋

10、轉(zhuǎn)是左右雙旋轉(zhuǎn)的鏡像。l在子樹在子樹F或或G中插入新結(jié)點(diǎn)，該子樹高度增中插入新結(jié)點(diǎn)，該子樹高度增1。結(jié)點(diǎn)結(jié)點(diǎn)A的平衡因子變?yōu)榈钠胶庖蜃幼優(yōu)?，發(fā)生了不平衡。，發(fā)生了不平衡。 l從結(jié)點(diǎn)從結(jié)點(diǎn)A起沿插入路徑選取起沿插入路徑選取3個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)A、C和和D，它們位于一條形如它們位于一條形如“ ”的折線上，需要進(jìn)行的折線上，需要進(jìn)行先右后左先右后左的雙旋轉(zhuǎn)。的雙旋轉(zhuǎn)。l首先做右單旋轉(zhuǎn)：以結(jié)點(diǎn)首先做右單旋轉(zhuǎn)：以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)為旋轉(zhuǎn)軸，將結(jié)點(diǎn)C順時(shí)針旋轉(zhuǎn)，以順時(shí)針旋轉(zhuǎn)，以D代替原來代替原來C的位置。的位置。l再做左單旋轉(zhuǎn)：以結(jié)點(diǎn)再做左單旋轉(zhuǎn)：以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)，恢復(fù)

11、樹的平衡。反時(shí)針旋轉(zhuǎn)，恢復(fù)樹的平衡。2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系1616例，輸入關(guān)鍵碼序列為例，輸入關(guān)鍵碼序列為 16, 3, 7, 11, 9, 16, 3, 7, 11, 9, 26, 18, 14, 15 26, 18, 14, 15 ，插入和調(diào)整過程如下。，插入和調(diào)整過程如下。316377316731173161611937169371126916112022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系181831631673918261173261611997161471126269112022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系15183181673117149161511262

12、61492022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系 在平衡樹上進(jìn)行查找的過程和二叉在平衡樹上進(jìn)行查找的過程和二叉排序樹相同，因此，排序樹相同，因此，查找過程中和給定查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過平衡值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過平衡 樹的深度。樹的深度。查找性能分析：查找性能分析： 問：含問：含 n 個(gè)關(guān)鍵字的二叉平衡樹個(gè)關(guān)鍵字的二叉平衡樹可能達(dá)到的最大深度是多少？可能達(dá)到的最大深度是多少？2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系n = 0空樹空樹最大深度為最大深度為 0n = 1最大深度為最大深度為 1n = 2最大深度為最大深度為 2n = 4最大深度為最大深度為 3n

13、= 7最大深度為最大深度為 4看幾個(gè)具體情況看幾個(gè)具體情況:2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系 因此，在二叉平衡樹上進(jìn)行查找時(shí)，因此，在二叉平衡樹上進(jìn)行查找時(shí)，查找過程中和給定值進(jìn)行比較的關(guān)鍵字查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)和的個(gè)數(shù)和 log(n) 相當(dāng)相當(dāng)。 深度為深度為 h 的二叉平衡樹二叉平衡樹中所含結(jié)點(diǎn)含結(jié)點(diǎn)的最小值的最小值 Nh = h+2/5 - 1。 反之，含有含有 n 個(gè)結(jié)點(diǎn)的二叉平衡樹能個(gè)結(jié)點(diǎn)的二叉平衡樹能達(dá)到的最大深度達(dá)到的最大深度 hn = log ( 5 (n+1) - 2。 2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系B - 樹樹定義定義查找過程查找過

14、程插入操作插入操作刪除操作刪除操作2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系B-樹的定義樹的定義B-樹是一種樹是一種 平衡平衡 的的 多路多路 查找查找 樹： root 50 15 71 84 3 8 20 26 43 56 62 78 89 962022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系 在在 m 階的階的B-樹上，每個(gè)非終端結(jié)點(diǎn)可能樹上，每個(gè)非終端結(jié)點(diǎn)可能含有：含有： n 個(gè)個(gè)關(guān)鍵字關(guān)鍵字 Ki（1 in） nm n 個(gè)個(gè)指向記錄的指針指向記錄的指針 Di（1in） n+1 個(gè)個(gè)指向子樹的指針指向子樹的指針 Ai（0in）多叉樹的特性多叉樹的特性2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系l

15、非葉結(jié)點(diǎn)中的非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字多個(gè)關(guān)鍵字均均自小至大自小至大有有序排列，即：序排列，即：K1 K2 Kn ；l Ai-1 所指子樹上所有關(guān)鍵字均所指子樹上所有關(guān)鍵字均小于小于Ki ；l Ai 所指子樹上所有關(guān)鍵字均所指子樹上所有關(guān)鍵字均大于大于Ki ；查找樹的特性查找樹的特性2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系平衡樹的特性（平衡樹的特性（m階）階）l樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹中的同一層次上；中的同一層次上；l根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹；子樹；l其余所有非葉結(jié)點(diǎn)均至少含有其余所有非葉結(jié)點(diǎn)均至少含有

16、m/2 棵棵子樹，至多含有子樹，至多含有 m 棵子樹；棵子樹；2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系 從根結(jié)點(diǎn)出發(fā)，沿指針從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)搜索結(jié)點(diǎn)和和在在結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找進(jìn)行順序（或折半）查找 兩個(gè)過程兩個(gè)過程交叉進(jìn)行。交叉進(jìn)行。查找過程：查找過程： 若若查找成功查找成功，則，則返回指向返回指向被查關(guān)鍵字所被查關(guān)鍵字所在在結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置；若若查找不成功查找不成功，則，則返回插入位置返回插入位置。2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系在查找不成功之后，需進(jìn)行插入。在查找不成功之后，需進(jìn)行插入。顯然，顯然，關(guān)鍵

17、字插入的位置必定在最下關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點(diǎn)層的非葉結(jié)點(diǎn)，有下列幾種情況：，有下列幾種情況：插入插入1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nm， 不修改指針不修改指針; 例如例如2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系2）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) n=m， 則則需進(jìn)行需進(jìn)行“結(jié)點(diǎn)分裂結(jié)點(diǎn)分裂”，令，令 s = m/2 ， 在原結(jié)點(diǎn)中保留在原結(jié)點(diǎn)中保留 （A0，K1， ， Ks-1，As-1）；）； 建新結(jié)點(diǎn)建新結(jié)點(diǎn) （As，Ks+1， ，Kn，An）；）； 將（將（Ks，p）插入雙親結(jié)點(diǎn)）插入雙親結(jié)點(diǎn)；例如例如3）若雙親為空，則若

18、雙親為空，則建新的根結(jié)點(diǎn)建新的根結(jié)點(diǎn)。 例如例如2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系例如例如:下列為下列為 3 階階B-樹樹50 20 40 80 插入關(guān)鍵字插入關(guān)鍵字 = 60, 60 80 90, 60 80 90 90 50 80 60 30, 40 20 30 50 808030 502022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系 和插入的考慮相反，首先必須找到待刪和插入的考慮相反，首先必須找到待刪關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，結(jié)關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不能小于點(diǎn)中關(guān)鍵字的個(gè)數(shù)不能小于 m/2 -1， 否則，要從其左否則，要從其左(或右或右)兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)“借調(diào)借調(diào)”關(guān)鍵字關(guān)鍵字，若其左和右兄弟結(jié)點(diǎn)均無關(guān)鍵字，若其左和右兄弟結(jié)點(diǎn)均無關(guān)鍵字可借可借(結(jié)點(diǎn)中只有最少量的關(guān)鍵字結(jié)點(diǎn)中只有最少量的關(guān)鍵字)，則必須，則必須進(jìn)行結(jié)點(diǎn)的進(jìn)行結(jié)點(diǎn)的“合并合并”。刪除刪除2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系是是B-樹的一種變型樹的一種變型B+樹樹2022-3-10濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系B+樹的結(jié)構(gòu)特點(diǎn)：樹的結(jié)構(gòu)特點(diǎn)： 每個(gè)葉子結(jié)點(diǎn)中含有每個(gè)葉子結(jié)點(diǎn)中含有 n 個(gè)關(guān)鍵字和個(gè)關(guān)鍵字和 n 個(gè)指向記錄的指針個(gè)指向記錄的指針；并且，所有葉子；并且，所有葉子結(jié)點(diǎn)彼此相鏈接構(gòu)