北京師范大學(xué)數(shù)據(jù)結(jié)構(gòu)教學(xué)資料-第7章-搜索結(jié)構(gòu)

靜態(tài)搜索表二叉搜索樹AVL樹散列第七章搜索結(jié)構(gòu)1精選PPT搜索(Search)的概念靜態(tài)搜索表所謂搜索，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對(duì)象。搜索的結(jié)果通常有兩種可能：搜索成功，即找到滿足條件的數(shù)據(jù)對(duì)象。這時(shí)，作為結(jié)果，可報(bào)告該對(duì)象在結(jié)構(gòu)中的位置,還可給出該對(duì)象中的具體信息。搜索不成功，或搜索失敗。作為結(jié)果，應(yīng)報(bào)告一些信息,如失敗標(biāo)志、位置等。

2精選PPT通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對(duì)象(或記錄)組成。在每個(gè)對(duì)象中有若干屬性，其中有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對(duì)象。稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實(shí)際應(yīng)用時(shí)，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。實(shí)施搜索時(shí)有兩種不同的環(huán)境。靜態(tài)環(huán)境，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。靜態(tài)搜索表

3精選PPT動(dòng)態(tài)環(huán)境，為保持較高的搜索效率,搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動(dòng)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。

動(dòng)態(tài)搜索表在靜態(tài)搜索表中，數(shù)據(jù)元素存放于數(shù)組中，利用數(shù)組元素的下標(biāo)作為數(shù)據(jù)元素的存放地址。搜索算法根據(jù)給定值k，在數(shù)組中進(jìn)行搜索。直到找到k在數(shù)組中的存放位置或可確定在數(shù)組中找不到

k為止。

靜態(tài)搜索表4精選PPT數(shù)據(jù)表與搜索表的類定義

#include<iostream.h>#include<assert.h>constintdefaultSize=100;template<classE,classK>classdataList; //數(shù)據(jù)表類的前視定義template<classE,classK>classdataNode{ //數(shù)據(jù)表中結(jié)點(diǎn)類的定義friendclassdataList<E,K>; //聲明其友元類為dataListpublic:5精選PPT

dataNode(constKx):key(x){} //構(gòu)造函數(shù)

KgetKey()const{returnkey;} //讀取關(guān)鍵碼

voidsetKey(Kx){key=x;} //修改關(guān)鍵碼private:

Kkey; //關(guān)鍵碼域

E

other; //其他域（視問題而定）};template<classE,classK>classdataList{ //數(shù)據(jù)表類定義public:6精選PPT

dataList(intsz=defaultSize)

:ArraySize(sz),CuurentSize(0){

Element=newdataNode<E,K>[sz];

assert(Element!=NULL);}

dataList(dataList<E,K>&R);//復(fù)制構(gòu)造函數(shù)

virtual～dataList(){delete[]Element;}

//析構(gòu)函數(shù)

virtualintLength(){returnCurrentSize;}

//求表的長度

virtualKgetKey(inti)const{ //提取第

i（1開始）元素值

7精選PPTassert(i>0||i<=CurrentSize);returnElement[i-1].key;}virtualvoidsetKey(Kx,inti){ //修改第i（1開始）元素值

assert(i>0||i<=CurrentSize);

Element[i-1].key=x;} virtualintSeqSearch(constKx)const; //搜索

virtualboolInsert(E&e1); //插入

virtualboolRemove(K

x,E&e1); //刪除friendostream&operator<<(ostream&out,constdataList<E,K>&OutList);//輸出8精選PPTfriendistream&operator>>(istream&in,

dataList<E,K>&InList);//輸入protected:

dataNode<E,K>*Element; //數(shù)據(jù)表存儲(chǔ)數(shù)組

intArraySize,CurrentSize; //數(shù)組最大長度和當(dāng)前長度};template<classE,classK>booldataList<E,K>::Insert(E&e1){//在dataList的尾部插入新元素,若插入失敗函數(shù)返//回false,否則返回true.9精選PPTif(CurrentSize==ArraySize)returnfalse;

Element[CurrentSize]=e1; //插入在尾端

CurrentSize++;returntrue;};template<classE,classK>booldataList<E,K>::Remove(Kx,E&e1){//在dataList中刪除關(guān)鍵碼為x的元素,通過e1返回。//用尾元素填補(bǔ)被刪除元素。

if(CurrentSize==0)returnfalse;for(inti==0;i<CurrentSize&&

Element[i]!=x;i++); //在表中順序?qū)ふ?0精選PPTif(i==CurrentSize)returnfalse; //未找到

e1=Element[i].other; //找到,保存被刪元素的值

Element[i]=Element[CurrentSize-1];//填補(bǔ)

CurrentSize--;returntrue;};template<classE,classK>ostream&operator<<(ostream&out,constdataList<E,K>&OutList){

out<<“存儲(chǔ)數(shù)組大小”<<endl;數(shù)據(jù)表類的友元函數(shù)

11精選PPTfor(inti=1;i<=OutList.CurrentSize;i++)

out<<OutList.Element[i-1]<<‘’;

out<<endl; //輸出表的所有表項(xiàng)到out

out<<“數(shù)組當(dāng)前長度:”<<

OutList.CurrentSize<<endl;//輸出表的當(dāng)前長度到out returnout;};template<classE,classK>istream&operator>>(istream&in,

dataList<E,K>&InList){ 12精選PPTcout<<“輸入存儲(chǔ)數(shù)組當(dāng)前長度:”;

in>>InList.CurrentSize; //從in輸入表的當(dāng)前長度

cout<<“輸入數(shù)組元素的值:\n”;for(inti=1;i<=InList.CurrentSize;i++){

//從in輸入表的全部表項(xiàng)

cout<<“元素”<<i<<“:”;

in>>InList.Element[i-1];}returnin;};13精選PPT順序搜索主要用于在線性表中搜索。設(shè)若表中有CurrentSize個(gè)元素，則順序搜索從表的先端開始，順序用各元素的關(guān)鍵碼與給定值x進(jìn)行比較若找到與其值相等的元素，則搜索成功，給出該元素在表中的位置。若整個(gè)表都已檢測(cè)完仍未找到關(guān)鍵碼與x相等的元素，則搜索失敗。給出失敗信息。順序搜索（SequentialSearch）

14精選PPT一般的順序搜索算法在第二章已經(jīng)討論過，本章介紹一種使用“監(jiān)視哨”的順序搜索方法。設(shè)在數(shù)據(jù)表dataList中順序搜索關(guān)鍵碼與給定值x相等的數(shù)據(jù)元素，要求數(shù)據(jù)元素在表中從下標(biāo)0開始存放,下標(biāo)為CurrentSize的元素作為控制搜索過程自動(dòng)結(jié)束的“監(jiān)視哨”使用。若搜索成功，則函數(shù)返回該元素在表中序號(hào)Location（比下標(biāo)大1）,若搜索失敗，則函數(shù)返回CurrentSize+1。15精選PPT使用監(jiān)視哨的順序搜索算法

template<classE,classK>intdataList<E,K>::SeqSearch(constKx)const{

Element[CurrentSize].key=x; inti=0; //將x設(shè)置為監(jiān)視哨

while(Element[i].key!=x)i++; //從前向后順序搜索

returni+1;};constintSize=10;main(){16精選PPTdataList<int>L1(Size); //定義int型搜索表L1intTarget;intLoc;cin>>L1;cout<<L1; //輸入L1

cout<<“Searchforainteger:”;cin>>Target; //輸入要搜索的數(shù)據(jù)

if((Location=L1.Seqsearch(Target))!=

L1.Length()) cout<<“找到待查元素位置在：”<<Loc+1

<<endl; //搜索成功

elsecout<<“沒有找到待查元素\n”;

//搜索不成功};17精選PPT設(shè)數(shù)據(jù)表中有n

個(gè)元素，搜索第i

個(gè)元素的概率為pi，搜索到第i

個(gè)元素所需比較次數(shù)為ci，則搜索成功的平均搜索長度:在順序搜索并設(shè)置“監(jiān)視哨”情形：

ci=i+1,i=0,1,,n-1，因此順序搜索的平均搜索長度18精選PPT一般表中各個(gè)元素的搜索概率不同，如果按搜索概率的高低排列表中的元素，從有序順序表的情況可知，能夠得到高的平均搜索長度。在等概率情形，pi=1/n,i=1,2,,n。搜索成功的平均搜索長度為：在搜索不成功情形，ASLunsucc

=n+1。19精選PPT采用遞歸方法搜索值為x的元素，每遞歸一層就向待查元素逼近一個(gè)位置，直到到達(dá)該元素。假設(shè)待查元素在第i（1≤i≤n）個(gè)位置，則算法遞歸深度達(dá)i（1～i）。102030405060i=1搜索

30102030405060i=2102030405060i=3遞歸順序搜索的遞歸算法20精選PPT順序搜索的遞歸算法template<classE,classK>intdataList<E,K>::SeqSearch(constKx,

intloc)const{//在數(shù)據(jù)表Element[1..n]中搜索其關(guān)鍵碼與給定值//匹配的對(duì)象,函數(shù)返回其表中位置。參數(shù)loc是在//表中開始搜索位置

if(loc>CurrentSize)return0;//搜索失敗

elseif(Element[loc-1].key==x)returnloc;

//搜索成功

elsereturnSearch(x,loc+1);//遞歸搜索};21精選PPT#include<iostream.h>#include“SeqList.h”constintdefaultSize=50;template<classE,classK>class

SortedList:publicSeqList{public:

intSearch(Kk1)const; //搜索

voidInsert(constKk1,E&e1); //插入

boolRemove(constK

k1,E&e1); //刪除};有序順序表的類定義22精選PPT基于有序順序表的順序搜索算法template<classE,classK>intSortedList<E,K>::Search(Kk1)const{//順序搜索關(guān)鍵碼為x的數(shù)據(jù)對(duì)象

for(inti=1;i<=n;i++)

if(data[i-1]==k1)returni;//成功

elseif(data[i-1]>k1)break;return0;

//順序搜索失敗,返回失敗信息};算法中的“==”和“>”都是重載函數(shù)，在定義E時(shí)定義它們的實(shí)現(xiàn)。23精選PPT有序順序表順序搜索的時(shí)間代價(jià)衡量一個(gè)搜索算法的時(shí)間效率的標(biāo)準(zhǔn)是：在搜索過程中關(guān)鍵碼平均比較次數(shù)，也稱為平均搜索長度ASL(AverageSearchLength)，通常它是字典中元素總數(shù)n的函數(shù)。設(shè)搜索第i

個(gè)元素的概率為pi,搜索到第i

個(gè)元素所需比較次數(shù)為ci,則搜索成功的平均搜索長度:24精選PPT在順序搜索情形，搜索第i(1≤i≤n)個(gè)元素需要比較i

次，假定按等概率搜索各元素：這與一般順序表情形相同。但搜索不成功時(shí)不需一直比較到表尾，只要發(fā)現(xiàn)下一個(gè)元素的值比給定值大，就可斷定搜索不成功。設(shè)一個(gè)有n

個(gè)表項(xiàng)的表，查找失敗的位置有n+1個(gè)，可以用判定樹加以描述。搜索成功時(shí)停在內(nèi)結(jié)點(diǎn)，搜索失敗時(shí)停在外結(jié)點(diǎn)。25精選PPT例如，有序順序表(10,20,30,40,50,60)的順序搜索的分析（使用判定樹）105060======203040<<<<<<>>>>>>26精選PPT判定樹是一種擴(kuò)充二叉樹。內(nèi)結(jié)點(diǎn)代表順序表中已有的元素，外結(jié)點(diǎn)代表失敗結(jié)點(diǎn)，它表示在兩個(gè)相鄰已有元素值之間的值。假定表中所有失敗位置的搜索概率相同，則搜索不成功的平均搜索長度：時(shí)間代價(jià)為O(n)。為了加速搜索，在有序順序表的情形，可以采用折半搜索，它也稱二分搜索，時(shí)間代價(jià)可減到O(log2n)。27精選PPT基于有序順序表的折半搜索設(shè)n個(gè)元素存放在一個(gè)有序順序表中。折半搜索時(shí),先求位于搜索區(qū)間正中的元素的下標(biāo)mid，用其關(guān)鍵碼與給定值x比較:

data[mid].key==x，搜索成功；

data[mid].key>x，把搜索區(qū)間縮小到表的前半部分，繼續(xù)折半搜索；

data[mid].key<x，把搜索區(qū)間縮小到表的后半部分，繼續(xù)折半搜索。如果搜索區(qū)間已縮小到一個(gè)對(duì)象，仍未找到想要搜索的對(duì)象，則搜索失敗。28精選PPT搜索成功的例子-101346810126012345678搜索給定值lowmidhigh66810125678lowmidhigh665lowmidhigh629精選PPT搜索失敗的例子-101346810125012345678搜索給定值lowmidhigh56810125678lowmidhigh655lowmidhigh530精選PPTtemplate<classE,classK>intSortedList<E,K>::BinarySearch(Kk1,

const

intlow,

const

inthigh)const{//折半搜索的遞歸算法，用到E的重載操作“<”和“>”

intmid=0; //元素序號(hào)從1開始

if(low<=high){

mid=(low+high)/2;

if(data[mid-1]<k1)//元素序號(hào)與下標(biāo)差一

mid=BinarySearch(k1,mid+1,high);

elseif(data[mid-1]>k1) mid=BinarySearch(k1,low,mid-1);}returnmid;};31精選PPTtemplate<classE,classK>intSortedList<E,K>::BinarySearch(Kk1)const{

//折半搜索的迭代算法，用到E的重載操作“<”和“>”

inthigh=n,low=1,mid;//元素序號(hào)從1開始

while(low<=high){

mid=(low+high)/2;

if(data[mid-1]<k1)low=mid+1;

//右縮搜索區(qū)間

else

if(data[mid-1]>k1)high=mid-1;

//左縮搜索區(qū)間

elsereturnmid;//搜索成功

}

return0;//搜索失敗}32精選PPT分析有序順序表(10,20,30,40,50,60)的折半搜索算法性能的判定樹：1050======30<<<<<<>>>>>>204060ASLunsucc=(2*1+3*6)/7=20/7ASLsucc=(1+2*2+3*3)/6=14/6

33精選PPT折半搜索算法的性能分析若設(shè)n=2h-1，則描述折半搜索的判定樹是高度為h

的滿二叉樹。

2h=n+1,h=log2(n+1)第1層結(jié)點(diǎn)有1個(gè),搜索第1層結(jié)點(diǎn)要比較1次;第2層結(jié)點(diǎn)有2個(gè),搜索第2層結(jié)點(diǎn)要比較2次;…,第i(1≤i≤h)層結(jié)點(diǎn)有2i-1

個(gè),搜索第i層結(jié)點(diǎn)要比較i次，…。假定每個(gè)結(jié)點(diǎn)的搜索概率相等，即pi

=1/n，則搜索成功的平均搜索長度為34精選PPT可以用歸納法證明這樣，由2h=n+1,h=log2(n+1)35精選PPT二叉搜索樹(BinarySearchTree)定義

二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼(key)，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同。左子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼。右子樹（如果非空）上所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。左子樹和右子樹也是二叉搜索樹。36精選PPT351545504025102030二叉搜索樹例結(jié)點(diǎn)左子樹上所有關(guān)鍵碼小于結(jié)點(diǎn)關(guān)鍵碼；右子樹上所有關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼；注意：若從根結(jié)點(diǎn)到某個(gè)葉結(jié)點(diǎn)有一條路徑，路徑左邊的結(jié)點(diǎn)的關(guān)鍵碼不一定小于路徑上的結(jié)點(diǎn)的關(guān)鍵碼。37精選PPT如果對(duì)一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。二叉搜索樹的類定義#include<iostream.h>#include<stdlib.h>template<classE,classK>structBSTNode{ //二叉樹結(jié)點(diǎn)類

Edata; //數(shù)據(jù)域

BSTNode<E,K>*left,*right;//左子女和右子女38精選PPTBSTNode(){left=NULL;right=NULL;

}

//構(gòu)造函數(shù)

BSTNode(constEd,BSTNode<E,K>*L=NULL,

BSTNode<E,K>*R=NULL){data=d;left=L;right=R;}

//構(gòu)造函數(shù)～BSTNode(){} //析構(gòu)函數(shù)

voidsetData(Ed){data=d;} //修改

EgetData(){returndata;} //提取

booloperator<(constE&x)

//重載：判小于

{returndata.key<x.key;}39精選PPTbooloperator>(constE&x)

//重載：判大于

{returndata.key>x.key;}booloperator==(constE&x)

//重載：判等于

{returndata.key==x.key;}};template<classE,classK>classBST{ //二叉搜索樹類定義public:BST(){root=NULL;

} //構(gòu)造函數(shù)

BST(Kvalue); //構(gòu)造函數(shù)～BST(){}; //析構(gòu)函數(shù)

40精選PPTboolSearch(constKx)const //搜索

{returnSearch(x,root)!=NULL;}

BST<E,K>&operator=(constBST<E,K>&R); //重載：賦值

voidmakeEmpty()

//置空

{makeEmpty(root);root=NULL;}voidPrintTree()const{PrintTree(root);}//輸出

EMin(){returnMin(root)->data;} //求最小

EMax(){returnMax(root)->data;} //求最大

boolInsert(constE&e1)

//插入新元素

{returnInsert(e1,root);}41精選PPTboolRemove(constKx){returnRemove(x,root);} //刪除含x的結(jié)點(diǎn)private:

BSTNode<E,K>*root; //根指針

KRefValue; //輸入停止標(biāo)志

BSTNode<E,K>* //遞歸：搜索

Search(constKx,BSTNode<E,K>*ptr);voidmakeEmpty(BSTNode<E,K>*&ptr); //遞歸：置空

voidPrintTree(BSTNode<E,K>*ptr)const; //遞歸：打印

BSTNode<E,K>* //遞歸：復(fù)制

Copy(constBSTNode<E,K>*ptr); 42精選PPTBSTNode<E,K>*Min(BSTNode<E,K>*ptr);

//遞歸：求最小

BSTNode<E,K>*Max(BSTNode<E,K>*ptr);

//遞歸：求最大

boolInsert(constE&e1,BSTNode<E,K>*&ptr);

//遞歸：插入

boolRemove(constKx,BSTNode<E,K>*&ptr);

//遞歸：刪除};二叉搜索樹的類定義用二叉鏈表作為它的存儲(chǔ)表示，許多操作的實(shí)現(xiàn)與二叉樹類似。43精選PPT二叉搜索樹的搜索算法在二叉搜索樹上進(jìn)行搜索，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為x

的元素，搜索過程從根結(jié)點(diǎn)開始。如果根指針為NULL，則搜索不成功；否則用給定值

x

與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：若給定值等于根結(jié)點(diǎn)關(guān)鍵碼，則搜索成功，返回搜索成功信息并報(bào)告搜索到結(jié)點(diǎn)地址。44精選PPT若給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹；否則。遞歸搜索根結(jié)點(diǎn)的右子樹。搜索45搜索成功搜索28搜索失敗35154550402510203045精選PPTtemplate<classE,classK>BSTNode<E,K>*BST<E,K>::Search(constKx,BSTNode<E,K>*ptr){//私有遞歸函數(shù)：在以ptr為根的二叉搜索樹中搜//索含x的結(jié)點(diǎn)。若找到，則函數(shù)返回該結(jié)點(diǎn)的//地址，否則函數(shù)返回NULL值。

if(ptr==NULL)returnNULL;

elseif(x<ptr->data)returnSearch(x,ptr->left);elseif(x>ptr->data)returnSearch(x,ptr->right);elsereturnptr; //搜索成功};46精選PPTtemplate<classE,classK>BSTNode<E,K>*BST<E,K>::Search(constKx,BSTNode<E,K>*ptr){//非遞歸函數(shù)：作為對(duì)比，在當(dāng)前以ptr為根的二//叉搜索樹中搜索含x的結(jié)點(diǎn)。若找到，則函數(shù)返//回該結(jié)點(diǎn)的地址，否則函數(shù)返回NULL值。

if(ptr==NULL)returnNULL;

BSTNode<E,K>*temp=ptr;while(temp!=NULL){

if(x==temp->data)returntemp;

if(x<temp->data)

temp=temp->left;47精選PPTelsetemp=temp->right;}returnNULL;};搜索過程是從根結(jié)點(diǎn)開始，沿某條路徑自上而下逐層比較判等的過程。搜索成功，搜索指針將停留在樹上某個(gè)結(jié)點(diǎn)；搜索不成功，搜索指針將走到樹上某個(gè)結(jié)點(diǎn)的空子樹。設(shè)樹的高度為h，最多比較次數(shù)不超過h。48精選PPT二叉搜索樹的插入算法為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如果搜索成功，說明樹中已經(jīng)有這個(gè)元素，不再插入；如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。49精選PPT35154550402510203028插入新結(jié)點(diǎn)28二叉搜索樹的插入每次結(jié)點(diǎn)的插入，都要從根結(jié)點(diǎn)出發(fā)搜索插入位置，然后把新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入。50精選PPT二叉搜索樹的插入算法template<classE,classK>boolBST<E,K>::Insert(constE&e1,

BSTNode<E,K>*&ptr){ //私有函數(shù)：在以ptr為根的二叉搜索樹中插入值為//e1的結(jié)點(diǎn)。若在樹中已有含e1的結(jié)點(diǎn)則不插入

if(ptr==NULL){ //新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入

ptr=newBstNode<E,K>(e1); //創(chuàng)建新結(jié)點(diǎn)

if(ptr==NULL)

{cerr<<"Outofspace"<<endl;exit(1);} returntrue;51精選PPT}elseif(e1<ptr->data)Insert(e1,ptr->left); //左子樹插入

elseif(e1>ptr->data)Insert(e1,ptr->right); //右子樹插入

elsereturnfalse; //x已在樹中,不再插入};注意參數(shù)表中引用型指針參數(shù)ptr的使用。利用二叉搜索樹的插入算法，可以很方便地建立二叉搜索樹。

52精選PPT輸入數(shù)據(jù){53,78,65,17,87,09,81,15}53537853786553786517537865871753786509178753786581178709537865151787098153精選PPTtemplate<classE,classK>BST<E,K>::BST(Kvalue){//輸入一個(gè)元素序列,建立一棵二叉搜索樹

Ex;

root=NULL;RefValue=value; //置空樹

cin>>x; //輸入數(shù)據(jù)

while(x.key!=RefValue){ //RefValue是一個(gè)輸入結(jié)束標(biāo)志

Insert(x,root);cin>>x; //插入，再輸入數(shù)據(jù)

}};54精選PPT二叉搜索樹的刪除算法在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來，同時(shí)確保二叉搜索樹的性質(zhì)不會(huì)失去。為保證在刪除后樹的搜索性能不至于降低，還需要防止重新鏈接后樹的高度增加。刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。被刪結(jié)點(diǎn)右子樹為空，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。55精選PPT被刪結(jié)點(diǎn)左子樹為空，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)左、右子樹都不為空，可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個(gè)結(jié)點(diǎn)的刪除問題。5378651787092345刪除45右子樹空,用左子女頂替5378651787092356精選PPT8853788817940923刪除78左子樹空,用右子女頂替53948817092353788117940945刪除78在右子樹上找中序下第一個(gè)結(jié)點(diǎn)填補(bǔ)236553818817940945236557精選PPT二叉搜索樹的刪除算法template<classE,classK>boolBST<E,K>::Remove(constKx,

BstNode<E,K>*&ptr){//在以ptr為根的二叉搜索樹中刪除含x的結(jié)點(diǎn)

BstNode<E,K>*temp;if(ptr!=NULL){if(x<ptr->data)Remove(x,ptr->left);

//在左子樹中執(zhí)行刪除

elseif(x>ptr->data)Remove(x,ptr->right);

//在右子樹中執(zhí)行刪除58精選PPTelseif(ptr->left!=NULL&&ptr->right!=NULL)

{//ptr指示關(guān)鍵碼為x的結(jié)點(diǎn)，它有兩個(gè)子女

temp=ptr->right;

//到右子樹搜尋中序下第一個(gè)結(jié)點(diǎn)

while(temp->left!=NULL)temp=temp->left;

ptr->data=temp->data;

//用該結(jié)點(diǎn)數(shù)據(jù)代替根結(jié)點(diǎn)數(shù)據(jù)

Remove(ptr->data,ptr->right);} else{ //ptr指示關(guān)鍵碼為x的結(jié)點(diǎn)有一個(gè)子女59精選PPT

temp=ptr; if(ptr->left==NULL)ptr=ptr->right;elseptr=ptr->left;deletetemp;returntrue;} } returnfalse;};注意在刪除算法參數(shù)表引用型指針參數(shù)的使用。60精選PPT

二叉搜索樹性能分析對(duì)于有n個(gè)關(guān)鍵碼的集合，其關(guān)鍵碼有n!種不同排列，可構(gòu)成不同二叉搜索樹有

(棵)

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}

12311113222332361精選PPT同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大。用樹的搜索效率來評(píng)價(jià)這些二叉搜索樹。為此，在二叉搜索樹中加入外結(jié)點(diǎn)，形成判定樹。外結(jié)點(diǎn)表示失敗結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)表示搜索樹中已有的數(shù)據(jù)。這樣的判定樹即為擴(kuò)充的二叉搜索樹。62精選PPT舉例說明。已知關(guān)鍵碼集合

{a1,a2,a3}=

{do,if,to}，對(duì)應(yīng)搜索概率p1,p2,p3,在各搜索不成功間隔內(nèi)搜索概率分別為q0,q1,q2,q3?？赡艿亩嫠阉鳂淙缦滤?。doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)63精選PPT判定樹doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)64精選PPT在判定樹中

○表示內(nèi)部結(jié)點(diǎn)，包含了關(guān)鍵碼集合中的某一個(gè)關(guān)鍵碼；□表示外部結(jié)點(diǎn)，代表各關(guān)鍵碼間隔中的不在關(guān)鍵碼集合中的關(guān)鍵碼。在每兩個(gè)外部結(jié)點(diǎn)間必存在一個(gè)內(nèi)部結(jié)點(diǎn)。一棵判定樹上的搜索成功的平均搜索長度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點(diǎn)上的搜索概率p[i]與搜索該結(jié)點(diǎn)時(shí)所需的關(guān)鍵碼比較次數(shù)c[i](=l[i],即結(jié)點(diǎn)所在層次)乘積之和：65精選PPT設(shè)各關(guān)鍵碼的搜索概率相等：p[i]=1/n搜索不成功的平均搜索長度ASLunsucc為樹中所有外部結(jié)點(diǎn)上搜索概率q[j]與到達(dá)外部結(jié)點(diǎn)所需關(guān)鍵碼比較次數(shù)c'[j](=l'[j])乘積之和：設(shè)外部結(jié)點(diǎn)搜索概率相等：q[j]=1/(n+1)：66精選PPT設(shè)樹中所有內(nèi)、外部結(jié)點(diǎn)的搜索概率都相等：

p[i]=1/3,1≤i≤3,q[j]=1/4,0≤

j≤3

圖(a):ASLsucc=1/3*3+1/3*2+1/3*1=6/3,

ASLunsucc=1/4*3*2+1/4*2+1/4*1=9/4。

圖(b):

ASLsucc=1/3*2*2+1/3*1=5/3,

ASLunsucc=1/4*2*4=8/4。圖(c):ASLsucc=1/3*1+1/3*2+1/3*3=6/3,

ASLunsucc=1/4*1+1/4*2+1/4*3*2=9/4。圖(d):ASLsucc=1/3*2+1/3*3+1/3*1=6/3,

ASLunsucc=1/4*2+1/4*3*2+1/4*1=9/4。(1)相等搜索概率的情形67精選PPT

圖(e):ASLsucc=1/3*1+1/3*3+1/3*2=6/3,

ASLunsucc=1/4*1+1/4*3*2+1/4*2=9/4。圖(b)的情形所得的平均搜索長度最小。一般把平均搜索長度達(dá)到最小的擴(kuò)充的二叉搜索樹稱作最優(yōu)二叉搜索樹。在相等搜索概率的情形下，所有內(nèi)部、外部結(jié)點(diǎn)的搜索概率都相等，視它們的權(quán)值都為1。同時(shí)，第k層有2k-1個(gè)結(jié)點(diǎn)，k=1,2,。則有n個(gè)內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉搜索樹的內(nèi)部路徑長度I至少等于序列

68精選PPT

0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,…

的前n項(xiàng)的和。因此，最優(yōu)二叉搜索樹的搜索成功的平均搜索長度和搜索不成功的平均搜索長度分別為:69精選PPTAVL樹高度平衡的二叉搜索樹

高度不平衡高度平衡ABCABCDEDEAVL樹的定義一棵AVL樹或者是空樹，或者是具有下列性質(zhì)的二叉搜索樹：它的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對(duì)值不超過1。

70精選PPT

結(jié)點(diǎn)的平衡因子

bf(balancefactor)每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出該結(jié)點(diǎn)右子樹的高度減去左子樹的高度所得的高度差，這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子bf。AVL樹任一結(jié)點(diǎn)平衡因子只能取-1,0,1。如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則這棵二叉搜索樹就失去了平衡，不再是AVL樹。如果一棵有n個(gè)結(jié)點(diǎn)的二叉搜索樹是高度平71精選PPT

衡的，其高度可保持在O(log2n)，平均搜索長度也可保持在O(log2n)。#include<iostream.h>#include“stack.h”template<classE,classK>structAVLNode:publicBSTNode<E,K>{//AVL樹結(jié)點(diǎn)的類定義

intbf;

AVLNode(){left=NULL;right=NULL;bf=0;}AVL樹的類定義

72精選PPT

AVLNode(Ed,AVLNode<E,K>*l=NULL,

AVLNode<E,K>*r=NULL){data=d;left=l;right=r;bf=0;}};template<classE,classK>classAVLTree:publicBST<E,K>{//平衡的二叉搜索樹（AVL）類定義public:

AVLTree(){root=NULL;} //構(gòu)造函數(shù)

AVLTree(KRef){RefValue=Ref;root=NULL;}

//構(gòu)造函數(shù)：構(gòu)造非空AVL樹73精選PPTintHeight()const; //高度

AVLNode<E,K>*Search(Kx,AVLNode<E,K>*&par)const; //搜索

boolInsert(E&e1){returnInsert(root,e1);}//插入

boolRemove(Kx,E&e1)

{returnRemove(root,x,e1);} //刪除

friendistream&operator>>(istream&in,

AVLTree<E,K>&Tree); //重載：輸入

friendostream&operator<<(ostream&out,constAVLTree<E,K>&Tree);//重載：輸出protected:intHeight(AVLNode<E,K>*ptr)const;

74精選PPT

boolInsert(AVLNode<E,K>*&ptr,E&e1);boolRemove(AVLNode<E,K>*&ptr,Kx,E&e1);voidRotateL(AVLNode<E,K>*&ptr); //左單旋

voidRotateR(AVLNode<E,K>*&ptr);

//右單旋

voidRotateLR(AVLNode<E,K>*&ptr); //先左后右雙旋

voidRotateRL(AVLNode<E,K>*&ptr); //先右后左雙旋};75精選PPT平衡化旋轉(zhuǎn)如果在一棵平衡的二叉搜索樹中插入一個(gè)新結(jié)點(diǎn)，造成了不平衡。此時(shí)必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。平衡化旋轉(zhuǎn)有兩類：單旋轉(zhuǎn)(左旋和右旋)

雙旋轉(zhuǎn)(左平衡和右平衡)每插入一個(gè)新結(jié)點(diǎn)時(shí),AVL樹中相關(guān)結(jié)點(diǎn)的平衡狀態(tài)會(huì)發(fā)生改變。因此,在插入一個(gè)新結(jié)點(diǎn)后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點(diǎn)的平衡因子。76精選PPT如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn),其中一個(gè)是另一個(gè)的鏡像，其方向與不平衡的形狀相關(guān)。如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。77精選PPT右單旋轉(zhuǎn)左單旋轉(zhuǎn)

左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)左單旋轉(zhuǎn)(RotateLeft)在結(jié)點(diǎn)A的右子女的右子樹E中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成2，出現(xiàn)不平衡。為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)取3個(gè)結(jié)點(diǎn)A、C和E，以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)。78精選PPTtemplate<classE,classK>voidAVLTree<E,K>::RotateL(AVLNode<E,K>*&ptr){//右子樹比左子樹高:做左單旋轉(zhuǎn)后新根在ptr插入左單旋轉(zhuǎn)ACEBDhhh-1h-1100BACEDhhh-1h211BhhCEAD00h-1h179精選PPT

AVLNode<E,K>*subL=ptr;

ptr=subL->right;

subL->right=ptr->left;

ptr->left=subL;

ptr->bf=subL->bf=0;};在結(jié)點(diǎn)A的左子女的左子樹D上插入新結(jié)點(diǎn)使其高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子增到-2，造成不平衡。為使樹恢復(fù)平衡，從A沿插入路徑右單旋轉(zhuǎn)(RotateRight)80精選PPT插入路徑連續(xù)取3個(gè)結(jié)點(diǎn)A、B和D，以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。template<classE,classK>voidAVLTree<E,K>::RotateR(AVLNode<E,K>*&ptr){

BACEDhhh-1h-2-1-1h插入hhh-1h-1ABDCE-100hhh-1BCEAD-100h81精選PPT先左后右雙旋轉(zhuǎn)(RotationLeftRight)//左子樹比右子樹高,旋轉(zhuǎn)后新根在ptrAVLNode<E,K>*subR=ptr;//要右旋轉(zhuǎn)的結(jié)點(diǎn)

ptr=subR->left;subR->left=ptr->right;

//轉(zhuǎn)移ptr右邊負(fù)載

ptr->right=subR;

//ptr成為新根

ptr->bf=subR->bf=0;};在結(jié)點(diǎn)A的左子女的右子樹中插入新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變?yōu)?2，82精選PPT插入hhACEDh-1h-1BFG-100E左單旋轉(zhuǎn)GACDBFhhh-1h1-1-2

造成不平衡。以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)B反時(shí)針旋轉(zhuǎn)，以E代替原來B的位置。83精選PPT再以結(jié)點(diǎn)E為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。使之平衡化。template<classE,classK>voidAVLTree<E,K>::

右單旋轉(zhuǎn)AEhhCDh-1hBFG0-2-2FGDhAh-1CEB00-1hh84精選PPTRotateLR(AVLNode<E,K>*&ptr){AVLNode<E,K>*subR=ptr;AVLNode<E,K>*subL=subR->left;ptr=subL->right;subL->right=ptr->left;ptr->left=subL;

if(ptr->bf<=0)subL->bf=0;

elsesubL->bf=-1;subR->left=ptr->right;ptr->right=subR;

if(ptr->bf==

-1)subR->bf=1;

elsesubR->bf=0;85精選PPTptr->bf=0;};在結(jié)點(diǎn)A的右子女的左子樹中插入新結(jié)點(diǎn)，該子樹高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?，發(fā)生了不平衡。首先以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)C順時(shí)針旋轉(zhuǎn)，以D代替原來C的位置。先右后左雙旋轉(zhuǎn)(RotationRightLeft)86精選PPT插入hhh-1h-1ACEDBFG100右單旋轉(zhuǎn)ACEBFGDhhhh-1102再以結(jié)點(diǎn)D為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)，恢復(fù)樹的平衡。87精選PPTACEDBFGhhh-1h00-1hhh-1h左單旋轉(zhuǎn)ACEBFGD022template<classE,classK>voidAVLTree<E,K>::RotateRL(AVLNode<E,K>*&ptr){AVLNode<E,K>*subL=ptr;88精選PPTAVLNode<E,K>*subR=subL->right;

ptr=subR->left;

subR->left=ptr->right;ptr->right=subR;if(ptr->bf>=0)subR->bf=0;elsesubR->bf=1;subL->right=ptr->left;

ptr->left=subL;if(ptr->bf==1)subL->bf=-1;elsesubL->bf=0;ptr->bf=0;};

89精選PPTAVL樹的插入在向一棵本來是高度平衡的AVL樹中插入一個(gè)新結(jié)點(diǎn)時(shí)，如果樹中某個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值|bf|>1，則出現(xiàn)了不平衡，需要做平衡化處理。AVL樹的插入算法從一棵空樹開始，通過輸入一系列對(duì)象關(guān)鍵碼，逐步建立AVL樹。在插入新結(jié)點(diǎn)后，需從插入結(jié)點(diǎn)沿通向根的路徑向上回溯，如果發(fā)現(xiàn)有不平衡的結(jié)點(diǎn)，需從這個(gè)結(jié)點(diǎn)出發(fā)，使用平衡旋轉(zhuǎn)方法進(jìn)行平衡化處理。90精選PPT設(shè)新結(jié)點(diǎn)p的平衡因子為0，其父結(jié)點(diǎn)為pr。插入新結(jié)點(diǎn)后pr的平衡因子值有三種情況：結(jié)點(diǎn)pr的平衡因子為0。說明剛才是在pr的較矮的子樹上插入了新結(jié)點(diǎn)，此時(shí)不需做平衡化處理，返回主程序。子樹的高度不變。結(jié)點(diǎn)pr的平衡因子的絕對(duì)值|bf|=1。說明插入前pr的平衡因子是0，插入新結(jié)點(diǎn)后，以pr為根的子樹不需平衡化旋轉(zhuǎn)。但該子樹高度10插入后prp91精選PPT

增加，還需從結(jié)點(diǎn)pr向根方向回溯，繼續(xù)考查結(jié)點(diǎn)pr雙親(pr=Parent(pr))的平衡狀態(tài)。結(jié)點(diǎn)pr的平衡因子的絕對(duì)值|bf|=2。說明新結(jié)點(diǎn)在較高的子樹上插入，造成了不平衡，需要做平衡化旋轉(zhuǎn)。此時(shí)可進(jìn)一步分2種情況討論：若結(jié)點(diǎn)pr的bf=2，說明右子樹高，結(jié)合其右子女q的bf分別處理：0-1

插入后prp92精選PPT若q的bf為1，執(zhí)行左單旋轉(zhuǎn)。若q的bf為-1，執(zhí)行先右后左雙旋轉(zhuǎn)。左單旋轉(zhuǎn)插入后2q1prp0pr0ppr=q右左雙旋轉(zhuǎn)插入后2q-1prp0pr0qpr=p93精選PPT若結(jié)點(diǎn)pr的bf=-2，說明左子樹高，結(jié)合其左子女q的bf分別處理：若q的bf為-1，執(zhí)行右單旋轉(zhuǎn)；若q的bf為1，執(zhí)行先左后右雙旋轉(zhuǎn)。下面舉例說明在AVL樹上的插入過程。-2q-1prp-2q1prp右單旋轉(zhuǎn)左右雙旋轉(zhuǎn)94精選PPT例如，輸入關(guān)鍵碼序列為{16,3,7,11,9,26,18,14,15}，插入和調(diào)整過程如下。160163-10左右雙旋731600073110-1116右單旋37169000111163701-273161190-1-22371126916011295精選PPT右左雙旋0左單旋181600732611900031609171126183-1-17161426911127390182611-116196精選PPT1518231816-2左右雙旋73000117149-1161501112626141-29從空樹開始的建樹過程97精選PPTAVL樹的刪除如果被刪結(jié)點(diǎn)x最多只有一個(gè)子女，可做簡單刪除:將結(jié)點(diǎn)x從樹中刪去。因?yàn)榻Y(jié)點(diǎn)x最多有一個(gè)子女，可以簡單地把x的雙親中原來指向x的指針改指到這個(gè)子女結(jié)點(diǎn)；如果結(jié)點(diǎn)x沒有子女，x雙親原來指向x的指針置為NULL。將原來以結(jié)點(diǎn)x為根的子樹的高度減1。9