[工學]數據結構第17次課-查找c(編輯修改稿)
2025-02-15 11:23 本頁面
【文章內容簡介】 67。 結點的 平衡因子 BF (Balance Factor)是 ?左子樹的深度減去右子樹的深度 ,它只可能是 1, 0, 1 167。 平衡二叉樹 (也稱 AVL樹 )的深度為 O(log2N) (其中 N為結點個數 ) 167。 它的平均查找長度也是 O(log2N) 數據結構 計算機與信息學院 姜敏 第 20頁 平衡二叉樹及平衡因子舉例 1 1 0 0 1 1 0 平衡的二叉樹 1 1 0 0 數據結構 計算機與信息學院 姜敏 第 21頁 不平衡的二叉樹 1 0 0 0 2 1 0 2 1 0 1 0 0 不平衡二叉樹及平衡因子舉例 危急 結點 危急 結點 數據結構 計算機與信息學院 姜敏 第 22頁 二叉排序樹在結點添加過程中失衡 的幾種情況 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 數據結構 計算機與信息學院 姜敏 第 23頁 二叉排序樹轉成平衡樹 失去平衡后需要進行調整的四種情況 (1) 單向右旋平衡處理 LL ?當在 左子樹上插入左結點 ,使平衡因子由 1增至 2時 (2) 單向左旋平衡處理 RR ?當在 右子樹上插入右結點 ,使平衡因子由 1增至 2時 (3) 雙向旋轉 (先左后右 )平衡處理 LR ?當在 左子樹上插入右結點 ,使平衡因子由 1增至 2時 (4) 雙向旋轉 (先右后左 )平衡處理 RL ?當在 右子樹上插入左結點 ,使平衡因子由 1增至 2時 數據結構 計算機與信息學院 姜敏 第 24頁 2 A 1 B 0 A 0 B BL BR AR h h1 h1 AR BR LL BL LL型平衡旋轉 A的 左子樹的左子樹 上插入結點，作順時針旋轉。 數據結構 計算機與信息學院 姜敏 第 25頁 RR型： A的 右子樹 的 右子樹 上插入結點，作逆時針旋轉。 2 A 1 B 0 A 0 B BR BL AL h1 BL AL RR BR h1 h 數據結構 計算機與信息學院 姜敏 第 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的 左子樹 的 右子樹 上插入結點，作兩次（逆、順）旋轉。 數據結構 計算機與信息學院 姜敏 第 27頁 4 RL型： 在 A的右子樹的左子樹上插入結點，作兩次（順、逆）旋轉。 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 數據結構 計算機與信息學院 姜敏 第 28頁 二叉排序樹在結點添加平衡化方法總結 LL RR LR RL2a1b0c0c0c0c1b1b1b2a2a2a0a0b0c0a0b0c0b0c0a0a0c0b數據結構 計算機與信息學院 姜敏 第 29頁 二叉排序樹轉成平衡樹示例 設關鍵字序列為 (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 數據結構 計算機與信息學院 姜敏 第 30頁 練習：下列情況屬于哪種失衡狀況？應該操作哪些結點？ 21207119122020016LR 12,7,9 RR 12,19 2 12 1 7 0 19 1 9 0 8 0 6 數據結構 計算機與信息學院 姜敏 第 31頁 二叉排序樹在結點添加平衡化實例 例：給定平衡二叉排序樹的輸入結點序列，請圖示結點插入過程樹結構的變化。 15， 12， 7， 19， 24， 9， 8， 5， 6 015012115012015
教學課件相關推薦
鄂ICP備17016276號-1