數(shù)據(jù)結(jié)構(gòu)第九章ppt課件(編輯修改稿)
2025-05-27 18:12 本頁面
【文章內(nèi)容簡介】 32 223323直觀上 的結(jié)論 ,二叉排序樹的高度不能太高 .19. 二叉排序樹上的 刪除在二叉搜索樹中刪除一個結(jié)點時 ,必須將因刪除結(jié)點而斷開的二叉鏈表重新鏈接起來 ,同時確保二叉搜索樹的性質(zhì)不會失去 ..為保證在執(zhí)行刪除后 ,樹的搜索性能不至于降低 ,還需要防止重新鏈接后樹的 高度增加 .1)刪除葉結(jié)點 ,只需將其雙親結(jié)點指向它的指針清零 ,再釋放它即可 .2)被刪結(jié)點缺右子樹 ,可以拿它的左子女結(jié)點頂替它的位置 ,再釋放它 .3)被刪結(jié)點缺左子樹 ,可以拿它的右子女結(jié)點頂替它的位置，再釋放它 . 204)被刪結(jié)點左 ,右子樹都存在 ,可以在它的右子樹中尋找中序下的第一個結(jié)點 (關(guān)鍵碼最小 ),用它的值填補到被刪結(jié)點中 ,再來處理這個結(jié)點的刪除問題 .21. 二叉排序樹上的 查找性能分析.二叉排序樹上的查找與折半查找類似 ..但 ,折半查找長度為 n的表的判定樹惟一 ..顯然 ,n個結(jié)點的二叉排序樹的平均查找長度與樹的二叉樹的形態(tài)有關(guān) .想想 ,最好情況 與 最壞情況各是什么樣 ?.結(jié)論 :在隨機情況下 ,二叉排序樹的平均查找長度是對數(shù)級 .但這種情況出現(xiàn)的概率小于 50%..結(jié)論 :在構(gòu)建二叉排序樹的過程中要進行 ”平衡化”處理 .22.平衡二叉樹 (AVL樹 ).AVL樹的定義.一棵 AVL樹或者是空樹 ,或者是具有下列性質(zhì)的二叉搜索樹 :它的左子樹和右子樹都是 AVL樹 ,且左子樹和右子樹的高度之差的絕對值不超過 1. (a) (b) 23.結(jié)點的平衡因子.每個結(jié)點附加一個數(shù)字 ,給出該結(jié)點右 (左 )子樹的高度減去左 (右 )子樹的高度所得的高度差 .這個數(shù)字即為結(jié)點的平衡因子 balance ..如果一個結(jié)點的平衡因子的絕對值大于 1,則這棵二叉搜索樹就失去了平衡 ,不再是 AVL樹 .任何一個結(jié)點的平衡因子有幾個取值 ?. 一棵 AVL樹的高度保持在什么級別 ?.高度可保持在 O(log2n).24.平衡化處理.平衡化旋轉(zhuǎn)有兩類： 單旋轉(zhuǎn) (左旋和右旋 ) 雙旋轉(zhuǎn) (左平衡和右平衡 ).每插入一個新結(jié)點時 ,AVL樹中相關(guān)結(jié)點的平衡狀態(tài)會發(fā)生改變 .因此 ,在插入一個新結(jié)點后 ,需要從插入位置沿通向根的路徑回溯 ,檢查各結(jié)點的平衡因子 (左 ,右子樹的高度差 ).如果在某一結(jié)點發(fā)現(xiàn)高度不平衡 ,停止回溯 .25.從發(fā)生不平衡的結(jié)點起 ,沿剛才回溯的路徑取直接下兩層的結(jié)點 .如果這三個結(jié)點處于一條直線上，則采用單旋轉(zhuǎn)進行平衡化 .單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn) ,其中一個是另一個的鏡像 ,其方向與不平衡的形狀相關(guān) .如果這三個結(jié)點處于一條折線上，則采用雙旋轉(zhuǎn)進行平衡化 .雙旋轉(zhuǎn)分為先左后右和先右后左兩類 .右單旋轉(zhuǎn)右單旋轉(zhuǎn) 左單旋轉(zhuǎn)左單旋轉(zhuǎn) 左右雙旋轉(zhuǎn)左右雙旋轉(zhuǎn) 右左雙旋轉(zhuǎn)右左雙旋轉(zhuǎn) 26.AVL樹的插入例 :輸入關(guān)鍵碼序列為 { 16, 3, 7, 11, 9, 26, 18, 14, 15 },寫出插入和調(diào)整過程 .0 1 2 0 1161631630701 左右雙旋左右雙旋 73 160 0 73110173 1616119012右單旋右單旋 371690 0013711269 1611011222718 1803163101602 右左雙旋右左雙旋73 9000182611173 26161191左單旋左單旋9716140017112626911112815182318162左右雙旋左右雙旋7300011714911615011126 2614129例 :以 { 30,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1