數(shù)據(jù)結(jié)構(gòu)第九章

第九章查找課時安排

6學時教學內(nèi)容：

靜態(tài)查找表(順序表,有序表,索引順序表)；動態(tài)查找表(二叉排序樹,平衡二叉樹,B-樹和B+樹)的建立和查找；哈希表的建立，查找及分析；

要求學生掌握：

1、順序查找，折半查找和索引查找的方法，并能靈活應用；2、二叉排序樹的構(gòu)造方法；3、二叉平衡樹的旋轉(zhuǎn)平衡方法；4、B-樹，B+樹和鍵樹的特點以及它們的建立過程；5、哈希表的構(gòu)造方法；6、按定義計算各種查找方法在等概率情況下查找成功時和失敗時的平均查找長度，理解哈希表在查找不成功時的平均查找長度的計算方法。教學重點及難點：

重點：各種查找方法，哈希表的構(gòu)造方法及平均查找長度的計算。難點：二叉平衡樹的旋轉(zhuǎn)平衡方法；何謂查找表？

查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。

由于“集合”中的數(shù)據(jù)元素之間存在著松散的關系，因此查找表是一種應用靈便的結(jié)構(gòu)。對查找表經(jīng)常進行的操作:1)查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2)檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3)在查找表中插入一個數(shù)據(jù)元素；4)從查找表中刪去某個數(shù)據(jù)元素。僅作查詢和檢索操作的查找表為靜態(tài)查找表。靜態(tài)查找表有時在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素,此類表為動態(tài)查找表。動態(tài)查找表查找表可分為兩類:關鍵字

用來標識一個數(shù)據(jù)元素（或記錄）的某個數(shù)據(jù)項的值，稱為關鍵字。主關鍵字若此關鍵字可唯一地標識一個記錄，則稱此關鍵字是主關鍵字；次關鍵字反之，用以識別若干記錄的關鍵字是次關鍵字。

根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的數(shù)據(jù)元素或(記錄)。

查找

若查找表中存在這樣一個記錄，則稱“查找成功”。查找結(jié)果給出整個記錄的信息，或指示該記錄在查找表中的位置；

否則稱“查找不成功”。查找結(jié)果給出“空記錄”或“空指針”。

由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。為了提高查找的效率，需要在查找表中的元素之間人為地附加某種確定的關系，換句話說，用另外一種結(jié)構(gòu)來表示查找表。如何進行查找？

查找的方法取決于查找表的結(jié)構(gòu),即表中數(shù)據(jù)元素是依何種關系組織在一起的。9.1靜態(tài)查找表9.2動態(tài)查找樹表9.3哈希表9.1靜態(tài)查找表數(shù)據(jù)對象D：數(shù)據(jù)關系R：D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類型相同的關鍵字，可唯一標識數(shù)據(jù)元素。

數(shù)據(jù)元素同屬一個集合。ADTStaticSearchTable{

Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());基本操作P：}ADTStaticSearchTable抽象數(shù)據(jù)類型靜態(tài)查找表的定義：構(gòu)造一個含n個數(shù)據(jù)元素的靜態(tài)查找表ST。

Create(&ST,n);操作結(jié)果：銷毀表ST。Destroy(&ST);初始條件：操作結(jié)果：靜態(tài)查找表ST存在；若ST中存在其關鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。

Search(ST,key);初始條件：操作結(jié)果：靜態(tài)查找表ST存在，key為和查找表中元素的關鍵字類型相同的給定值；按某種次序?qū)T的每個元素調(diào)用函數(shù)Visit()一次且僅一次，一旦Visit()失敗，則操作失敗。Traverse(ST,Visit());初始條件：操作結(jié)果：靜態(tài)查找表ST存在，Visit是對元素操作的應用函數(shù)；typedefstruct{

//數(shù)據(jù)元素存儲空間基址，建表時//按實際長度分配，0號單元留空intlength;//表的長度}SSTable;假設靜態(tài)查找表的順序存儲結(jié)構(gòu)為ElemType*elem;數(shù)據(jù)元素類型的定義為:typedefstruct{keyTypekey;//關鍵字域

……

//其它屬性域}ElemType;,TElemType;宏定義（對兩個關鍵字的比較約定）

//對數(shù)值型關鍵字

#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))

//對字符串型關鍵字

#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)一、順序查找表二、有序查找表三、索引順序表以順序表或線性鏈表表示靜態(tài)查找表一、順序查找表ST.elem（1）回顧順序表的查找過程：假設給定值e=64,要求ST.elem[k]=e,問:k=?kkkintlocation(SqListL,ElemType&e,

Status(*compare)(ElemType,ElemType)){k=1;p=L.elem;

while(k<=L.length

&&

!(*compare)(*p++,e))

k++;if(k<=L.length)returnk;

elsereturn0;}//location（2）從前往后查的算法ST.elemiST.elemi60ikey=64key=60i64intSearch_Seq(SSTableST,KeyTypekey){

//在順序表ST中順序查找其關鍵字等于//key的數(shù)據(jù)元素。若找到，則函數(shù)值為//該元素在表中的位置，否則為0。

ST.elem[0].key=key;

//“哨兵”

for(i=ST.length;ST.elem[i].key!=key;

--i);

//從后往前找

returni;

//找不到時，i為0}//Search_Seq（3）從后往前查的算法從后往前查的算法中，查找之前，把第0個元素設為查找元素key。這樣避免在查找過程中每一步都要檢測整個表是否查找完畢。ST.elem[0]起到了監(jiān)視哨的作用。上述程序技巧上的改進，在查找表的長度>1000時，查找所需的平均時間減少一半。查找算法的平均查找長度

(AverageSearchLength)

為確定記錄在表中的位置，需和給定值進行比較的關鍵字次數(shù)的期望值稱為查找算法在查找成功時的平均查找長度。

查找不成功時的比較次數(shù)為n+1。（4）分析順序查找的時間性能對于含有n個數(shù)據(jù)元素的表,查找成功時的平均查找長度為:

nASL=ΣPiCi

i=1

其中:Pi為查找第i個數(shù)據(jù)元素的概率,且

Ci為查到第i個數(shù)據(jù)元素時,需要進行的比較次數(shù).在等概率查找的情況下，順序表查找的平均查找長度為：對順序表而言，Ci取決于所查元素所處的位置：查找記錄是A[n]時,僅需比較一次;查找記錄是A[1]時,要比較n次;查找記錄是A[i]時,要比較n-i+1次.ASL=nP1+(n-1)P2+…+2Pn-1+Pn若查找概率無法事先測定，則查找過程采取的改進辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。在不等概率查找的情況下，ASLss

在

Pn≥Pn-1≥···≥P2≥P1時取極小值

上述順序查找表的查找算法簡單，但平均查找長度較大，特別不適用于表長較大的查找表。二、有序查找表

若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進行。（1）折半查找的基本思想折半查找又稱為二分查找如果查找表中的數(shù)據(jù)元素按關鍵字有序(假設遞增有序),則在查找時不必逐個順序比較,而采用跳躍的方式,先與“中間位置”的記錄關鍵字值比較,若相等則查找成功;若給定值大于“中間位置”的關鍵字值,則在后半部繼續(xù)進行折半查找;否則在前半部進行折半查找.折半查找僅適用于以順序存貯結(jié)構(gòu)組織的有序表的查找。ST.elemST.length例如:key=64的查找過程如下：lowhighmidlow

mid

high

midlow

指示查找區(qū)間的下界high

指示查找區(qū)間的上界mid=(low+high)/2（取整）（2）折半查找算法設待查元素所在區(qū)域的下界為low,上界為hig,則中間位置mid=(low+hig)DIV2若此元素關鍵字值等于給定值,則查找成功;若此元素關鍵字值大于給定值,則在區(qū)域

[mid+1，hig]進行折半查找若此關鍵字值小于給定值,則在區(qū)域

[low，mid-1]內(nèi)進行折半查找intSearch_Bin(SSTableST,KeyTypekey){

low=1;high=ST.length;//置區(qū)間初值

while(low<=high){mid=(low+high)/2;

if（EQ(key,ST.elem[mid].key))

returnmid;

//找到待查元素

elseif(LT(key,ST.elem[mid].key))

high=mid-1;//繼續(xù)在前半?yún)^(qū)間進行查找

else

low=mid+1;

//繼續(xù)在后半?yún)^(qū)間進行查找

}return0;

//順序表中不存在待查元素}//Search_Bin先看一個具體的情況，假設：n=11(3)分析折半查找的時間性能（ASL)6391425781011判定樹12233334444上述查找過程可用二叉樹（又稱為判定樹）來描述。樹中每個園結(jié)點（內(nèi)部結(jié)點）代表表中的一個記錄，園結(jié)點中的值代表該記錄在表中的位置。方形結(jié)點（外部結(jié)點）是人為增加的。查找成功時的比較次數(shù)不超過判定樹的深度。比較次數(shù)等于該路徑上內(nèi)部結(jié)點的個數(shù)。查找不成功的過程是走了從根結(jié)點到外部結(jié)點的路徑（即樹的深度）。比較次數(shù)等于該路徑上結(jié)點個數(shù)。不超過log2n」+1n個結(jié)點的判定樹的深度與n個結(jié)點的完全二叉樹的深度相同。假設n=2h-1并且查找概率相等(Pi=1/n),則判定樹的深度為h的滿二叉樹。層次為h的結(jié)點有2h-1個。則平均查找長度ASL為：

在n>50時，可得近似結(jié)果

三、索引順序表索引順序查找又稱分塊查找（1）表中數(shù)據(jù)元素的特點若把所有n個數(shù)據(jù)元素分成m塊,第一塊中任一元素的關鍵字都小于第二塊中任一元素的關鍵字,第二塊中任一元素的關鍵字都小于第三塊中的任一元素的關鍵字...,第m-1塊中任一元素的關鍵字都小于第m塊中的任一元素的關鍵字.而每一塊中元素的關鍵字不一定是有序的。（2）索引順序查找的優(yōu)點是:

在表中插入或刪除一個元素時,只要找到該元素所屬的塊,然后在塊內(nèi)進行插入和刪除。因塊內(nèi)元素的存放是任意的,所以插入和刪除時不需移動大量元素.所付出的代價是增加了存放索引表的輔助空間。（3）索引順序查找算法基本思想:①先抽出各塊中的最大關鍵字構(gòu)成一個索引表；②查找分兩步進行:(a)先對索引表進行折半查找或順序查找,確定待查記錄在哪一塊。(b)在已確定的那一塊中進行順序查找。213343851782119433740313322256178735585索引順序查找示例將17,8,21,19,31,33,22,25,43,37,40,61,78,73,55,85分為4塊:[17,8,21,19],[31,33,22,25],[43,37,40],[61,78,73,55,85]以每塊中最大關鍵字作為該塊所有元素的索引索引表按關鍵字有序，包含兩項內(nèi)容：（1）索引關鍵字----其值為該子表（塊）內(nèi)的最大關鍵字（2）指針項----指示該子表的第一個記錄在表中的位置22488617132212138920334244382448605874498653索引表表最大關鍵字起始地址索引順序表的查找過程：1）由索引確定記錄所在區(qū)間（塊）；2）在順序表的某個區(qū)間（塊）內(nèi)進行查找。注意：索引可以根據(jù)查找表的特點來構(gòu)造?？梢?，

索引順序查找的過程也是一個“縮小區(qū)間”的查找過程。索引順序查找的平均查找長度=

查找“索引表”的平均查找長度Lb

+查找“順序子表”的平均查找長度Lw（4）索引順序表查找性能分析假設長度為n的表均勻地分成b塊，每塊含有s個記錄，即b=「n/s。假定每條記錄的查找概率相等，則每塊查找的概率為1/b，塊中每個記錄查找的概率為1/s。ASL=Lb+Lw=(b+1)/2+(s+1)/2=(n/s+s)/2+1由此可見，索引順序表的平均查找長度與表長n和塊中記錄數(shù)s有關。當s取時，ASL取最小值n四、四種查找方法比較順序查找折半查找分塊查找平均查找長度最大等概率查找最小次小表的結(jié)構(gòu)有序表、無序表均可僅適用于有序表表中元素逐段有序表的存儲結(jié)構(gòu)順序、鏈式結(jié)構(gòu)均可僅適用于順序存儲順序、鏈式均可，索引表順序存儲9.2動態(tài)查找樹表(n)(1)(n)(1)綜合上一節(jié)討論的幾種查找表的特性查找插入刪除無序順序表無序線性鏈表有序順序表有序線性鏈表(n)(n)(logn)(n)(1)(1)(n)(1)1)從查找性能看，最好情況能達(logn)，此時要求表有序；2)從插入和刪除的性能看，最好情況能達(1)，此時要求存儲結(jié)構(gòu)是鏈表?？傻萌缦陆Y(jié)論：動態(tài)查找表的特點：表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的，即對于給定值key，若表中存在其關鍵字等于key的記錄，則查找成功返回。否則，插入關鍵字等于key的記錄。ADTDynamicSearchTable{抽象數(shù)據(jù)類型動態(tài)查找表的定義如下：數(shù)據(jù)對象D：數(shù)據(jù)關系R：

數(shù)據(jù)元素同屬一個集合。D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類型相同的關鍵字，可唯一標識數(shù)據(jù)元素。InitDSTable(&DT)基本操作P：DestroyDSTable(&DT)SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&DT,key);TraverseDSTable(DT,Visit());}ADTDynamicSearchTable操作結(jié)果：構(gòu)造一個空的動態(tài)查找表DT。InitDSTable(&DT)銷毀動態(tài)查找表DT。DestroyDSTable(&DT)初始條件：操作結(jié)果：動態(tài)查找表DT存在；若DT中存在其關鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。SearchDSTable(DT,key)初始條件：操作結(jié)果：動態(tài)查找表DT存在，key為和關鍵字類型相同的給定值；動態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素；InsertDSTable(&DT,e)初始條件：操作結(jié)果：若DT中不存在其關鍵字等于e.key的數(shù)據(jù)元素，則插入e到DT。動態(tài)查找表DT存在，key為和關鍵字類型相同的給定值；DeleteDSTable(&DT,key)初始條件：操作結(jié)果：若DT中存在其關鍵字等于key的數(shù)據(jù)元素，則刪除之。動態(tài)查找表DT存在，Visit是對結(jié)點操作的應用函數(shù)；TraverseDSTable(DT,Visit())初始條件：操作結(jié)果：按某種次序?qū)T的每個結(jié)點調(diào)用函數(shù)Visit()一次且至多一次。一旦Visit()失敗，則操作失敗。一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B-樹四、B+樹五、鍵樹一、二叉排序樹(二叉查找樹)1．定義2．查找算法3．插入算法4．刪除算法5．查找性能的分析TheSearchTreeADT--BinarySearchTrees【Definition】Abinarysearchtreeisabinarytree.Itmaybeempty.Ifitisnotempty,itsatisfiesthefollowingproperties:(1)Everynodehasakeywhichisaninteger,andthekeysaredistinct.(2)Thekeysinanonemptyleftsubtreemustbesmallerthanthekeyintherootofthesubtree.(3)Thekeysinanonemptyrightsubtreemustbelargerthanthekeyintherootofthesubtree.(4)Theleftandrightsubtreesarealsobinarysearchtrees.305240201512251022607080651.Definition1/22

(1)若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；1.二叉排序樹(二叉查找樹)定義

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：

(3)它的左、右子樹也都分別是二叉排序樹。

(2)若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；503080209010854035252388例如:是二叉排序樹。66不

通常，取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)typedefstruct

BiTNode

{

//結(jié)點結(jié)構(gòu)

structBiTNode*lchild,*rchild;

//左右孩子指針}BiTNode,*BiTree;TElemTypedata;2.ADTObjects:Afiniteorderedlistwithzeroormoreelements.Operations:SearchTreeMakeEmpty(SearchTreeT);PositionSearch(ElementTypeX,SearchTreeT);PositionFindMin(SearchTreeT);PositionFindMax(SearchTreeT);SearchTreeInsert(ElementTypeX,SearchTreeT);SearchTreeDelete(ElementTypeX,SearchTreeT);ElementTypeRetrieve(PositionP);2/22ADTDefinition(c++)ClassDefinition(c++)2．二叉排序樹的查找算法：1)若給定值等于根結(jié)點的關鍵字，則查找成功；2)

若給定值小于根結(jié)點的關鍵字，則繼續(xù)在左子樹上進行查找；3)若給定值大于根結(jié)點的關鍵字，則繼續(xù)在右子樹上進行查找。否則，

若二叉排序樹為空，則查找不成功；50308020908540358832例如:二叉排序樹查找關鍵字==50,505035,503040355090,50809095,從上述查找過程可見，在查找過程中，生成了一條查找路徑

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

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

——查找成功

——查找不成功算法描述如下：StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){

//在根指針

T

所指二叉排序樹中遞歸地查找其//關鍵字等于key的數(shù)據(jù)元素，若查找成功，

//則返回指針

p

所指該數(shù)據(jù)元素的結(jié)點，并返回//函數(shù)值為TRUE;

}//SearchBST

…………

否則表明查找不成功，返回//指針

p所指查找路徑上訪問的最后一個結(jié)點，//并返回函數(shù)值為FALSE,指針

f

指向當前訪問//的結(jié)點的雙親，其初始調(diào)用值為NULLif(!T)elseif(EQ(key,T->data.key))

elseif

(LT(key,T->data.key))

else{p=f;returnFALSE;}

//查找不成功{p=T;returnTRUE;}//查找成功SearchBST(T->lchild,key,T,p);

//在左子樹中繼續(xù)查找SearchBST(T->rchild,key,T,p);

//在右子樹中繼續(xù)查找30201040352523fT設key=48fTfT22pfTfTTTTfffp3.ImplementationsSearchPositionSearch(ElementTypeX,SearchTreeT){

if(T==NULL)

returnNULL;/*notfoundinanemptytree*/

if(X<T->Element)/*ifsmallerthanroot*/

returnSearch(X,T->Left);/*searchleftsubtree*/

elseif(X>T->Element)/*iflargerthanroot*/

returnSearch(X,T->Right);/*searchrightsubtree*/

else/*ifX==root*/ returnT;/*found*/}T(N)=S(N)=O(d)wheredisthedepthofXThesearetailrecursions.PositionIter_Search(ElementTypeX,SearchTreeT){

/*iterativeversionofFind*/

while(T){

if(X==T->Element)

returnT;/*found*/

if(X<T->Element)T=T->Left;/*movedownalongleftpath*/

else T=T->Right;/*movedownalongrightpath*/}/*endwhile-loop*/

returnNULL;/*notfound*/}SearchFunction(c++)FindMinPositionFindMin(SearchTreeT){

if(T==NULL)

returnNULL;/*notfoundinanemptytree*/

elseif(T->Left==NULL)returnT;/*foundleftmost*/

elsereturnFindMin(T->Left);/*keepmovingtoleft*/}

FindMaxPositionFindMax(SearchTreeT){

if(T!=NULL)

while(T->Right!=NULL) T=T->Right;/*keepmovingtofindrightmost*/

returnT;/*returnNULLortherightmost*/}

T(N)=O(d)T(N)=O(d)5/22根據(jù)動態(tài)查找表的定義，“插入”操作在查找不成功時才進行；3．二叉排序樹的插入算法若二叉排序樹為空樹，則新插入的結(jié)點為新的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子結(jié)點，其插入位置由查找過程得到。Insert305240Sketchoftheidea:Insert80checkif80isalreadyinthetree80>40,soitmustbetherightchildof4080Insert35checkif35isalreadyinthetree35<40,soitmustbetheleftchildof4035Insert25checkif25isalreadyinthetree25>5,soitmustbetherightchildof525Thisisthelastnodeweencounterwhensearchforthekeynumber.Itwillbetheparentofthenewnode.6/22InsertexampleStatusInsertBST(BiTree&T,ElemTypee){

//當二叉排序樹中不存在關鍵字等于e.key的//數(shù)據(jù)元素時，插入元素值為e的結(jié)點，并返//回TRUE;否則，不進行插入并返回FALSE

if

(!SearchBST(T,e.key,NULL,p))

{

}elsereturnFALSE;}//InsertBST……s=(BiTree)malloc(sizeof(BiTNode));

//為新結(jié)點分配空間s->data=e;s->lchild=s->rchild=NULL;if

(!p)T=s;

//插入s為新的根結(jié)點elseif(

LT(e.key,p->data.key))p->lchild=s;

//插入*s為*p的左孩子else

p->rchild=s;

//插入*s為*p的右孩子returnTRUE;

//插入成功SearchTreeInsert(ElementTypeX,SearchTreeT){if(T==NULL){/*Createandreturnaone-nodetree*/

T=malloc(sizeof(structTreeNode));

if(T==NULL)

FatalError("Outofspace!!!");

else{

T->Element=X;

T->Left=T->Right=NULL;}}/*Endcreatingaone-nodetree*/

else

/*Ifthereisatree*/

if(X<T->Element)

T->Left=Insert(X,T->Left);

else

if(X>T->Element)

T->Right=Insert(X,T->Right);

/*ElseXisinthetreealready;we'lldonothing*/

returnT;/*Donotforgetthisline!!*/

}HowwouldyouHandleduplicatedKeys?T(N)=O(d)7/22InsertFunction(c++)InsertFunction(c++)(continue)(1)被刪除的結(jié)點是葉子；(2)被刪除的結(jié)點只有左子樹或者只有右子樹(3)被刪除的結(jié)點既有左子樹，也有右子樹。4．二叉排序樹的刪除算法可分三種情況討論：和插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結(jié)點之后，仍然保持二叉排序樹的特性。50308020908540358832(1)被刪除的結(jié)點是葉子結(jié)點例如:被刪關鍵字=2088其雙親結(jié)點中相應指針域的值改為“空”50308020908540358832(2)

被刪除的結(jié)點只有左子樹或者只有右子樹其雙親結(jié)點的相應指針域的值改為“指向被刪除結(jié)點的左子樹或右子樹”。被刪關鍵字=408050308020908540358832(3)被刪除的結(jié)點既有左子樹，也有右子樹4040以其中序前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點被刪結(jié)點前驅(qū)結(jié)點被刪關鍵字=50DeleteDeletealeafnode:ResetitsparentlinktoNULL.Deleteadegree1node:Replacethenodebyitssinglechild.Deleteadegree2node:Replacethenodebythelargestoneinitsleftsubtreeorthesmallestoneinitsrightsubtree.Note:Thesekindsofnodeshavedegreeatmost1.Deletethereplacingnodefromthesubtree.〖Example〗Delete6040504555526070201030Solution1:resetleftsubtree.5552Solution2:resetrightsubtree.8/22DeleteexampleStatusDeleteBST(BiTree&T,KeyTypekey){

//若二叉排序樹T中存在其關鍵字等于key的//數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點，并返回//函數(shù)值TRUE，否則返回函數(shù)值FALSEif(!T)returnFALSE;

//不存在關鍵字等于key的數(shù)據(jù)元素

else{}}//DeleteBST算法描述如下：

……if(EQ(key,T->data.key))

//找到關鍵字等于key的數(shù)據(jù)元素elseif(LT(key,T->data.key))

else{Delete(T);returnTRUE;}

DeleteBST(T->lchild,key);

//繼續(xù)在左子樹中進行查找DeleteBST(T->rchild,key);

//繼續(xù)在右子樹中進行查找voidDelete(BiTree&p){

//從二叉排序樹中刪除結(jié)點p，重接它左子樹或右子樹if(!p->rchild){q=p;p=p->lchild;free(q);}//P只有左孩子elseif(!p->lchild){q=p;p=p->rchild;free(q);}//P只有右孩子else{}//P有左、右孩子

returnTRUE;}//Delete其中刪除操作過程如下所描述：……q=p;s=p->lchild;while(!s->rchild){q=s;s=s->rchild;}//轉(zhuǎn)左，然后向右到盡頭，指向被刪結(jié)點P的直接前驅(qū)S//左右子樹均不空p->data=s->data;//直接前驅(qū)替代結(jié)點pif(q!=p)q->rchild=s->lchild;//重接*q的右子樹elseq->lchild=s->lchild;

//q=p表明P的左孩子S沒有右孩子，則p的左孩子S就是p的直接前驅(qū)。重接*q的左子樹free(s);pqs

//右子樹為空樹則只需重接它的左子樹q=p;p=p->lchild;free(q);pp//左子樹為空樹只需重接它的右子樹q=p;p=p->rchild;free(q);ppSearchTreeDelete(ElementTypeX,SearchTreeT){PositionTmpCell;

if(T==NULL)Error("Elementnotfound");

elseif(X<T->Element)/*Goleft*/

T->Left=Delete(X,T->Left);

elseif(X>T->Element)/*Goright*/

T->Right=Delete(X,T->Right);

else

/*Foundelementtobedeleted*/

if(T->Left&&T->Right){/*Twochildren*/

/*Replacewithsmallestinrightsubtree*/

TmpCell=FindMin(T->Right); T->Element=TmpCell->Element; T->Right=Delete(TmpCell->Element,T->Right);}/*Endif*/

else{/*Oneorzerochild*/

TmpCell=T;

if(T->Left==NULL)/*Alsohandles0child*/

T=T->Right;

elseif(T->Right==NULL)T=T->Left;

free(TmpCell);}/*Endelse1or0child*/

returnT;}T(N)=O(h)wherehistheheightofthetree9/22DeleteFunction(c++)DeleteFunction(c++)(continue)DeleteFunction(c++)(continue)DeleteFunction(c++)(continue)結(jié)論：

⑴一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進行排序的過程；⑵每次插入的新結(jié)點都是二叉排序樹的葉子結(jié)點，在進行插入操作時，不必移動其它結(jié)點，僅需修改某個結(jié)點的指針由空變?yōu)榉强占纯伞＿@就相當于在一個有序序列上插入一個元素而沒有移動其它元素。這個特性告訴我們，對于需要經(jīng)常插入和刪除記錄的有序表采用二叉排序樹結(jié)構(gòu)更為合適。5．查找性能的分析

對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。4.Average-CaseAnalysisQuestion:Placenelementsinabinarysearchtree.Howhighcanthistreebe?Answer:Theheightdependsontheorderofinsertion.〖Example〗Givenelements1,2,3,4,5,6,7.Insertthemintoabinarysearchtreeintheorders:4,2,1,3,6,5,7and1,2,3,4,5,6,74567213h=22314567h=611/22由關鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹，由關鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2

下面討論平均情況:

不失一般性，假設長度為

n的序列中有k個關鍵字小于第一個關鍵字，則必有n-k-1個關鍵字大于第一個關鍵字,由它構(gòu)造的二叉排序樹n-k-1k的平均查找長度是n和k的函數(shù)P(n,k)(0kn-1)。假設n個關鍵字可能出現(xiàn)的n!種排列的可能性相同，則含n個關鍵字的二叉排序樹的平均查找長度：在等概率查找的情況下，由此可類似于解差分方程，此遞歸方程有解：二、二叉平衡樹1、何謂“二叉平衡樹”？3、二叉平衡樹的查找性能分析2、如何構(gòu)造“二叉平衡樹”?AVLTreesTarget:Speedupsearching(withinsertionanddeletion)Tool:BinarysearchtreesrootsmalllargeProblem:AlthoughTp=O(height),buttheheightcanbeasbadasO(N).13/22〖Example〗3binarysearchtreesobtainedforthemonthsoftheyearNovOctSeptMayMarJuneJulyDecAugAprFebJanJulyJuneMarMayOctSeptNovJanFebAugAprDecEnteredfromJantoDecAbalancedtreeAveragesearchtime=?3.5Averagesearchtime=?3.1Whatifthemonthsareenteredinalphabeticalorder?AST=6.514/22Adelson-Velskii-Landis(AVL)Trees(1962)【Definition】Anemptybinarytreeisheightbalanced.If

T

isanonemptybinarytreewith

TL

and

TR

asitsleftandrightsubtrees,thenTisheightbalancediff

(1)

TL

and

TR

areheightbalanced,and

(2)|hL

hR|1where

hL

and

hR

aretheheightsof

TL

and

TR,respectively.【Definition】Thebalancefactor

BF(node)=hL

hR

.InanAVLtree,

BF(node)=1,0,or1.582143778214354563217Theheightofanemptytreeisdefinedtobe–1.15/221、二叉平衡樹概念

又稱AVL樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹或右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。（1）平衡因子二叉樹上任一結(jié)點的左子樹深度減去右子樹深度的差值，稱為此結(jié)點的平衡因子。（2）特點：二叉平衡樹是二叉查找樹的另一種形式，其特點為：樹中每個結(jié)點的左、右子樹深度之差的絕對值不大于1，即。例如:548254821是平衡樹不是平衡樹1100-110-10102-10010-100-2100平衡二叉樹不平衡的二叉樹構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術。例如:依次插入的關鍵字為5,4,2,8,6,95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)2、構(gòu)造“二叉平衡樹”426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關鍵字9平衡旋轉(zhuǎn)處理只對最小不平衡子樹進行。設a為插入結(jié)點而失去平衡的最小子樹根結(jié)點的指針（即a是離插入結(jié)點最近，并且平衡因子絕對值超過1的祖先結(jié)點）。

平衡旋轉(zhuǎn)的規(guī)律如下：（1）單向右旋轉(zhuǎn)平衡處理：在*a的左子樹根結(jié)點的左子樹上插入結(jié)點。（2）單向左旋轉(zhuǎn)平衡處理：在*a的右子樹根結(jié)點的右子樹上插入結(jié)點。（3）雙向旋轉(zhuǎn)--先左后右--平衡處理：在*a的左子樹根結(jié)點的右子樹上插入結(jié)點。（4）雙向旋轉(zhuǎn)--先右后左--平衡處理：在*a的右子樹根結(jié)點的左子樹上插入結(jié)點?！糆xample〗InputthemonthsMarMar01MayMay0NovNov012May01Nov0021Mar000ThetroublemakerNovisintherightsubtree’srightsubtreeofthetroublefinderMar.HenceitiscalledanRRrotation.Ingeneral:A1B0BLBRALRRInsertionRRRotationA2B1BLBRALBLB0AALBR0AisnotnecessarilytherootofthetreeSinglerotation16/22AugMay01Nov0021Mar011Aug0AprApr0122LLRotationMay01Nov0021Aug0111Mar00Apr0Ingeneral:A1B0BRBLARLLInsertionA2B1BRBLARLLRotationB0AARBLBR017/22May01Nov0021Aug0111Mar00Apr0JanJan0112LRRotationMar01May0121Aug0101Jan00Apr0Nov0Ingeneral:A1B0BLARC0CRCLLRInsertionA2B1BLARC1CRCLORLRRotationBLARC0A1or0CRB0or1CLORDoubleRotation18/22DecJulyMar01May0121Aug0111Jan0Apr0Nov0July0Dec0FebFeb01122RLRotationJuly0Dec01Aug0121Jan0101Feb00Apr0Mar01May01211Nov0Ingeneral:A1B0BRALC0CLCRRLInsertionA2B1BRALC1CLCRORRLRotationBRALC0A0or1CLB1or0CROR19/22July0Dec01Aug0121Jan0101Feb00Apr0Mar01May01211Nov0JuneOctSeptJune01112Nov0Dec01Aug121Feb01July1Apr0Mar0May1June0Jan0Oct01211Oct0Dec01Aug121Feb01July1Apr0Mar0Nov0June0Jan0May0Sept01111Note:Severalbf’smightbechangedevenifwedon’tneedtoreconstructthetree.Anotheroptionistokeepaheightfieldforeachnode.20/22

在平衡樹上進行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進行比較的關鍵字的個數(shù)不超過平衡樹的深度。3、平衡樹的查找性能分析：問：含n個關鍵字的二叉平衡樹可能達到的最大深度是多少？n=0空樹最大深度為0n=1最大深度為1n=2最大深度為2n=4最大深度為3n=7最大深度為4先看幾個具體情況:反過來問，深度為h

的二叉平衡樹中所含結(jié)點的最小值Nh

是多少？h=0N0=0h=1h=2h=3一般情況下N1=1N2=2N3=4Nh=Nh-1+Nh-2+1利用歸納法可證得Nh=Fh+2-1而Fh≈h／5其中=（1+5）／2

因此，在二叉平衡樹上進行查找時，查找過程中和給定值進行比較的關鍵字的次數(shù)和log(n)

相當。由此推得，深度為h

的二叉平衡樹中所含結(jié)點的最小值

Nh=h+2/5-1。反之，含有n個結(jié)點的二叉平衡樹能達到的最大深度hn=log(5(n+1))-2。

三、B-樹1．定義2．查找過程3．插入操作4．刪除操作5．查找性能的分析1．B-樹的定義B-樹是一種平衡的多路查找樹，它在文件系統(tǒng)中很有用。一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：①樹中每個結(jié)點至多有m棵子樹；②若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹；（至少含1個關鍵字）③除根之外的所有非終端結(jié)點至少有m/2棵子樹。（至少含m/2-1個關鍵字）

④所有的非終端結(jié)點中包含下列信息數(shù)據(jù)(n,A0,K1,A1,K2,A2,…,Kn,An)其中：Ki(i=1,2,…,n)為關鍵字，且Ki<Ki+1(i=1,…,n-1);

Ai(i=0,…,n)為指向子樹根結(jié)點的指針，且指針Ai-1所指子樹中所有結(jié)點的關鍵字均小于Ki(i=1,…,n),An所指子樹中所有結(jié)點的關鍵字均大于Kn,

n(m/2-1≤n≤m-1)為關鍵字的個數(shù)(或n+1為子樹個數(shù))。⑤所有的葉子結(jié)點都出現(xiàn)在同一層次上，并且不帶信息(可以看作是外部結(jié)點或查找失敗的結(jié)點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針為空)。

B-Trees【Definition】AB-treeoforderMisatreewiththefollowingstructuralproperties:(1)Therootiseitheraleaforhasbetween2andMchildren.(2)Allnonleafnodes(excepttheroot)havebetweenM/2andMchildren.(3)Allleavesareatthesamedepth.AssumeeachnonrootleafalsohasbetweenM/2andMchildren.9/12如圖所示為一棵4階的B-樹，其深度為3。B-treeexampleB-treeexample在m階的B-樹上，每個非終端結(jié)點可能含有：

n個關鍵字Ki（1≤i≤n）n<m

n個指向記錄的指針Di（1≤i≤n）

n+1個指向子樹的指針Ai（0≤i≤n）多叉樹的特性typedefstructBTNode{int

keynum;

//結(jié)點中關鍵字個數(shù)，結(jié)點大小

structBTNode*parent;

//指向雙親結(jié)點的指針

KeyTypekey[m+1];

//關鍵字向量（0號單元不用）

structBTNode*ptr[m+1];

//子樹指針向量

Record*recptr[m+1];

//記錄指針向量(0號單元不用)}BTNode,*BTree;

//B-樹結(jié)點和B-樹的類型B-樹結(jié)構(gòu)的C語言描述如下:非葉結(jié)點中的多個關鍵字均自小至大有序排列，即：K1<K2<…<Kn；

Ai-1所指子樹上所有關鍵字均小于Ki；

Ai所指子樹上所有關鍵字均大于Ki；查找樹的特性平衡樹的特性

樹中所有葉子結(jié)點均不帶信息，且在樹中的同一層次上；

根結(jié)點或為葉子結(jié)點，或至少含有兩棵子樹（至少含1個關鍵字）；其余所有非葉子結(jié)點均至少含有m/2棵子樹（至少含m/2-1個關鍵字），至多含有m棵子樹（最多含m-1個關鍵字）

；從根結(jié)點出發(fā)，沿指針搜索結(jié)點和在結(jié)點內(nèi)進行順序（或折半）查找

兩個過程交叉進行(查找包含兩個操作：在B-樹中找結(jié)點、在結(jié)點中找關鍵字)。2.查找過程：若查找成功，則返回指向被查關鍵字所在結(jié)點的指針和關鍵字在結(jié)點中的位置；

若查找不成功，則返回插入位置。如圖所示為一棵4階的B-樹，其深度為3。typedefstruct{

BTNode*pt;

//指向找到的結(jié)點的指針

inti;

//1..m，在結(jié)點中的關鍵字序號

inttag;

//標志查找成功(=1)或失敗(=0)}Result;

//在B樹的查找結(jié)果類型假設返回的是如下所述結(jié)構(gòu)的記錄：ResultSearchBTree(BTreeT,KeyTypeK){

//在m階的B-樹T中查找關鍵字K,返回//查找結(jié)果(pt,i,tag)。若查找成功，則//特征值tag=1,指針pt所指結(jié)點中第i個//關鍵字等于K；否則特征值tag=0,等于//K的關鍵字應插入在指針pt所指結(jié)點//中第i個關鍵字和第i+1個關鍵字之間}//SearchBTree……p=T;q=NULL;found=FALSE;i=0;

while(p&&!found){n=p->keynum;

i=Search(p,K);

//在p->key[1..n]中查找i，p->key[i]<=K<p->key[i+1]

if(i>0&&p->key[i]==K)found=TRUE;

else{q=p;p=p->ptr[i];}//q指示p的雙親}

if(found)return

(p,i,1);//查找成功

elsereturn

(q,i,0);

//查找不成功在查找不成功之后，需進行插入。顯然，關鍵字插入的位置必定在最下層的非葉子結(jié)點，有下列幾種情況：3．插入1)

插入后，該結(jié)點的關鍵字個數(shù)n<m，

不修改指針;2)

插入后，該結(jié)點的關鍵字個數(shù)n