數(shù)據(jù)結(jié)構(gòu)與算法分析：檢索動(dòng)態(tài)樹(shù)

檢索數(shù)據(jù)結(jié)構(gòu)與算法1BST2（1）若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；二叉排序樹(shù)

二叉排序樹(shù)或者是一棵空樹(shù)；或者是具有如下特性的二叉樹(shù)：（3）它的左、右子樹(shù)也都分別是二叉排序樹(shù)。（2）若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；3二叉排序樹(shù)的查找算法1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹(shù)上進(jìn)行查找；3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹(shù)上進(jìn)行查找。否則，若二叉排序樹(shù)為空，則查找不成功；450308020908540358832例如:二叉排序樹(shù)查找關(guān)鍵字==50,505035,503040355090,50809095,5從上述查找過(guò)程可見(jiàn)，在查找過(guò)程中，生成了一條查找路徑：

從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn);或者

從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹(shù)為止。

——查找成功

——查找不成功6根據(jù)動(dòng)態(tài)查找表的定義，“插入”操作在查找不成功時(shí)才進(jìn)行；二叉排序樹(shù)的插入算法若二叉排序樹(shù)為空樹(shù)，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置由查找過(guò)程得到。7（1）被刪除的結(jié)點(diǎn)是葉子；（2）被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)；（3）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)。二叉排序樹(shù)的刪除算法可分三種情況討論：和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹(shù)的特性。8（1）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空”（2）被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)”。（3）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)9BST查找性能的分析

對(duì)于每一棵特定的二叉排序樹(shù)，均可按照平均查找長(zhǎng)度的定義來(lái)求它的ASL值，顯然，由值相同的n個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹(shù)的平均查找長(zhǎng)度的值不同，甚至可能差別很大。10由關(guān)鍵字序列

3，1，2，5，4構(gòu)造而得的二叉排序樹(shù)，由關(guān)鍵字序列

1，2，3，4，5構(gòu)造而得的二叉排序樹(shù)，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.211

下面討論平均情況:

不失一般性，假設(shè)長(zhǎng)度為

n

的序列中有k

個(gè)關(guān)鍵字小于第一個(gè)關(guān)鍵字，則必有n-k-1

個(gè)關(guān)鍵字大于第一個(gè)關(guān)鍵字,由它構(gòu)造的二叉排序樹(shù)：n-k-1k的平均查找長(zhǎng)度是n

和k的函數(shù)P(n,k)(0kn-1)。12

假設(shè)n個(gè)關(guān)鍵字可能出現(xiàn)的n!種排列的可能性相同，則含n個(gè)關(guān)鍵字的二叉排序樹(shù)的平均查找長(zhǎng)度：在等概率查找的情況下，1314由此可類似于解差分方程，此遞歸方程有解：15AVL16平衡二叉樹(shù)（AVL）AVL樹(shù)定義 它或者是一棵空二叉樹(shù)，或者是具有下列特性的二叉樹(shù)：它的左子樹(shù)和右子樹(shù)的深度之差的絕對(duì)值不大于1，且左、右子樹(shù)也是平衡二叉樹(shù)結(jié)點(diǎn)的平衡因子 二叉樹(shù)中某一結(jié)點(diǎn)的左子樹(shù)的深度與右子樹(shù)的深度之差17例：ABDCFEG–1+1000–1–1平衡二叉樹(shù)ABDCFEG–1+2+100–2–2–1HI0不平衡的二叉樹(shù)可以證明AVL樹(shù)的深度和logn同數(shù)量級(jí)平衡二叉樹(shù)（AVL）18BST的平衡旋轉(zhuǎn)圖例ABARBRBLBAARBRBLABBRBLALBABRBLALABARCRBLCCLCBARCRBLACLABALCRBRCCLCABRCRALBCL19舉例:構(gòu)建AVL樹(shù)輸入關(guān)鍵碼序列（13，24，37，90，53）(a)130(b)1324-10(c)1324370–2–1(d)243713000(e)1(f)243713-2-2090530(g)2437135390539037(h)24130000-120舉例:構(gòu)建AVL樹(shù)(續(xù))輸入關(guān)鍵碼序列（13，24，37，90，53，95）539037241300-1-1-29502437135390955390372413001-1-2700243713539070輸入關(guān)鍵碼序列（13，24，37，90，53，70）21舉例:構(gòu)建AVL樹(shù)(續(xù))輸入關(guān)鍵碼序列（13，24，37，90，53，40）53903724130-101-240024401337539053903724130111-2300243013375390輸入關(guān)鍵碼序列（13，24，37，90，53，30）22平衡樹(shù)結(jié)構(gòu)的方法單旋轉(zhuǎn)額外的結(jié)點(diǎn)是S左子女的左子女額外的結(jié)點(diǎn)是S右子女的右子女雙旋轉(zhuǎn)額外的結(jié)點(diǎn)是S左子女的右子女額外的結(jié)點(diǎn)是S右子女的左子女旋轉(zhuǎn)操作的正確性容易由保持BST樹(shù)的特性證明在經(jīng)過(guò)平衡處理后，新平衡樹(shù)的深度與插入之前的子樹(shù)相同。因此當(dāng)AVL樹(shù)因插入結(jié)點(diǎn)而失去平衡時(shí)，僅需對(duì)最小不平衡子樹(shù)進(jìn)行平衡旋轉(zhuǎn)處理即可23

在平衡樹(shù)上進(jìn)行查找的過(guò)程和二叉排序樹(shù)相同，因此，查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過(guò)平衡樹(shù)的深度。平衡樹(shù)的查找性能分析問(wèn)：含n

個(gè)關(guān)鍵字的二叉平衡樹(shù)可能達(dá)到的最大深度是多少？24因此，在二叉平衡樹(shù)上進(jìn)行查找時(shí)，查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)和

log(n)

相當(dāng)。由此推得，深度為

h的二叉平衡樹(shù)中所含結(jié)點(diǎn)的最小值Nh=h+2/5-1。反之，含有n

個(gè)結(jié)點(diǎn)的二叉平衡樹(shù)能達(dá)到的最大深度hn=log(5(n+1))-2。25課堂練習(xí)已知8個(gè)元素(34,76,45,18,26,54,92,65),按照依次插入結(jié)點(diǎn)的方法生成一棵AVL樹(shù).請(qǐng)下課時(shí)，提交你的練習(xí)結(jié)果給我，謝謝。并請(qǐng)寫(xiě)好你的學(xué)號(hào)和姓名。26三、B-樹(shù)1．定義2．查找過(guò)程3．插入操作4．刪除操作5．查找性能的分析271．B-樹(shù)的定義B-樹(shù)是一種平衡

的多路

查找

樹(shù)：28

在

m

階的B-樹(shù)上，每個(gè)非終端結(jié)點(diǎn)可能含有：

n

個(gè)關(guān)鍵字Ki（1≤i≤n）n<m

n

個(gè)指向記錄的指針Di（1≤i≤n）

n+1

個(gè)指向子樹(shù)的指針Ai（0≤i≤n）多叉樹(shù)的特性29非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字均自小至大有序排列，即：K1<K2<…<Kn

；

Ai-1所指子樹(shù)上所有關(guān)鍵字均小于Ki

；

Ai所指子樹(shù)上所有關(guān)鍵字均大于Ki

；查找樹(shù)的特性30平衡樹(shù)的特性樹(shù)中所有葉子結(jié)點(diǎn)均不帶信息，且在樹(shù)中的同一層次上；根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹(shù)；其余所有非葉結(jié)點(diǎn)均至少含有m/2棵子樹(shù)，至多含有m

棵子樹(shù)；31從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找兩個(gè)過(guò)程交叉進(jìn)行。2.查找過(guò)程：若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置；若查找不成功，則返回插入位置。32在查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點(diǎn)，有下列幾種情況：3．插入1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n<m，

不修改指針;332）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)n=m，

則需進(jìn)行“結(jié)點(diǎn)分裂”，令s=m/2，

在原結(jié)點(diǎn)中保留（A0，K1，……，Ks-1，As-1）；建新結(jié)點(diǎn)（As，Ks+1，……，Kn，An）；

將（Ks，p）插入雙親結(jié)點(diǎn)；3）若雙親為空，則建新的根結(jié)點(diǎn)。34例如:下列為3階B-樹(shù)502040

80插入關(guān)鍵字=60,

608090,60809090

50806030,

40203050808030

5035

和插入的考慮相反，首先必須找到待刪關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不能小于m/2-1，否則，要從其左(或右)兄弟結(jié)點(diǎn)“借調(diào)”關(guān)鍵字，若其左和右兄弟結(jié)點(diǎn)均無(wú)關(guān)鍵字可借(結(jié)點(diǎn)中只有最少量的關(guān)鍵字)，則必須進(jìn)行結(jié)點(diǎn)的“合并”。4．刪除36

在B-樹(shù)中進(jìn)行查找時(shí)，其查找時(shí)間主要花費(fèi)在搜索結(jié)點(diǎn)（訪問(wèn)外存）上，即主要取決于B-樹(shù)的深度。5．查找性能的分析37在含N

個(gè)關(guān)鍵字的B-樹(shù)上進(jìn)行一次查找，需訪問(wèn)的結(jié)點(diǎn)個(gè)數(shù)不超過(guò)

logm/2((N+1)/2)+1結(jié)論：38是B-樹(shù)的一種變型四、B+樹(shù)391．B+樹(shù)的結(jié)構(gòu)特點(diǎn)：※每個(gè)葉子結(jié)點(diǎn)中含有

n

個(gè)關(guān)鍵字和n

個(gè)指向記錄的指針；并且，所有葉子結(jié)點(diǎn)彼此相鏈接構(gòu)成一個(gè)有序鏈表，其頭指針指向含最小關(guān)鍵字的結(jié)點(diǎn)；40※每個(gè)非葉結(jié)點(diǎn)中的關(guān)鍵字Ki

即為其相應(yīng)指針Ai所指子樹(shù)中關(guān)鍵字的最大值；※所有葉子結(jié)點(diǎn)都處在同一層次上，每個(gè)葉子結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)均介于m/2和m之間。412．查找過(guò)程

※在B+樹(shù)上，既可以進(jìn)行縮小范圍的查找，也可以進(jìn)行順序查找；

※在進(jìn)行縮小范圍的查找時(shí)，不管成功與否，都必須查到葉子結(jié)點(diǎn)才能結(jié)束；

※若在結(jié)點(diǎn)內(nèi)查找時(shí)，給定值≤Ki，則應(yīng)繼續(xù)在Ai所指子樹(shù)中進(jìn)行查找。423．插入和刪除的操作類似于B-樹(shù)進(jìn)行，即必要時(shí)，也需要進(jìn)行結(jié)點(diǎn)的“分裂”或“歸并”。43

5096

155062

78

96

717884

89

96

566220264350

3815sqroot44五、鍵樹(shù)1.

鍵樹(shù)的結(jié)構(gòu)特點(diǎn)2.

.雙鏈樹(shù)3.Trie樹(shù)451.

鍵樹(shù)的結(jié)構(gòu)特點(diǎn)：

※關(guān)鍵字中的各個(gè)符號(hào)分布在從根結(jié)點(diǎn)到葉的路徑上，葉結(jié)點(diǎn)內(nèi)的符號(hào)為“結(jié)束”的標(biāo)志符。因此，鍵樹(shù)的深度和關(guān)鍵字集合的大小無(wú)關(guān)；

※鍵樹(shù)被約定為是一棵有序樹(shù)，即同一層中兄弟結(jié)點(diǎn)之間依所含符號(hào)自左至右有序，并約定結(jié)束符‘$’小于任何其它符號(hào)。46HAD$S$VE$E$R$E$IGH$S$例如:表示關(guān)鍵字集合{HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS}472.雙鏈樹(shù)—以二叉鏈表作存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的鍵樹(shù)typedef

enum{LEAF,

BRANCH}NodeKind;

//兩種結(jié)點(diǎn)：{葉子和

分支}結(jié)點(diǎn)結(jié)構(gòu):first

symbol

next分支結(jié)點(diǎn)infoptr

symbol

next葉子結(jié)點(diǎn)指向孩子結(jié)點(diǎn)的指針指向兄弟結(jié)點(diǎn)的指針指向記錄的指針48HAD$HADE$R$$ES$GH$IHEHERHEREHIGHHIS…T葉子結(jié)點(diǎn)分支結(jié)點(diǎn)含關(guān)鍵字的記錄49在雙鏈樹(shù)中查找記錄的過(guò)程:假設(shè):T為指向雙鏈樹(shù)根結(jié)點(diǎn)的指針，

K.ch[0..K.num-1]

為待查關(guān)鍵字

(給定值)。則查找過(guò)程中的基本操作為進(jìn)行下列比較:

K.ch[i]=?p->symbol

其中:p指向雙鏈樹(shù)中某個(gè)結(jié)點(diǎn)，

0≤i≤K.num-1503.Trie樹(shù)—以多重鏈表作存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的鍵樹(shù)結(jié)點(diǎn)結(jié)構(gòu):分支結(jié)點(diǎn)葉子結(jié)點(diǎn)