第九章查找課時安排

6學時教學內容：

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

要求學生掌握：

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

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

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

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

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

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

查找

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

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

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

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

數據元素同屬一個集合。ADTStaticSearchTable{

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

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

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

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

……

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

//對數值型關鍵字

#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)一、順序查找表二、有序查找表三、索引順序表以順序表或線性鏈表表示靜態查找表一、順序查找表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的數據元素。若找到，則函數值為//該元素在表中的位置，否則為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]起到了監視哨的作用。上述程序技巧上的改進，在查找表的長度>1000時，查找所需的平均時間減少一半。查找算法的平均查找長度

(AverageSearchLength)

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

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

nASL=ΣPiCi

i=1

其中:Pi為查找第i個數據元素的概率,且

Ci為查到第i個數據元素時,需要進行的比較次數.在等概率查找的情況下，順序表查找的平均查找長度為：對順序表而言，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時取極小值

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

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

mid

high

midlow

指示查找區間的下界high

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

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

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

low=1;high=ST.length;//置區間初值

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;//繼續在前半區間進行查找

else

low=mid+1;

//繼續在后半區間進行查找

}return0;

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

在n>50時，可得近似結果

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

在表中插入或刪除一個元素時,只要找到該元素所屬的塊,然后在塊內進行插入和刪除。因塊內元素的存放是任意的,所以插入和刪除時不需移動大量元素.所付出的代價是增加了存放索引表的輔助空間。（3）索引順序查找算法基本思想:①先抽出各塊中的最大關鍵字構成一個索引表；②查找分兩步進行:(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]以每塊中最大關鍵字作為該塊所有元素的索引索引表按關鍵字有序，包含兩項內容：（1）索引關鍵字----其值為該子表（塊）內的最大關鍵字（2）指針項----指示該子表的第一個記錄在表中的位置22488617132212138920334244382448605874498653索引表表最大關鍵字起始地址索引順序表的查找過程：1）由索引確定記錄所在區間（塊）；2）在順序表的某個區間（塊）內進行查找。注意：索引可以根據查找表的特點來構造。可見，

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

查找“索引表”的平均查找長度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和塊中記錄數s有關。當s取時，ASL取最小值n四、四種查找方法比較順序查找折半查找分塊查找平均查找長度最大等概率查找最小次小表的結構有序表、無序表均可僅適用于有序表表中元素逐段有序表的存儲結構順序、鏈式結構均可僅適用于順序存儲順序、鏈式均可，索引表順序存儲9.2動態查找樹表(n)(1)(n)(1)綜合上一節討論的幾種查找表的特性查找插入刪除無序順序表無序線性鏈表有序順序表有序線性鏈表(n)(n)(logn)(n)(1)(1)(n)(1)1)從查找性能看，最好情況能達(logn)，此時要求表有序；2)從插入和刪除的性能看，最好情況能達(1)，此時要求存儲結構是鏈表。可得如下結論：動態查找表的特點：表結構本身是在查找過程中動態生成的，即對于給定值key，若表中存在其關鍵字等于key的記錄，則查找成功返回。否則，插入關鍵字等于key的記錄。ADTDynamicSearchTable{抽象數據類型動態查找表的定義如下：數據對象D：數據關系R：

數據元素同屬一個集合。D是具有相同特性的數據元素的集合。每個數據元素含有類型相同的關鍵字，可唯一標識數據元素。InitDSTable(&DT)基本操作P：DestroyDSTable(&DT)SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&DT,key);TraverseDSTable(DT,Visit());}ADTDynamicSearchTable操作結果：構造一個空的動態查找表DT。InitDSTable(&DT)銷毀動態查找表DT。DestroyDSTable(&DT)初始條件：操作結果：動態查找表DT存在；若DT中存在其關鍵字等于key的數據元素，則函數值為該元素的值或在表中的位置，否則為“空”。SearchDSTable(DT,key)初始條件：操作結果：動態查找表DT存在，key為和關鍵字類型相同的給定值；動態查找表DT存在，e為待插入的數據元素；InsertDSTable(&DT,e)初始條件：操作結果：若DT中不存在其關鍵字等于e.key的數據元素，則插入e到DT。動態查找表DT存在，key為和關鍵字類型相同的給定值；DeleteDSTable(&DT,key)初始條件：操作結果：若DT中存在其關鍵字等于key的數據元素，則刪除之。動態查找表DT存在，Visit是對結點操作的應用函數；TraverseDSTable(DT,Visit())初始條件：操作結果：按某種次序對DT的每個結點調用函數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)若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；1.二叉排序樹(二叉查找樹)定義

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

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

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

通常，取二叉鏈表作為二叉排序樹的存儲結構typedefstruct

BiTNode

{

//結點結構

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)若給定值等于根結點的關鍵字，則查找成功；2)

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

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

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

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

——查找成功

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

//在根指針

T

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

//則返回指針

p

所指該數據元素的結點，并返回//函數值為TRUE;

}//SearchBST

…………

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

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

f

指向當前訪問//的結點的雙親，其初始調用值為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);

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

//在右子樹中繼續查找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根據動態查找表的定義，“插入”操作在查找不成功時才進行；3．二叉排序樹的插入算法若二叉排序樹為空樹，則新插入的結點為新的根結點；否則，新插入的結點必為一個新的葉子結點，其插入位置由查找過程得到。Insert305240Sketchoftheidea:Insert80checkif80isalreadyinthetree80>40,soitmustbetherightchildof4080Insert35checkif35isalreadyinthetree35<40,soitmustbetheleftchildof4035Insert25checkif25isalreadyinthetree25>5,soitmustbetherightchildof525Thisisthelastnodeweencounterwhensearchforthekeynumber.Itwillbetheparentofthenewnode.6/22InsertexampleStatusInsertBST(BiTree&T,ElemTypee){

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

if

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

{

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

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

(!p)T=s;

//插入s為新的根結點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)被刪除的結點是葉子；(2)被刪除的結點只有左子樹或者只有右子樹(3)被刪除的結點既有左子樹，也有右子樹。4．二叉排序樹的刪除算法可分三種情況討論：和插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結點之后，仍然保持二叉排序樹的特性。50308020908540358832(1)被刪除的結點是葉子結點例如:被刪關鍵字=2088其雙親結點中相應指針域的值改為“空”50308020908540358832(2)

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

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

//不存在關鍵字等于key的數據元素

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

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

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

else{Delete(T);returnTRUE;}

DeleteBST(T->lchild,key);

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

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

//從二叉排序樹中刪除結點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;}//轉左，然后向右到盡頭，指向被刪結點P的直接前驅S//左右子樹均不空p->data=s->data;//直接前驅替代結點pif(q!=p)q->rchild=s->lchild;//重接*q的右子樹elseq->lchild=s->lchild;

//q=p表明P的左孩子S沒有右孩子，則p的左孩子S就是p的直接前驅。重接*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)結論：

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

對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關鍵字，構造所得的不同形態的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。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構造而得的二叉排序樹，由關鍵字序列1，2，3，4，5構造而得的二叉排序樹，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2

下面討論平均情況:

不失一般性，假設長度為

n的序列中有k個關鍵字小于第一個關鍵字，則必有n-k-1個關鍵字大于第一個關鍵字,由它構造的二叉排序樹n-k-1k的平均查找長度是n和k的函數P(n,k)(0kn-1)。假設n個關鍵字可能出現的n!種排列的可能性相同，則含n個關鍵字的二叉排序樹的平均查找長度：在等概率查找的情況下，由此可類似于解差分方程，此遞歸方程有解：二、二叉平衡樹1、何謂“二叉平衡樹”？3、二叉平衡樹的查找性能分析2、如何構造“二叉平衡樹”?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樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左子樹或右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。（1）平衡因子二叉樹上任一結點的左子樹深度減去右子樹深度的差值，稱為此結點的平衡因子。（2）特點：二叉平衡樹是二叉查找樹的另一種形式，其特點為：樹中每個結點的左、右子樹深度之差的絕對值不大于1，即。例如:548254821是平衡樹不是平衡樹1100-110-10102-10010-100-2100平衡二叉樹不平衡的二叉樹構造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉技術。例如:依次插入的關鍵字為5,4,2,8,6,95424258665842向右旋轉一次先向右旋轉再向左旋轉2、構造“二叉平衡樹”426589642895向左旋轉一次繼續插入關鍵字9平衡旋轉處理只對最小不平衡子樹進行。設a為插入結點而失去平衡的最小子樹根結點的指針（即a是離插入結點最近，并且平衡因子絕對值超過1的祖先結點）。

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

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

的二叉平衡樹中所含結點的最小值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

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

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

的二叉平衡樹中所含結點的最小值

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

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

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

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

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

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-樹上，每個非終端結點可能含有：

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

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

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

keynum;

//結點中關鍵字個數，結點大小

structBTNode*parent;

//指向雙親結點的指針

KeyTypekey[m+1];

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

structBTNode*ptr[m+1];

//子樹指針向量

Record*recptr[m+1];

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

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

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

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

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

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

；從根結點出發，沿指針搜索結點和在結點內進行順序（或折半）查找

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

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

BTNode*pt;

//指向找到的結點的指針

inti;

//1..m，在結點中的關鍵字序號

inttag;

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

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

//在m階的B-樹T中查找關鍵字K,返回//查找結果(pt,i,tag)。若查找成功，則//特征值tag=1,指針pt所指結點中第i個//關鍵字等于K；否則特征值tag=0,等于//K的關鍵字應插入在指針pt所指結點//中第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);

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

插入后，該結點的關鍵字個數n<m，

不修改指針;2)

插入后，該結點的關鍵字個數n