一種高效的二叉查找樹紅黑樹

《一種高效的二叉查找樹紅黑樹》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、一種高效的二叉查找樹——紅黑樹1．紅黑樹的定義查找是計算機信息管理的最常見操作。普通的二叉查找樹的查找效率與樹的深度有關(guān)。當它的左右子樹深度相差較大時，查找效率就與單鏈表差不多。為提高查找效率，必須設(shè)法使二叉查找樹的左、右子樹的深度保持平衡。紅黑查找樹就是一種平衡的二叉查找樹。定義一棵二叉查找樹如果滿足下列性質(zhì)，則稱為紅黑樹：（1）每個結(jié)點或是紅色的，或是黑色的（增加一位表示顏色的存儲位）；（2）每個空結(jié)點NIL是黑色的；（3）如果一個結(jié)點是紅色的，則它的兒子應(yīng)是黑色的；（4）從任何一給定結(jié)點到

2、其子孫葉結(jié)點每條簡單路徑上都具有相同個數(shù)的黑結(jié)點。圖1給出了一棵紅黑樹的例子，其中黑結(jié)點用方框表示，紅結(jié)點用橢圓表示。2、例：3、推論：若一棵二叉查找樹是紅黑樹，則它的任一子樹也必為紅黑樹。4、紅黑樹的生成可以從空樹開始，通過逐步插入結(jié)點來生成一棵紅黑樹。向一棵紅黑樹T中插入一個新結(jié)點x的過程如下：先按普通二叉查找樹那樣，在T中插入結(jié)點x，并將x著為紅色。為保證紅黑樹的的性質(zhì)要求得以繼續(xù)保持，一般需隨時進行調(diào)整。具體可分為以下幾種情況：（1）若x的父結(jié)點是黑色的，則插入過程結(jié)束。（2）若x的父結(jié)

3、點是紅色的，而x的叔叔結(jié)點y是黑色的，則需按圖2或圖3方式進行調(diào)整，其中子樹α,β,γ,δ每一棵都有一個黑根。（3）若x的結(jié)點是紅色的，而x的叔叔結(jié)點y也是紅色的，則需按圖4或圖5方式進行調(diào)整。對插入結(jié)點x在其祖父結(jié)點的右子樹中的情況，不難給出調(diào)整規(guī)則。將x的祖父結(jié)點作為新的x，繼續(xù)按情況（1）、（2）、（3）處理。由于需要判定插入結(jié)點的父結(jié)點及叔叔結(jié)點的紅與黑，為便于操作，紅黑樹的結(jié)點就具有如下結(jié)構(gòu)：lchildparentdatatagrchild其中l(wèi)child、parent、rchild

4、分別是指向左兒子、父結(jié)點和右兒子的指針，tag是紅黑標志位，data是數(shù)據(jù)域2紅黑樹的查找效率為方便起見，我們把紅黑樹的葉結(jié)點（NIL）稱為外部結(jié)點，帶有關(guān)鍵字的結(jié)點稱為內(nèi)部結(jié)點。定義從某個結(jié)點x出發(fā)（不包括結(jié)點x本身）到葉結(jié)點的路徑上的黑結(jié)點個數(shù)，稱為該結(jié)點x的黑深度，記為bd（x），根結(jié)點的黑深度就是該紅黑樹的黑深度。定理1以結(jié)點x為根的子樹，至少有2bd(x)-1個內(nèi)部結(jié)點。證：對以x結(jié)點為根的子樹深度用歸納法。為方便起見，將以x為根的子樹深度記為d（x）。若d（x）=0，則x就是葉結(jié)點N

5、IL，這時該子樹的內(nèi)部結(jié)點數(shù)為0，bd(x)=0，故結(jié)論為真。設(shè)d（x）≤k-1時結(jié)論為真，考察d（x）=k的情形。由紅黑樹定義中的性質(zhì)要求3和4可知，當x為紅色時，x的子樹的黑深度為bd（x）-1；當x為黑色時，x的子樹的黑深度或為bd（x），或為bd（x）–1，而x的子樹的深度小于等于k-1，由歸納假設(shè)可知，以x為根的子樹至少包含有2bd(x)–1-1+2bd(x)–1-1+1個內(nèi)部結(jié)點。故結(jié)論成立。定理2含有n個內(nèi)部結(jié)點的紅黑樹的深度至多為2lg（n+1）。證：設(shè)紅黑樹的深度為d，根據(jù)紅黑

6、樹定義中的性質(zhì)要求3，從根到葉結(jié)點的路徑上至少有一半的黑結(jié)點，從而該樹的黑深度至少為d/2，由定理1有2d/2–1≤n故d/2≤lg（n+1），d≤2lg（n+1）由于查找操作的時間復雜性與紅黑樹的深度成正比，故對紅黑樹的查找，在最壞情況下的時間復雜性為O（lgn）。若考慮紅黑樹的動態(tài)查找特性，即在查找失敗時插入該結(jié)點，這時最壞情況是發(fā)生樹的形狀連續(xù)調(diào)整，但調(diào)整次數(shù)不會超過樹的深度，故時間復雜性仍保持為O（lgn）。綜上所述，不難發(fā)現(xiàn)，紅黑樹是一種高效的查找樹，值得推廣應(yīng)用。i:=i+1;ifA

7、.data[i]=xthen〖A.data[i]=A.data[A.last];A.last:=A.last―1〗】end;{DELETE}MEMBER,INSERT,DELETE運算有最壞情況下的復雜性為O(n)二、字典的散列實現(xiàn)1．圖示開散列(hashing)的思想,使每一個運算所需要的時間最壞情況下也為常數(shù)2．散列函數(shù)3．例functionh(x:elementtype):0..B-1;vari,sun:integer;beginsum:=0fori:=1to10dosum:=sum+or

8、d(x[i]);h:=summodBend;{h}其中集合元素x是長度為10的字符串。該散列函數(shù)利用Pascal提供的函數(shù)ord(ord?字符所對應(yīng)的整數(shù)碼)，將字符串x中的每個字符轉(zhuǎn)換為一個整數(shù)，然后將每個字符對應(yīng)的整數(shù)相加，用所得和除以B的余數(shù)作為h(x)值。顯然這個余數(shù)是0，1,…,B-1之一。4.用開散列來實現(xiàn)字典時，其數(shù)據(jù)類型可說明如下：constB=100{桶的個數(shù)}typecelltype=recordelement:elementtyoe;next;celltypeendDICT