數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程（第3版）課件 第8章查找(上)

第8章查找8.1

查找的概念8.2靜態(tài)查找表8.3動(dòng)態(tài)查找表8.4哈希表查找第8章查找1/908.1查找的概念查找是對(duì)已存入計(jì)算機(jī)中的數(shù)據(jù)所進(jìn)行的一種運(yùn)算，采用何種查找方法，首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來表示“表”，即表中數(shù)據(jù)元素是按何種方式組織的。為了提高查找速度，常常用某些特殊的數(shù)據(jù)結(jié)構(gòu)來組織表，或?qū)Ρ硎孪冗M(jìn)行諸如排序這樣的運(yùn)算。因此在研究各種查找方法時(shí)，必須弄清：①數(shù)據(jù)結(jié)構(gòu)是什么？②對(duì)表中關(guān)鍵字的次序有何要求，例如，是對(duì)無序表查找還是對(duì)有序表查找？8.1查找的概念2/90若在查找的同時(shí)對(duì)表做修改運(yùn)算（如插入和刪除），合適這樣操作的表稱之為動(dòng)態(tài)查找表（既適合查找，也適合刪除和插入操作）。否則稱之為靜態(tài)查找表（適合查找，不適合刪除和插入操作）。8.1查找的概念3/90由于查找運(yùn)算的主要運(yùn)算是關(guān)鍵字的比較，所以通常把查找過程中對(duì)關(guān)鍵字執(zhí)行的平均比較次數(shù)（也稱為平均查找長(zhǎng)度）作為衡量一個(gè)查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。平均查找長(zhǎng)度ASL（AverageSearchLength）定義為：其中，n是查找表中元素的個(gè)數(shù)。pi是查找第i（1≤i≤n）個(gè)元素的概率，一般地，除特別指出外，均認(rèn)為每個(gè)元素的查找概率相等，即pi=1/n，ci是找到第i個(gè)元素所需進(jìn)行的比較次數(shù)。8.1查找的概念4/90平均查找長(zhǎng)度分為：成功查找情況下的平均查找長(zhǎng)度ASLsucc，指在表中找到指定關(guān)鍵字的元素平均所需關(guān)鍵字比較的次數(shù)。不成功查找情況下的平均查找長(zhǎng)度ASLunsucc，指在表中找不到指定關(guān)鍵字的元素平均所需關(guān)鍵字比較的次數(shù)。8.1查找的概念5/908.2靜態(tài)查找表靜態(tài)查找表采用順序存儲(chǔ)結(jié)構(gòu)，順序表是一種典型的順序存儲(chǔ)結(jié)構(gòu)，本節(jié)靜態(tài)查找表采用順序表組織方式，并假設(shè)順序表中數(shù)據(jù)元素類型的定義如下：typedefintKeyType;typedefstruct{

KeyTypekey; //存放關(guān)鍵字,KeyType為關(guān)鍵字類型

ElemTypedata; //其他數(shù)據(jù),ElemType為其他數(shù)據(jù)的類型}SqType;8.2靜態(tài)查找表6/908.2.1順序查找順序查找又稱為線性查找，是一種最簡(jiǎn)單的查找方法?；舅悸罚簭谋淼囊欢碎_始順序掃描順序表，依次將掃描到的元素關(guān)鍵字和給定值k相比較，若當(dāng)前掃描到的元素關(guān)鍵字與k相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于k的元素，則查找失敗。8.2靜態(tài)查找表7/90

【例8.1】在關(guān)鍵字序列為（3,9,1,5,8,10,6,7,2,4）的順序表采用順序查找方法查找關(guān)鍵字為6的元素。39158106724i=0第1次比較39158106724i=1第2次比較39158106724i=2第3次比較8.2靜態(tài)查找表順序查找過程如下：8/9039158106724i=3第4次比較39158106724i=4第5次比較39158106724i=5第6次比較39158106724i=6第7次比較8.2靜態(tài)查找表9/90順序查找算法如下（在順序表R[0..n-1]中查找關(guān)鍵字為k的元素，成功時(shí)返回找到的元素的邏輯序號(hào)，失敗時(shí)返回0）：intSqSearch(SqTypeR[],intn,KeyTypek)

//順序查找算法{inti=0;

while(i<n&&R[i].key!=k)

//從表頭往后找

i++;

if(i>=n)

//未找到返回0 return0;

else returni+1;

//找到后返回其邏輯序號(hào)i+1}8.2靜態(tài)查找表關(guān)鍵字比較10/90

算法分析：對(duì)于含有n個(gè)元素的順序表，元素的查找在等概率的前提下，查找成功的概率pi=1/n。

第1個(gè)元素（序號(hào)為0的元素）查找成功需比較1次

第2個(gè)元素（序號(hào)為1的元素）查找成功需比較2次

……

第n個(gè)元素（序號(hào)為n-1的元素）查找成功需比較n次

即成功找到第i（1≤i≤n）個(gè)元素所需關(guān)鍵字比較次數(shù)Ci=i，所以查找成功時(shí)的平均查找長(zhǎng)度為：8.2靜態(tài)查找表11/90任何一次不成功的查找，都需要和順序表中n個(gè)元素的關(guān)鍵字都比較一次，所以：

ASLunsucc=n。8.2靜態(tài)查找表順序查找的時(shí)間復(fù)雜度為O(n)。12/908.2.2折半查找折半查找又稱二分查找，它是一種效率較高的查找方法。折半查找要求順序表中元素是有序的，即表中元素按關(guān)鍵字有序，假設(shè)有序順序表是遞增有序的。

8.2靜態(tài)查找表13/90

基本思路：設(shè)R[low..high]是當(dāng)前的查找區(qū)間，首先確定該區(qū)間的中點(diǎn)位置mid=

(low+high)/2

；然后將待查的k值與R[mid].key比較：若R[mid].key=k，則查找成功并返回該元素的邏輯序號(hào)。若R[mid].key>k，則由表的有序性可知新的查找區(qū)間是左子表R[low..mid-1]。若R[mid].key<k，則新的查找區(qū)間是右子表R[mid+1..high]。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。8.2靜態(tài)查找表14/90

【例8.2】在有序序列（2,4,7,9,10,14,18,26,32,40）中采用折半查找方法查找關(guān)鍵字為7的元素。

0123456789low=02479101418263240high=9mid=47<100123456789low=02479101418263240high=3mid=101234567897>4low=22

479101418263240high=3mid=27=7成功！8.2靜態(tài)查找表折半查找過程如下：15/90折半查找算法如下（在有序順序表R[0..n-1]中進(jìn)行折半查找，成功時(shí)返回元素的邏輯序號(hào)，失敗時(shí)返回0）：intBinSearch(SqTypeR[],intn,KeyTypek)//拆半查找算法{intlow=0,high=n-1,mid;while(low<=high) //當(dāng)前區(qū)間存在元素時(shí)循環(huán)

{mid=(low+high)/2; //求查找區(qū)間的中間位置

if(R[mid].key==k)

returnmid+1; //找到后返回其邏輯序號(hào)mid+1

elseif(R[mid].key>k) //繼續(xù)在R[low..mid-1]中查找

high=mid-1;

else

//R[mid].key<k

low=mid+1; //繼續(xù)在R[mid+1..high]中查找

}

return0;

//若當(dāng)前查找區(qū)間沒有元素時(shí)返回0}8.2靜態(tài)查找表k與R[mid]最多兩次比較：只計(jì)1次（這樣做不影響時(shí)間復(fù)雜度）16/90

算法分析：折半查找過程構(gòu)成一個(gè)判定樹，把當(dāng)前查找區(qū)間的中間位置上的元素作為根，左子表和右子表中的元素分別作為根的左子樹和右子樹。

n=10即R[0..9]的全部查找情況：R[4]0～9R[0]0～0R[2]2～3R[1]0～3R[7]5～9R[5]5～6R[6]6～6R[8]8～9R[9]9～9查找成功查找不成功8.2靜態(tài)查找表R[3]3～317/90當(dāng)折半查找表中元素個(gè)數(shù)n較大時(shí)，可以將整個(gè)判定樹近似看成是一棵滿二叉樹，所有的葉子結(jié)點(diǎn)集中在同一層。不考慮外部結(jié)點(diǎn)，樹的高度h=

log2(n+1)

。所以有：ASLunsucc=h=

log2(n+1)

8.2靜態(tài)查找表折半查找的時(shí)間復(fù)雜度為O(log2n)。18/90

【例8.3】已知一個(gè)長(zhǎng)度為16的順序表，其元素按關(guān)鍵字有序排序，若采用折半查找法查找一個(gè)不存在的元素，則比較的次數(shù)最多是（）。

A.4

B.5 C.6

D.78.2靜態(tài)查找表h=

log2(n+1)

=h=

log217

=519/908.2.3索引查找1.基本索引查找一般地，索引存儲(chǔ)結(jié)構(gòu)需要在主數(shù)據(jù)表基礎(chǔ)上建立一個(gè)關(guān)于索引項(xiàng)的索引表。索引表的結(jié)構(gòu)為：

（索引關(guān)鍵字，該關(guān)鍵字元素在主數(shù)據(jù)表中的相對(duì)地址）其中索引關(guān)鍵字項(xiàng)有序排列。8.2靜態(tài)查找表20/908.2靜態(tài)查找表地址索引關(guān)鍵字對(duì)應(yīng)地址0k111k20┇┇┇n-1kn-1…索引表主數(shù)據(jù)表地址索引關(guān)鍵字其他數(shù)據(jù)項(xiàng)0k2…1k1…┇┇┇n-1kn-1…索引存儲(chǔ)結(jié)構(gòu)=主數(shù)據(jù)表+索引表21/90在索引存儲(chǔ)結(jié)構(gòu)中查找關(guān)鍵字為k的元素的過程：先在索引表中查找，由于索引表是按關(guān)鍵字有序排列的，所以可以采用折半查找。當(dāng)找到后通過其對(duì)應(yīng)地址直接在主數(shù)據(jù)表中找到其元素。地址索引關(guān)鍵字對(duì)應(yīng)地址0k111k20┇┇┇n-1kn-1…索引表主數(shù)據(jù)表地址索引關(guān)鍵字其他數(shù)據(jù)項(xiàng)0k2…1k1…┇┇┇n-1kn-1…8.2靜態(tài)查找表22/902.分塊查找主數(shù)據(jù)表中的數(shù)據(jù)呈現(xiàn)這樣的規(guī)律：主數(shù)據(jù)表可以分成若干塊，每一塊中的元素是無序的，但塊與塊之間元素是有序的，即前一塊中的最大關(guān)鍵字小于（或大于）后一塊中的最?。ɑ蜃畲螅╆P(guān)鍵字值。索引表中的一項(xiàng)對(duì)應(yīng)主數(shù)據(jù)表中的一塊，索引項(xiàng)由關(guān)鍵字域和鏈域組成，關(guān)鍵字域存放相應(yīng)塊的最大關(guān)鍵字，鏈域存放指向本塊第一個(gè)元素的指針，索引表按關(guān)鍵字值遞增（或遞減）順序排列。在這種索引結(jié)構(gòu)中的查找稱為分塊查找。用索引表表示這種特性8.2靜態(tài)查找表23/90首先確定待查找的元素屬于哪一塊，即查找其所在的塊。然后在塊內(nèi)查找相應(yīng)的元素。由于索引表是遞增有序的，可以對(duì)索引表進(jìn)行折半查找，當(dāng)索引表中元素個(gè)數(shù)（即分塊的塊數(shù)）較少時(shí)，也可以對(duì)索引表采用順序查找方法。在進(jìn)行塊內(nèi)查找時(shí)，由于塊內(nèi)元素?zé)o序，所以只能采用順序查找方法。8.2靜態(tài)查找表分塊查找過程分為兩步進(jìn)行：24/90例如，有一個(gè)關(guān)鍵字序列為（9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82），給出分塊查找的索引結(jié)構(gòu)和查找算法。8.2靜態(tài)查找表應(yīng)用示例25/90（9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82）9,22,12,1435,42,44,3848,60,58,4778,80,77,82整個(gè)數(shù)據(jù)是無序的可以劃分為4塊：塊之間是有序的012345678910111213141592212143542443848605847788077822203444760811821215主數(shù)據(jù)表索引表8.2靜態(tài)查找表26/90查找48：在索引表中找到關(guān)鍵字恰好大于等于48的塊：第3塊在第3塊中順序查找：邏輯序號(hào)為92203444760811821215索引表01234567891011121314159221214354244384860584778807782主數(shù)據(jù)表分塊查找實(shí)際上進(jìn)行兩次查找！性能介于順序查找和二分查找之間。8.2靜態(tài)查找表27/90

【例8.5】設(shè)數(shù)據(jù)序列中有100個(gè)元素，待查找元素的關(guān)鍵字k=47。如果在查找過程中，和k進(jìn)行比較的元素依次是27，47，36，28，47，則所采用的查找方法可能是（）。A.順序查找B.折半查找

C.分塊查找D.都不是只有分塊查找需要進(jìn)行兩次查找。第一次與47的比較是在索引表中查找，第2次與47的比較是在對(duì)應(yīng)塊（該塊中最大關(guān)鍵字為47，并且所有關(guān)鍵字均大于27）中查找。C。8.2靜態(tài)查找表28/908.3動(dòng)態(tài)查找表8.3.1二叉排序樹二叉排序樹是一種特殊的二叉樹，在一般二叉樹中，區(qū)分左子樹和右子樹，但結(jié)點(diǎn)的值是無序的。在二叉排序樹中，不僅區(qū)分左子樹和右子樹，而且整個(gè)樹的結(jié)點(diǎn)是有序的。1.二叉排序樹的定義8.3.1二叉排序樹29/90

二叉排序樹又稱二叉查找樹，它或者是一棵空樹，或者是一棵具有如下特性的非空二叉樹：若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字；若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字；左、右子樹本身又各是一棵二叉排序樹。8.3.1二叉排序樹30/90一棵二叉排序樹示例：42135768根結(jié)點(diǎn)最左下結(jié)點(diǎn)，即為關(guān)鍵字最小的結(jié)點(diǎn)根結(jié)點(diǎn)最右下結(jié)點(diǎn)，即為關(guān)鍵字最大的結(jié)點(diǎn)特點(diǎn)：中序序列：1，2，3，4，5，6，7，8中序序列是一個(gè)遞增有序序列！8.3.1二叉排序樹31/90二叉排序樹的二叉鏈存儲(chǔ)結(jié)構(gòu)的結(jié)點(diǎn)的類型聲明如下：typedefstructbstnode{KeyTypekey; //存放關(guān)鍵字

ElemTypedata; //存放其他數(shù)據(jù)

structbstnode*lchild,*rchild; //存放左、右孩子的指針}BSTNode;8.3.1二叉排序樹32/902.二叉排序樹的基本運(yùn)算二叉排序樹的基本運(yùn)算如下：創(chuàng)建二叉排序樹CreateBST(bt,str,n)：由關(guān)鍵字?jǐn)?shù)組str建立一棵二叉排序樹bt；銷毀二叉排序樹DestroyBST(bt)：釋放二叉排序樹bt中所有結(jié)點(diǎn)的內(nèi)存空間。查找結(jié)點(diǎn)BSTSearch(bt,k)：在二叉排序樹bt中查找關(guān)鍵字為k的結(jié)點(diǎn)；插入結(jié)點(diǎn)BSTInsert(bt,k)：在二叉排序樹bt中插入關(guān)鍵字為k的結(jié)點(diǎn)；輸出二叉排序樹DispBST(bt)：采用括號(hào)表示法輸出二叉排序樹bt；刪除結(jié)點(diǎn)BSTDelete(bt,k)：在二叉排序樹bt中刪除關(guān)鍵字為k的結(jié)點(diǎn)。8.3.1二叉排序樹33/903.二叉排序樹基本運(yùn)算算法實(shí)現(xiàn)（1）查找結(jié)點(diǎn)運(yùn)算算法在二叉排序樹bt中查找關(guān)鍵字為k的結(jié)點(diǎn)，找到后返回該結(jié)點(diǎn)的指針，找不到返回NULL。若當(dāng)前結(jié)點(diǎn)p的關(guān)鍵字等于k，則返回p。否則若k小于當(dāng)前結(jié)點(diǎn)的關(guān)鍵字，則在左子樹中查找。否則若k大于當(dāng)前結(jié)點(diǎn)的關(guān)鍵字，則在右子樹中查找。8.3.1二叉排序樹34/90BSTNode*BSTSearch(BSTNode*bt,KeyTypek){BSTNode*p=bt;

while(p!=NULL)

{ if(p->key==k) //找到關(guān)鍵字為k的結(jié)點(diǎn)

returnp; elseif(k<p->key)

p=p->lchild; //沿左子樹查找

else

p=p->rchild; //沿右子樹查找

}

returnNULL; //未找到時(shí)返回NULL}8.3.1二叉排序樹35/90

【例8.6】在含有27個(gè)結(jié)點(diǎn)的二叉排序樹上，查找關(guān)鍵字為35的結(jié)點(diǎn)，以下哪些是可能的關(guān)鍵字比較序列？

A.28,36,18,46,35

B.18,36,28,46,35

C.46,28,18,36,35

D.46,36,18,28,35判斷標(biāo)準(zhǔn)：在二叉排序樹中的查找路徑是原來二叉排序樹的一部分，也一定構(gòu)成一棵二叉排序樹。8.3.1二叉排序樹36/90A.28,36,18,46,35B.18,36,28,46,35C.46,28,18,36,35D.46,36,18,28,3528361818362846462818364636182635是一棵二叉排序√

ⅩⅩⅩ8.3.1二叉排序樹37/90（2）插入結(jié)點(diǎn)運(yùn)算算法先在二叉排序樹bt中查找插入新結(jié)點(diǎn)的位置，由于二叉排序樹中所有新結(jié)點(diǎn)都是作為葉子結(jié)點(diǎn)插入的，所以這里是查找插入新結(jié)點(diǎn)的雙親即f結(jié)點(diǎn)。然后建立一個(gè)關(guān)鍵字為k的結(jié)點(diǎn)p。若bt為空樹，則p結(jié)點(diǎn)作為根結(jié)點(diǎn)。若k<f->key，將p結(jié)點(diǎn)作為f結(jié)點(diǎn)的左孩子插入。若k>f->key，將p結(jié)點(diǎn)作為f結(jié)點(diǎn)的右孩子插入。8.3.1二叉排序樹38/90intBSTInsert(BSTNode*&bt,KeyTypek){BSTNode*f,*p=bt;

while(p!=NULL)

//找插入位置,即找插入新結(jié)點(diǎn)的雙親f結(jié)點(diǎn)

{if(p->key==k)

//不能插入相同的關(guān)鍵字

return0;

f=p;

//f指向p結(jié)點(diǎn)的雙親結(jié)點(diǎn)

if(k<p->key)

p=p->lchild;

//在左子樹中查找

else

p=p->rchild;

//在右子樹中查找

}

p=(BSTNode*)malloc(sizeof(BSTNode));

p->key=k; //建立一個(gè)存放關(guān)鍵字k的新結(jié)點(diǎn)

p->lchild=p->rchild=NULL; //新結(jié)點(diǎn)總是作為葉子結(jié)點(diǎn)插入的

if(bt==NULL) //原樹為空時(shí),p作為根結(jié)點(diǎn)插入

bt=p;

elseif(k<f->key)f->lchild=p; //插入p作為f的左孩子

elsef->rchild=p; //插入p作為f的右孩子

return1; //插入成功返回1}8.3.1二叉排序樹39/90（3）創(chuàng)建二叉排序樹運(yùn)算算法由包含n個(gè)關(guān)鍵字的數(shù)組a建立相應(yīng)的二叉排序樹。依次掃描a數(shù)組r的所有元素，調(diào)用BSTInsert()將其插入到二叉排序樹bt中。voidCreateBST(BSTNode*&bt,KeyTypea[],intn){bt=NULL;

//初始時(shí)bt為空樹

inti=0;

while(i<n)

{BSTInsert(bt,a[i]);//將關(guān)鍵字a[i]插入到二叉排序樹bt中

i++;

}}8.3.1二叉排序樹40/90

【例8.7】已知一組關(guān)鍵字為

（25,18,46,2,53,39,32,4,74,67,60,11）按表中的元素順序依次插入到一棵初始為空的二叉排序樹中，畫出該二叉排序樹，并求在等概率的情況下查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。8.3.1二叉排序樹41/90生成的二叉排序樹如圖所示。25182464113953327467602518462533932474676011生成的二叉排序樹8.3.1二叉排序樹解42/901825241146393253746760在等概率的情況下，查找成功的平均查找長(zhǎng)度為：8.3.1二叉排序樹43/901825241146393253746760在等概率的情況下，查找不成功的平均查找長(zhǎng)度為：8.3.1二叉排序樹44/90由n個(gè)關(guān)鍵字構(gòu)成的二叉排序樹有多一棵，如n=3：312312ASLsucc=(1+2+3)/3=2ASLsucc=(1+2*2)/3=1.67一般地，高度為h的二叉排序樹查找時(shí)間為1～n。但平均起來，由n個(gè)關(guān)鍵字構(gòu)成的二叉排序樹的查找時(shí)間復(fù)雜度為O(log2n)。8.3.1二叉排序樹45/90（4）銷毀二叉排序樹運(yùn)算算法銷毀二叉排序樹和第7章介紹的二叉樹的算法相似。voidDestroyBST(BSTNode*&bt){if(bt!=NULL)

{ DestroyBST(bt->lchild); //銷毀左子樹

DestroyBST(bt->rchild); //銷毀右子樹

free(bt); //釋放根結(jié)點(diǎn)

}}8.3.1二叉排序樹46/90（5）輸出二叉排序樹運(yùn)算算法采用括號(hào)表示法輸出二叉排序樹bt，其過程類似二叉樹的輸出。voidDispBST(BSTNode*bt){if(bt!=NULL)

{printf("%d",bt->key);

//輸出根結(jié)點(diǎn)

if(bt->lchild!=NULL||bt->rchild!=NULL)

{printf("(");

//根結(jié)點(diǎn)有左或右孩子時(shí)輸出'('

DispBST(bt->lchild);//遞歸輸出左子樹

if(bt->rchild!=NULL)//有右孩子時(shí)輸出','

printf(",");

DispBST(bt->rchild);//遞歸輸出右子樹

printf(")");

//輸出一個(gè)')'

}

}}8.3.1二叉排序樹47/90（6）刪除結(jié)點(diǎn)運(yùn)算算法在二叉排序樹bt中刪除關(guān)鍵字為k的結(jié)點(diǎn)后，仍需要保持二叉排序樹的特性。先在二叉排序樹bt中查找關(guān)鍵字為k的結(jié)點(diǎn)p，用f指向其雙親結(jié)點(diǎn)。刪除p結(jié)點(diǎn)分以下三種情況。8.3.1二叉排序樹48/90

（1）若p結(jié)點(diǎn)沒有左子樹（含p為葉子結(jié)點(diǎn)的情況），則用p結(jié)點(diǎn)的右孩子替換它。51348762p5348762刪除結(jié)點(diǎn)18.3.1二叉排序樹49/90（2）若p結(jié)點(diǎn)沒有右子樹，則用p結(jié)點(diǎn)的左孩子替換它。51348762p刪除結(jié)點(diǎn)851347628.3.1二叉排序樹50/90

（3）若p結(jié)點(diǎn)既有左子樹又有右子樹，用其左子樹中最大的結(jié)點(diǎn)替代它。通過p結(jié)點(diǎn)的左孩子q找到它的最右下結(jié)點(diǎn)q1，q1結(jié)點(diǎn)就是p結(jié)點(diǎn)左子樹中最大的結(jié)點(diǎn)，將q1結(jié)點(diǎn)值替代p結(jié)點(diǎn)值，然后將q1結(jié)點(diǎn)刪除。由于q1結(jié)點(diǎn)一定沒有有孩子，可以采用（2）的操作刪除結(jié)點(diǎn)q1。刪除結(jié)點(diǎn)551348762pqq141387628.3.1二叉排序樹51/90intBSTDelete(BSTNode*&bt,KeyTypek){BSTNode*p=bt,*f,*q,*q1,*f1;

f=NULL;

//查找刪除的p結(jié)點(diǎn)及其雙親結(jié)點(diǎn)fif(bt==NULL)return0; //空樹返回0

while(p!=NULL) //查找關(guān)鍵字為k的結(jié)點(diǎn)p及雙親f

{if(p->key==k) //找到關(guān)鍵字為k的結(jié)點(diǎn),退出循環(huán)

break;f=p; //f指向p結(jié)點(diǎn)的雙親結(jié)點(diǎn)

if(k<p->key)

p=p->lchild;

//在左子樹中查找

else

p=p->rchild;

//在右子樹中查找

}

if(p==NULL)return0; //未找到關(guān)鍵字為k的結(jié)點(diǎn),返回0查找關(guān)鍵字為k的結(jié)點(diǎn)p（被刪結(jié)點(diǎn)）及其雙親結(jié)點(diǎn)fp結(jié)點(diǎn)既可能是f的左孩子結(jié)點(diǎn)，也可能是右孩子結(jié)點(diǎn)8.3.1二叉排序樹52/90elseif(p->lchild==NULL) //被刪結(jié)點(diǎn)p沒有左子樹的情況

{if(f==NULL) //p是根結(jié)點(diǎn),則用右孩子替換它

bt=p->rchild;pp為根結(jié)點(diǎn)…………bt被刪結(jié)點(diǎn)p沒有左子樹：分為3種子情況8.3.1二叉排序樹53/90 //被刪結(jié)點(diǎn)p沒有左子樹的情況elseif(f->lchild==p)

//p是f的左孩子,則用其右孩子替換它

f->lchild=p->rchild;

elseif(f->rchild==p)

//p是f的右孩子,則用其右孩子替換它

f->rchild=p->rchild;

free(p); //釋放被刪結(jié)點(diǎn)

}fpx……p為f的左孩子fpx……p為f的右孩子8.3.1二叉排序樹54/90elseif(p->rchild==NULL) //被刪結(jié)點(diǎn)p沒有右子樹的情況

{if(f==NULL) //p是根結(jié)點(diǎn),則用左孩子替換它

bt=p->lchild;

if(f->lchild==p) //p是f的左孩子,則用其左孩子替換它

f->lchild=p->lchild;

elseif(f->rchild==p)

//p是f的右孩子,則用其左孩子替換它

f->rchild=p->lchild;

free(p); //釋放被刪結(jié)點(diǎn)}被刪結(jié)點(diǎn)p沒有右子樹與p沒有左子樹的情況對(duì)稱！8.3.1二叉排序樹55/90else

//結(jié)點(diǎn)p既有左子樹又有右子樹的情況{q=p->lchild; //q指向p結(jié)點(diǎn)的左孩子

if(q->rchild==NULL) //若q結(jié)點(diǎn)無右孩子

{p->key=q->key; //將p結(jié)點(diǎn)值用q結(jié)點(diǎn)值代替p->data=q->data;

p->lchild=q->lchild; //刪除q結(jié)點(diǎn)

free(q); //釋放q結(jié)點(diǎn)

}51pq……特殊情況查找到p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)q8.3.1二叉排序樹56/90else

//若q結(jié)點(diǎn)有右孩子{f1=q;q1=f1->rchild;

while(q1->rchild!=NULL)//查找q結(jié)點(diǎn)的最右下結(jié)點(diǎn)q1

{f1=q1; //f1指向q1結(jié)點(diǎn)的雙親結(jié)點(diǎn)

q1=q1->rchild;

}

p->key=q1->key;

//將p結(jié)點(diǎn)值用q1結(jié)點(diǎn)值代替p->data=q1->data;查找p結(jié)點(diǎn)左子樹中最大結(jié)點(diǎn)q1（及其雙親f1），結(jié)點(diǎn)值替代pqf1q18.3.1二叉排序樹57/90if(f1->lchild==q1)

//刪除q1結(jié)點(diǎn):q1是f1的左孩子

f1->lchild=q1->rchild;elseif(f1->rchild==q1)//刪除q1結(jié)點(diǎn):q1是f1的右孩子

f1->rchild=q1->lchild;

free(q1);

//釋放q1所占空間

}}return1; //刪除成功返回1}8.3動(dòng)態(tài)查找表通過q1結(jié)點(diǎn)的雙親結(jié)點(diǎn)f1來刪除結(jié)點(diǎn)q1結(jié)點(diǎn)q1一定沒有右子樹用q1的左孩子結(jié)點(diǎn)替代它58/90若一棵二叉樹中每個(gè)結(jié)點(diǎn)的左、右子樹的高度至多相差1，則稱此二叉樹為AVL樹（默認(rèn)平衡二叉樹指的是AVL樹）。二叉樹中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)平衡因子（balancdfactor，用bf表示）域。每個(gè)結(jié)點(diǎn)的平衡因子是該結(jié)點(diǎn)左子樹的高度減去右子樹的高度。從平衡因子的角度可以說，若一棵二叉樹中所有結(jié)點(diǎn)的平衡因子的絕對(duì)值小于或等于1，即平衡因子取值為1、0或-1，則該二叉樹稱為AVL樹。8.3.2平衡二叉樹(AVL)8.3.2平衡二叉樹59/90平衡二叉樹總是二叉排序樹5482是平衡樹010154821不是平衡樹012208.3.2平衡二叉樹60/90平衡二叉樹中插入新結(jié)點(diǎn)方式與二叉排序樹相似，只是插入后可能破壞了平衡二叉樹的平衡性，解決方法是調(diào)整。調(diào)整操作可歸納為下列四種情況。8.3.2平衡二叉樹AVL中插入結(jié)點(diǎn)61/90（1）LL型調(diào)整插入的結(jié)點(diǎn)8.3.2平衡二叉樹62/90

LL調(diào)整實(shí)例542LL插入關(guān)鍵字20124250008.3.2平衡二叉樹63/90（2）RR型調(diào)整插入的結(jié)點(diǎn)8.3.2平衡二叉樹64/90426589426895插入關(guān)鍵字9RR0-1-1-2

RR調(diào)整實(shí)例8.3.2平衡二叉樹65/90（3）LR型調(diào)整插入的結(jié)點(diǎn)8.3.2平衡二叉樹66/901637RL0-2-1

LR調(diào)整實(shí)例插入7調(diào)整以16為根的不平衡子樹73160008.3.2平衡二叉樹67/90（4）RL型調(diào)整插入的結(jié)點(diǎn)8.3.2平衡二叉樹68/90

RL調(diào)整實(shí)例73119168RL0101-2插入8調(diào)整以7為根的不平衡子樹8397111600000-18.3.2平衡二叉樹69/908.3.2平衡二叉樹創(chuàng)建AVL樹將關(guān)鍵字序列依次插入的一棵空AVL樹，得到一棵AVL樹。70/90

【例8.9】輸入關(guān)鍵字序列（16，3，7，11，9，26，18，14，15），給出構(gòu)造一棵AVL樹的步驟。1637160161301623-170LR70301608.3.2平衡二叉樹解71/901197316-11110-2107316119LL73119160008.3.2平衡二叉樹72/90267311916-11026-2RR73119160000260-18.3.2平衡二叉樹73/90187311916261-2180RL731191826001608.3.2平衡二叉樹74/90731191826161414101-18.3.2平衡二叉樹75/9073119182616-115142150LR731191826150140160構(gòu)造的結(jié)果AVL樹8.3.2平衡二叉樹76/908.3.2平衡二叉樹AVL樹的刪除平衡二叉樹中刪除關(guān)鍵字為k的結(jié)點(diǎn)方式與二叉排序樹刪除相似。但刪除后可能破壞平衡二叉樹的平衡性，解決方法是調(diào)整。

77/908.3.2平衡二叉樹

首先在AVL樹中查找關(guān)鍵字為k的結(jié)點(diǎn)x（假定存在這樣的結(jié)點(diǎn)并且唯一），刪除結(jié)點(diǎn)x的過程如下：（1）如果結(jié)點(diǎn)x左子樹為空，用其右孩子結(jié)點(diǎn)替換它，即直接刪除結(jié)點(diǎn)x。（2）如果結(jié)點(diǎn)x右子樹為空，用其左孩子結(jié)點(diǎn)替換它，即直接刪除結(jié)點(diǎn)x。具體步驟78/908.3.2平衡二叉樹

（3）如果結(jié)點(diǎn)x同時(shí)有左右子樹（這種情況下，結(jié)點(diǎn)x是通過值替換間接刪除的，稱為間接刪除結(jié)點(diǎn)），分為兩種情況：若結(jié)點(diǎn)x的左子樹較高，在其左子樹中找到最大結(jié)點(diǎn)q，直接刪除結(jié)點(diǎn)q，用結(jié)點(diǎn)q的值替換結(jié)點(diǎn)x的值。若結(jié)點(diǎn)x的右子樹較高，在其右子樹中找到最小結(jié)點(diǎn)q，直接刪除結(jié)點(diǎn)q，用結(jié)點(diǎn)q的值替換結(jié)點(diǎn)x的值。79/908.3.2平衡二叉樹RL-21xppR(a)pR的左子樹高：RLR