數(shù)據(jù)結(jié)構(gòu)第17次課-查找c(編輯修改稿)
2025-08-31 16:05 本頁面
【文章內(nèi)容簡介】 167。 結(jié)點(diǎn)的 平衡因子 BF (Balance Factor)是 ?左子樹的深度減去右子樹的深度 ,它只可能是 1, 0, 1 167。 平衡二叉樹 (也稱 AVL樹 )的深度為 O(log2N) (其中 N為結(jié)點(diǎn)個數(shù) ) 167。 它的平均查找長度也是 O(log2N) 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 20頁 平衡二叉樹及平衡因子舉例 1 1 0 0 1 1 0 平衡的二叉樹 1 1 0 0 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 21頁 不平衡的二叉樹 1 0 0 0 2 1 0 2 1 0 1 0 0 不平衡二叉樹及平衡因子舉例 危急 結(jié)點(diǎn) 危急 結(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 22頁 二叉排序樹在結(jié)點(diǎn)添加過程中失衡 的幾種情況 LL RR LR RL 2 a 1 b 0 c 0 c 0 c 0 c 1 b 1 b 1 b 2 a 2 a 2 a 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 23頁 二叉排序樹轉(zhuǎn)成平衡樹 失去平衡后需要進(jìn)行調(diào)整的四種情況 (1) 單向右旋平衡處理 LL ?當(dāng)在 左子樹上插入左結(jié)點(diǎn) ,使平衡因子由 1增至 2時 (2) 單向左旋平衡處理 RR ?當(dāng)在 右子樹上插入右結(jié)點(diǎn) ,使平衡因子由 1增至 2時 (3) 雙向旋轉(zhuǎn) (先左后右 )平衡處理 LR ?當(dāng)在 左子樹上插入右結(jié)點(diǎn) ,使平衡因子由 1增至 2時 (4) 雙向旋轉(zhuǎn) (先右后左 )平衡處理 RL ?當(dāng)在 右子樹上插入左結(jié)點(diǎn) ,使平衡因子由 1增至 2時 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 24頁 2 A 1 B 0 A 0 B BL BR AR h h1 h1 AR BR LL BL LL型平衡旋轉(zhuǎn) A的 左子樹的左子樹 上插入結(jié)點(diǎn)，作順時針旋轉(zhuǎn)。 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 25頁 RR型： A的 右子樹 的 右子樹 上插入結(jié)點(diǎn)，作逆時針旋轉(zhuǎn)。 2 A 1 B 0 A 0 B BR BL AL h1 BL AL RR BR h1 h 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 26頁 2 A 1 B 1 A 0 C CL BL AR h2 h1 h1 LR 1 C h1 CR 0 B BL AR CL CR LR型： A的 左子樹 的 右子樹 上插入結(jié)點(diǎn)，作兩次（逆、順）旋轉(zhuǎn)。 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 27頁 4 RL型： 在 A的右子樹的左子樹上插入結(jié)點(diǎn)，作兩次（順、逆）旋轉(zhuǎn)。 h1 2 A 1 B 1 B 0 C CL AL h2 h1 RL 1 C h1 CR 0 A AL BR CL CR BR 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 28頁 二叉排序樹在結(jié)點(diǎn)添加平衡化方法總結(jié) LL RR LR RL2a1b0c0c0c0c1b1b1b2a2a2a0a0b0c0a0b0c0b0c0a0a0c0b數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 29頁 二叉排序樹轉(zhuǎn)成平衡樹示例 設(shè)關(guān)鍵字序列為 (13,24,37,90,53) 0 13 1 13 0 24 0 37 0 13 2 13 1 24 0 24 0 37 0 53 0 13 0 13 0 37 0 90 0 53 1 24 1 90 2 37 2 24 (a) (b) (c) (d) (e) (f) (g) (h) 24 13 37 53 90 (h) 24 13 37 53 90 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 30頁 練習(xí)：下列情況屬于哪種失衡狀況？應(yīng)該操作哪些結(jié)點(diǎn)？ 21207119122020016LR 12,7,9 RR 12,19 2 12 1 7 0 19 1 9 0 8 0 6 數(shù)據(jù)結(jié)構(gòu) 計算機(jī)與信息學(xué)院 姜敏 第 31頁 二叉排序樹在結(jié)點(diǎn)添加平衡化實(shí)例 例：給定平衡二叉排序樹的輸入結(jié)點(diǎn)序列，請圖示結(jié)點(diǎn)插入過程樹結(jié)構(gòu)的變化。 15， 12， 7， 19， 24， 9， 8， 5， 6 0150121150120
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1