平衡二叉排序樹(shù)-全文預(yù)覽
【正文】 的m叉樹(shù)： ⑴樹(shù)中每個(gè)結(jié)點(diǎn)至多有 m棵子樹(shù)； ⑵若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹(shù)； ⑶除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有 ?m/2? 棵子樹(shù)； ⑷所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù)：（ n， A0， K1，A1， K2， … ， Kn， An） 其中： Ki（ i=1,2,…,n ）為關(guān)鍵碼，且 KiKi+1， Ai為指向子樹(shù)根結(jié)點(diǎn)的指針 (i=0,1,…,n) ，且指針 Ai1所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均小于 Ki (i=1,2,…,n) ， An所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均大于 Kn， ?m/2? ?1≤n≤m ?1 ， n為關(guān)鍵碼的個(gè)數(shù)。但硬盤(pán)的驅(qū)動(dòng)受機(jī)械運(yùn)動(dòng)的制約，速度慢。 A S B BL BR AR B A AL S BL BR 不平衡二叉排序樹(shù)的調(diào)整 —— RR型 不平衡二叉排序樹(shù)的調(diào)整 —— RR型 30 25 20 40 60 A B 70 30 25 20 40 60 A B 70 Archild=Blchild Blchild=A 最低層失衡結(jié)點(diǎn)為 A，在結(jié)點(diǎn) A的右子樹(shù)的左子樹(shù)上插入新結(jié)點(diǎn) S后，導(dǎo)致失衡，假設(shè)在 CR下插入 S，由 A、 B、 C的平衡因子可知， CL與 CR深度相同， AL與 BR深度相同，且 AL、 BR的深度比 CL、 CR的深度大 1；為恢復(fù)平衡并保持二叉排序樹(shù)的特性，可將 B改為 C的右子，而 C原來(lái)的右子 CR改為 B的左子，然后將 A改為 C的左子， C原來(lái)的左子 CL改為 A的右子；這相當(dāng)于以 B為軸，對(duì) A做了一次順時(shí)針旋轉(zhuǎn)。 仍應(yīng)保持二叉排序樹(shù)的性質(zhì)不變。 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 1 1 1 0 0 0 0 0 0 0 0 平衡樹(shù) 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 1 1 1 0 0 0 0 0 0 0 0 2 +1 +1 +2 原平衡度為 0 危機(jī)結(jié)點(diǎn) 如何用最簡(jiǎn)單、最有效的辦法保持平衡分類(lèi)二叉樹(shù)的性質(zhì)不變？ 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1