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

1、一種高效的二叉查找樹紅黑樹紅黑樹的定義查找是計算機信息管理的最常見操作。普通的二叉查找樹的查找效率與樹的深度有關。當它的左右子樹深度相差較大時，查找效率就與單鏈表差不多。為提高查找效率，必須設法使二叉查找樹的左、右子樹的深度保持平衡。紅黑查找樹就是一種平衡的二叉查找樹。定義一棵二叉查找樹如果滿足下列性質(zhì)，則稱為紅黑樹：每個結(jié)點或是紅色的，或是黑色的（增加一位表示顏色的存儲位）；每個空結(jié)點NIL是黑色的；如果一個結(jié)點是紅色的，則它的兒子應是黑色的；從任何一給定結(jié)點到其子孫葉結(jié)點每條簡單路徑上都具有相同個數(shù)的黑結(jié)點。圖1給出了一棵紅黑樹的例子，其中黑結(jié)點用方框表示，紅結(jié)點用橢圓表示。2、例：3、推

2、論：若一棵二叉查找樹是紅黑樹，則它的任一子樹也必為紅黑樹。4、紅黑樹的生成可以從空樹開始，通過逐步插入結(jié)點來生成一棵紅黑樹。向一棵紅黑樹T中插入一個新結(jié)點x的過程如下:先按普通二叉查找樹那樣，在T中插入結(jié)點x,并將x著為紅色。為保證紅黑樹的的性質(zhì)要求得以繼續(xù)保持，一般需隨時進行調(diào)整。具體可分為以下幾種情況：（1）若x的父結(jié)點是黑色的，則插入過程結(jié)束。（2）若x的父結(jié)點是紅色的，而x的叔叔結(jié)點y是黑色的，則需按圖2或圖3方式進行調(diào)整，其中子樹，每一棵都有一個黑根。（3）若x的結(jié)點是紅色的，而x的叔叔結(jié)點y也是紅色的，則需按圖4或圖5方式進行調(diào)整。對插入結(jié)點x在其祖父結(jié)點的右子樹中的情況，不難給出

3、調(diào)整規(guī)則。將x的祖父結(jié)點作為新的x，繼續(xù)按情況（1）、（2）、（3）處理。由于需要判定插入結(jié)點的父結(jié)點及叔叔結(jié)點的紅與黑，為便于操作，紅黑樹的結(jié)點就具有如下結(jié)構(gòu)：Ichildparentdatatagrchild其中Ichild、parent、rchild分別是指向左兒子、父結(jié)點和右兒子的指針，tag是紅黑標志位，data是數(shù)據(jù)域2紅黑樹的查找效率為方便起見，我們把紅黑樹的葉結(jié)點(NIL)稱為外部結(jié)點，帶有關鍵字的結(jié)點稱為內(nèi)部結(jié)點。定義從某個結(jié)點x出發(fā)(不包括結(jié)點x本身)到葉結(jié)點的路徑上的黑結(jié)點個數(shù)，稱為該結(jié)點x的黑深度，記為bd(X)，根結(jié)點的黑深度就是該紅黑樹的黑深度。定理1以結(jié)點x為根的

4、子樹，至少有2bd(x)-1個內(nèi)部結(jié)點。證：對以x結(jié)點為根的子樹深度用歸納法。為方便起見，將以x為根的子樹深度記為d(x)。若d(x)=0，則x就是葉結(jié)點NIL，這時該子樹的內(nèi)部結(jié)點數(shù)為0，bd(x)=0,故結(jié)論為真。設d(x)W-1時結(jié)論為真，考察d(x)=k的情形。由紅黑樹定義中的性質(zhì)要求3和4可知，當x為紅色時，x的子樹的黑深度為bd(x)-1；當x為黑色時，x的子樹的黑深度或為bd(x)，或為bd(x)-1,而x的子樹的深度小于等于k-1，由歸納假設可知，以x為根的子樹至少包含有2bd(x)-i-1+2bd(x)-i-1+1個內(nèi)部結(jié)點。故結(jié)論成立。定理2含有n個內(nèi)部結(jié)點的紅黑樹的深度至

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

6、.last;A.last:=A.last1】end;DELETEMEMBER,INSERT,DELETE運算有最壞情況下的復雜性為O(n)二、字典的散列實現(xiàn).圖示開散列(hashing)的思想，使每一個運算所需要的時間最壞情況下也為常數(shù)2散列函數(shù)3例functionh(x:elementtype):0.B-1;vari,sun:integer;beginsum:=0fori:=1to10dosum:=sum+ord(xi);h:=summodBend;h其中集合元素x是長度為10的字符串。該散列函數(shù)利用Pascal提供的函數(shù)ord(ord字符所對應的整數(shù)碼)，將字符串x中的每個字符轉(zhuǎn)換為一個整

7、數(shù)，然后將每個字符對應的整數(shù)相加，用所得和除以B的余數(shù)作為h(x)值。顯然這個余數(shù)是0，1,B-1之一。.用開散列來實現(xiàn)字典時，其數(shù)據(jù)類型可說明如下：constB=100桶的個數(shù)typecelltype=recordelement:elementtyoe;next;celltypeendDICTIONARY=array0.B-1ofcelltype;.在字典的開散列表示下，它的各個運算可實現(xiàn)如下。(1)字典初化MAKENULLprocedureMAKENULL(varA:DICTIONARY);vari:integer;beginfori:=0toB-1doAi:=nilend;MAKENUL

8、L(2)字典查詢MEMBERfunctionMEMBER(x:elementtype;A:DICTIONARY):boolean;varcurrent:Tcellentype;begincurrent:=Ah(x);whilecurrentnildoifcurrenteleent=xthenreturn(true)elsecurrent:=currentnext;return(false)end;MEMBER(3)插入操作INSERTprocedureINSERT(x:elementtype;varA:DICTIONARY);varbucket:integer;oldheader:cellty

9、pe;beginifnotMEMBER(x,A)thenbeginbucket:=h(x);oldheader:=Abucket;new(Abucket);Abucketelement:=x;Abucketnext:=oldheader;endend;INSERT插入一個新元素，是在桶頭即在桶的第一個單元前做插入，所以必須區(qū)分處理。（4）刪除操作DELETEprocedureDELETE(x:elementtype;varA:DICTIONARY);varcurrent:celltype;bucket:integer;beginbucket:=h(x)ifAbucketnilthen【ifAb

10、uckett.element=xthenAbucket:=Abuckett.nextelsecurrent:=Abucket;whilecurrentt.nextildoifcurrentt.nextt.element=xthencurrentt.next:=currentt.nextt.next;returnelsecurrent:=currentt.nextend;DELETE若要刪除的元素正好位于不帶表頭單元的表的第一個位置，則對第一個位置進行特殊處理。三、閉散列閉散列是將字典中的元素直接放在桶頭數(shù)組中，而不是用桶頭數(shù)組來存放桶鏈接表的表頭，因此閉散列表中的每一桶都只能存放集合中的一個元

11、素。采用閉散列來存放元素時，可能會發(fā)生沖突。因為桶可能已被具有相同散列值的其它元素所占據(jù)。如果發(fā)生了沖突，則可以采用重新散列技術，即使用散列函數(shù)序列h(X),h(X),.,.逐步順序地試探，直到發(fā)現(xiàn)12一個空桶為止。例h(X)(h(X)i)modB,i1,2B1,并舉書上習題P173i第7題基本運算INSERT如上，MEMBER及DELETE如何來實現(xiàn)呢？實現(xiàn)MEMBER時，按h(x)(h(x)i)modB,i1,2B1的i順序逐步檢查每一個桶，看是否有一個桶中有,如果有，則返回真。否則，若遇到一個桶，我們是否能確定閉散列h(x)(h(x)i)modB,i1,2B1到此為止呢？i答案是否定的。

12、因為，若按h(x)(h(x)i)modB,i1,2.B1遇到一個“空”桶，這i個“空”是由于“閉散列尾”還是本來有一個元素但卻被刪除了呢？為了區(qū)別，我們用constempty=;10個空格deleted=*10個*號typeDICTIONARY=array0.B-1ofelementtype;基本運算(1)字典初始化MAKENULLprocedureMAKENULL(varA:DICTIONARY);vari:integer;beginfori:=0toB-1doAi:=emptyend;MAKENULL(2)LOCATEfunctionLOCATE(x:elementtype;A:DICTI

13、ONARY):integer;varinitial,i:integer;begininitial:=h(x);i:=0;while(iB)andA(initial+i)modBx)andA(initial+i)modBempty)doi:=i+1;return(initial+i)modB)end;LOCATE(3)”MEMBERfunctionMEMBER(x:elementtype;A:DICTIONARY):boolean;beginifALOCATE(x,A)=xthenreturn(true)elsereturn(false)end;MEMBER(4)插入操作INSERTprocedureINSERT(x:elementtype;varA:DICTIONARY);varbucket:integer;beginbucket:=LOCATE(x,A);ifAbucket=emptythenAbucket:=xelseifAbucketxthenerror(tableisfull)end;INSERT(5)冊U除操作DELETEprocedureDEL