第10章查找(編輯修改稿)
2024-08-16 07:13 本頁面
【文章內(nèi)容簡介】 est[] = {4,5,7,2,1,9,8,11,3}, x = {9}。 int n = 9, i, s。 BiTreeNode *root = NULL。 for(i = 0。 i n。 i++) Insert(amp。root, test[i])。 InTraverse(root)。 s = Search(root, x)。 if(s == 1) printf(\n數(shù)據(jù)元素 %d存在 ！ , )。 else printf(\n數(shù)據(jù)元素不存在 ！ )。 } 程序運(yùn)行建立的二叉排序樹如圖 105（ i） 所示 。 程序運(yùn)行結(jié)果如下： 1 2 3 4 5 7 8 9 11 數(shù)據(jù)元素 9存在！ 六、二叉排序樹的性能分析 一棵二叉排序樹的平均查找長度為： ?? ??miii CnnA S L11其中： ni 是每層結(jié)點(diǎn)個數(shù)； Ci 是結(jié)點(diǎn)所在層次數(shù)； m 為樹深。 當(dāng)二叉排序樹是一棵單分支退化樹時 ， 查找成功的平均查找長度和有序順序表的平均查找長度相同 ， 即為： ?????nininA S L12/)1(1成功若每個數(shù)據(jù)元素的查找概率相等，則二叉排序樹查找成功的平均查找長度為： )1(lo g)2(1 211 ???? ??? ninA S Lkii成功3 4 5 6 7 8 10 6 4 8 3 5 7 10 (a) (b) （ a） 滿二叉排序樹時， k = log2(7+1)=3，所以查找成功的平均查找長度為： 717)34221(71)2(1 11???????? ??? inA S L iki成功（ b） 左分支退化二叉排序樹時， k = n=7， 所以查找成功的平均查找長度為： 42/)17(2/)1(1?????? ??nininA S L 成功在最壞情況下，二叉排序樹的平均查找長度為 O(n)。 在一般情況下，二叉排序樹的平均查找長度為 O(log2n)。 B_樹是一種平衡多叉排序樹 。 平衡是指所有葉結(jié)點(diǎn)都在同一層上 ， 從而可避免出現(xiàn)像二叉排序樹那樣的分支退化現(xiàn)象 。 因此 B_樹的動態(tài)查找效率更高 。 B_樹中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)的最大值稱為 B_樹的階 ， 一棵 m階的 B_樹或者是一棵空樹，或者是滿足下列要求的 m叉樹： (1)樹中每個結(jié)點(diǎn)至多有 m個孩子結(jié)點(diǎn)。 (2)除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)至少有 ?m/2?個孩子結(jié)點(diǎn)（符號“ ? ?”表示上取整）。 (3)若根結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則根結(jié)點(diǎn)至少有兩個孩子結(jié)點(diǎn)； (4)每個結(jié)點(diǎn)的結(jié)構(gòu)為： n P0 K1 P1 K2 P2 … Kn Pn (5)所有葉結(jié)點(diǎn)都在同一層上。 1 50 20 41 1 72 2 1 44 3 23 30 35 1 15 1 60 3 77 80 88 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ root 一棵 4階 B_樹 1. 查找算法 在 B_樹上查找數(shù)據(jù)元素 x的方法為：將 Ki逐個進(jìn)行比較： （ 1） 若 =Ki則查找成功 。 （ 2） 若 keyK1則沿著指針 P0所指的子樹繼續(xù)查找 。 （ 3） 若 KikeyKi+1則沿著指針 Pi所指的子樹繼續(xù)查找 。 （ 4） 若 keyKn則沿著指針 Pn所指的子樹繼續(xù)查找 。 2. 插入算法 插入過程分兩步完成： （ 1） 利用查找算法找出該關(guān)鍵字的插入結(jié)點(diǎn) （ B_樹的插入結(jié)點(diǎn)一定是葉結(jié)點(diǎn) ） 。 （ 2） 判斷該結(jié)點(diǎn)是否還有空位置 ， 即判斷該結(jié)點(diǎn)是否滿足 nm1， 若該結(jié)點(diǎn)滿足 nm1， 說明該結(jié)點(diǎn)還有空位置 ， 直接把關(guān)鍵字；若該結(jié)點(diǎn)有 n=m1， 說明該結(jié)點(diǎn)已沒有空位置 ， 要插入就要分裂該結(jié)點(diǎn) 。 100 20 60 120 180 5 10 25 40 80 110 116 132 189 200 a b c 100 20 60 120 180 5 10 25 40 80 90 110 116 132 189 200 a b c (a)初始狀態(tài) (b)插入 90后的狀態(tài) 在 3階 B_樹上進(jìn)行插入操作如下圖示： 100 20 60 120 180 5 10 25 40 80 90 110 116 132 189 195 200 a b c (c) 插入 195后結(jié)點(diǎn)分裂前的狀態(tài) 100 180 20 60 5 10 25 40 80 90 a 120 195 39。 b 39。 39。 b 110 116 132 189 200 (d)插入結(jié)點(diǎn) 195后結(jié)點(diǎn)分裂的過程 39。 c 39。 39。 c 100 20 60 120 180 195 5 10 25 40 80 90 110 116 132 a b 189 200 39。 c 39。 39。 c 刪除分兩步完成： （ 1） 利用查找算法找出該關(guān)鍵字所在的結(jié)點(diǎn) 。 （ 2） 在結(jié)點(diǎn)上刪除關(guān)鍵字 ： 一種是在葉結(jié)點(diǎn)上刪除關(guān)鍵字 ， 共有以下三種情況： （ a） 假如要刪除關(guān)鍵字結(jié)點(diǎn)的關(guān)鍵字個數(shù) n大于 m/2+1， 說明刪去該關(guān)鍵字后該結(jié)點(diǎn)仍滿足 B_樹的定義，則可直接刪去該關(guān)鍵字。其過程如下圖 (b)所示 100 20 60 120 180 5 10 25 40 80 110 116 132 189 200 100 20 60 120 180 5 10 25 40 80 116 132 189 200 (a)初始狀態(tài) (b)刪去 110后的狀態(tài) （ b） 假如要刪除關(guān)鍵字結(jié)點(diǎn)的關(guān)鍵字個數(shù) n等于 m/2+1， 說明刪去該關(guān)鍵字后該結(jié)點(diǎn)將不滿足 B_樹的定義，此時若該結(jié)點(diǎn)的左（或
公司管理相關(guān)推薦
鄂ICP備17016276號-1