數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)

2021/4/61第七章搜索結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)電子教案殷人昆王宏數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第1頁。22021/4/6靜態(tài)搜索表二叉搜索樹最優(yōu)二叉搜索樹AVL樹伸展樹紅黑樹第七章搜索結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第2頁。32021/4/6搜索(Search)的概念靜態(tài)搜索表所謂搜索，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對象。搜索的結(jié)果通常有兩種可能：搜索成功，即找到滿足條件的數(shù)據(jù)對象。這時，作為結(jié)果，可報告該對象在結(jié)構(gòu)中的位置,還可給出該對象中的具體信息。搜索不成功，或搜索失敗。作為結(jié)果，應報告一些信息,如失敗標志、位置等。

數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第3頁。42021/4/6通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對象(或記錄)組成。在每個對象中有若干屬性，其中有一個屬性，其值可唯一地標識這個對象。稱為關鍵碼。使用基于關鍵碼的搜索，搜索結(jié)果應是唯一的。但在實際應用時，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。實施搜索時有兩種不同的環(huán)境。靜態(tài)環(huán)境，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。靜態(tài)搜索表

數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第4頁。52021/4/6動態(tài)環(huán)境，為保持較高的搜索效率,搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動進行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。

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

k為止。

靜態(tài)搜索表數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第5頁。62021/4/6數(shù)據(jù)表與搜索表的類定義

#include<iostream.h>#include<assert.h>constintdefaultSize=100;template<classE,classK>classdataList; //數(shù)據(jù)表類的前視定義template<classE,classK>classdataNode{ //數(shù)據(jù)表中結(jié)點類的定義friendclassdataList<E,K>; //聲明其友元類為dataListpublic:數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第6頁。72021/4/6

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

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

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

Kkey; //關鍵碼域

E

other; //其他域（視問題而定）};template<classE,classK>classdataList{ //數(shù)據(jù)表類定義public:數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第7頁。82021/4/6

dataList(intsz=defaultSize)

:ArraySize(sz),CuurentSize(0){

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

assert(Element!=NULL);}

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

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

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

virtualintLength(){returnCurrentSize;}

//求表的長度

virtualKgetKey(inti)const{ //提取第

i（1開始）元素值

數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第8頁。92021/4/6assert(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);//輸出數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第9頁。102021/4/6friendistream&operator>>(istream&in,

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

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

intArraySize,CurrentSize; //數(shù)組最大長度和當前長度};template<classE,classK>booldataList<E,K>::Insert(E&e1){//在dataList的尾部插入新元素,若插入失敗函數(shù)返//回false,否則返回true.數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第10頁。112021/4/6if(CurrentSize==ArraySize)returnfalse;

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

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

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

Element[i]!=x;i++); //在表中順序?qū)ふ覕?shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第11頁。122021/4/6if(i==CurrentSize)returnfalse; //未找到

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

Element[i]=Element[CurrentSize-1];//填補

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

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

數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第12頁。132021/4/6for(inti=1;i<=OutList.CurrentSize;i++)

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

out<<endl; //輸出表的所有表項到out

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

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

dataList<E,K>&InList){ 數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第13頁。142021/4/6cout<<“輸入存儲數(shù)組當前長度:”;

in>>InList.CurrentSize; //從in輸入表的當前長度

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

//從in輸入表的全部表項

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

in>>InList.Element[i-1];}returnin;};數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第14頁。152021/4/6順序搜索主要用于在線性表中搜索。設若表中有CurrentSize個元素，則順序搜索從表的先端開始，順序用各元素的關鍵碼與給定值x進行比較若找到與其值相等的元素，則搜索成功，給出該元素在表中的位置。若整個表都已檢測完仍未找到關鍵碼與x相等的元素，則搜索失敗。給出失敗信息。順序搜索（SequentialSearch）

數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第15頁。162021/4/6一般的順序搜索算法在第二章已經(jīng)討論過，本章介紹一種使用“監(jiān)視哨”的順序搜索方法。設在數(shù)據(jù)表dataList中順序搜索關鍵碼與給定值x相等的數(shù)據(jù)元素，要求數(shù)據(jù)元素在表中從下標0開始存放,下標為CurrentSize的元素作為控制搜索過程自動結(jié)束的“監(jiān)視哨”使用。若搜索成功，則函數(shù)返回該元素在表中序號Location（比下標大1）,若搜索失敗，則函數(shù)返回CurrentSize+1。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第16頁。172021/4/6使用監(jiān)視哨的順序搜索算法

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

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

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

returni+1;};constintSize=10;main(){數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第17頁。182021/4/6dataList<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”;

//搜索不成功};數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第18頁。192021/4/6設數(shù)據(jù)表中有n

個元素，搜索第i

個元素的概率為pi，搜索到第i

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

ci=i+1,i=0,1,,n-1，因此順序搜索的平均搜索長度數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第19頁。202021/4/6一般表中各個元素的搜索概率不同，如果按搜索概率的高低排列表中的元素，從有序順序表的情況可知，能夠得到高的平均搜索長度。在等概率情形，pi=1/n,i=1,2,,n。搜索成功的平均搜索程度為：在搜索不成功情形，ASLunsucc

=n+1。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第20頁。212021/4/6采用遞歸方法搜索值為x的元素，每遞歸一層就向待查元素逼近一個位置，直到到達該元素。假設待查元素在第i（1≤i≤n）個位置，則算法遞歸深度達i（1～i）。102030405060i=1搜索

30102030405060i=2102030405060i=3遞歸順序搜索的遞歸算法數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第21頁。222021/4/6順序搜索的遞歸算法template<classE,classK>intdataList<E,K>::SeqSearch(constKx,

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

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

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

//搜索成功

elsereturnSearch(x,loc+1);//遞歸搜索};數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第22頁。232021/4/6基于有序順序表的順序搜索算法template<classType>intsearchList<Type>::Search(constType&x)const{//順序搜索關鍵碼為x的數(shù)據(jù)對象

for(inti=0;i<CurrentSize;i++)

if(Element[i].key==x)returni;//成功

elseif(Element[i].key>x)break;return

-1;

//順序搜索失敗,返回失敗信息}數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第23頁。242021/4/6有序順序表的順序搜索

(10,20,30,40,50,60)105060======203040<<<<<<>>>>>>數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第24頁。252021/4/6基于有序順序表的折半搜索設n個對象存放在一個有序順序表中，并按其關鍵碼從小到大排好了序。折半搜索時,先求位于搜索區(qū)間正中的對象的下標mid，用其關鍵碼與給定值x比較:

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

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

Element[mid].key<x，把搜索區(qū)間縮小到表的后半部分，繼續(xù)折半搜索。如果搜索區(qū)間已縮小到一個對象，仍未找到想要搜索的對象，則搜索失敗。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第25頁。262021/4/6搜索成功的例子-101346810126012345678搜索lowmidhigh66810125678lowmidhigh665lowmidhigh6數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第26頁。272021/4/6搜索失敗的例子-101346810125012345678搜索lowmidhigh56810125678lowmidhigh655lowmidhigh5數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第27頁。282021/4/6template<classType>classorderedList:publicdataList<Type>{//有序表的類定義,繼承了數(shù)據(jù)表public:

orderedList(intsz=10):

dataList<Type>(sz){}~orderedList(){}

intBinarySearch(constType&x

)const;};

template<classType>intorderedList<Type>:://折半搜索算法數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第28頁。292021/4/6BinarySearch(constType&x,const

intlow,const

inthigh)const{//折半搜索的遞歸算法

intmid=-1;if(low<=high){

mid=(low+high)/2;

if(Element[mid].key<x)mid=BinarySearch(x,mid+1,high);

elseif(Element[mid].key>x) mid=BinarySearch(x,low,mid-1);}returnmid;}數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第29頁。302021/4/6template<classType>intorderedList<Type>::BinarySearch(constType&x)const{

//折半搜索的迭代算法

inthigh=CurrentSize-1,low=0,mid;

while(low<=high){

mid=(low+high)/2;

if(Element[mid].key<x)low=mid+1; //右縮搜索區(qū)

else

if(Element[mid].key>x)high=mid-1;//左縮搜索區(qū)間

elsereturnmid;//搜索成功

}

return

-1;//搜索失敗}數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第30頁。312021/4/6有序順序表的折半搜索的判定樹

(10,20,30,40,50,60)1050======30<<<<<<>>>>>>204060ASLunsucc=(2*1+3*6)/7=20/7ASLsucc=(1+2*2+3*3)/6=14/6數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第31頁。322021/4/6搜索成功時檢測指針停留在樹中某個結(jié)點。搜索不成功時檢測指針停留在某個外結(jié)點（失敗結(jié)點）。3515455025102030搜索22搜索45數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第32頁。332021/4/6折半搜索性能分析若設n=2h-1，則描述折半搜索的判定樹是高度為h-1

的滿二叉樹。

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

i

h)層結(jié)點有2i個,搜索第i層結(jié)點要比較i+1次，…。假定每個結(jié)點的搜索概率相等，即pi

=1/n，則搜索成功的平均搜索長度為數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第33頁。342021/4/6二叉搜索樹(BinarySearchTree)定義

二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：每個結(jié)點都有一個作為搜索依據(jù)的關鍵碼(key)，所有結(jié)點的關鍵碼互不相同。左子樹（如果非空）上所有結(jié)點的關鍵碼都小于根結(jié)點的關鍵碼。右子樹（如果非空）上所有結(jié)點的關鍵碼都大于根結(jié)點的關鍵碼。左子樹和右子樹也是二叉搜索樹。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第34頁。352021/4/6351545504025102030二叉搜索樹例結(jié)點左子樹上所有關鍵碼小于結(jié)點關鍵碼；右子樹上所有關鍵碼大于結(jié)點關鍵碼；注意：若從根結(jié)點到某個葉結(jié)點有一條路徑，路徑左邊的結(jié)點的關鍵碼不一定小于路徑上的結(jié)點的關鍵碼。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第35頁。362021/4/6如果對一棵二叉搜索樹進行中序遍歷，可以按從小到大的順序，將各結(jié)點關鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。二叉搜索樹的類定義#include<iostream.h>#include<stdlib.h>template<classE,classK>structBSTNode{ //二叉樹結(jié)點類

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

BSTNode<E,K>*left,*right;//左子女和右子女數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第36頁。372021/4/6BSTNode(){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;}數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第37頁。382021/4/6booloperator>(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ù)

數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第38頁。392021/4/6boolSearch(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);}數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第39頁。402021/4/6boolRemove(constKx){returnRemove(x,root);} //刪除含x的結(jié)點private:

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

KRefValue; //輸入停止標志

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

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

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

BSTNode<E,K>* //遞歸：復制

Copy(constBSTNode<E,K>*ptr); 數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第40頁。412021/4/6BSTNode<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);

//遞歸：刪除};二叉搜索樹的類定義用二叉鏈表作為它的存儲表示，許多操作的實現(xiàn)與二叉樹類似。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第41頁。422021/4/6二叉搜索樹的搜索算法在二叉搜索樹上進行搜索，是一個從根結(jié)點開始，沿某一個分支逐層向下進行比較判等的過程。它可以是一個遞歸的過程。假設想要在二叉搜索樹中搜索關鍵碼為x

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

x

與根結(jié)點的關鍵碼進行比較：若給定值等于根結(jié)點關鍵碼，則搜索成功，返回搜索成功信息并報告搜索到結(jié)點地址。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第42頁。432021/4/6若給定值小于根結(jié)點的關鍵碼，則繼續(xù)遞歸搜索根結(jié)點的左子樹；否則。遞歸搜索根結(jié)點的右子樹。搜索45搜索成功搜索28搜索失敗351545504025102030數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第43頁。442021/4/6template<classE,classK>BSTNode<E,K>*BST<E,K>::Search(constKx,BSTNode<E,K>*ptr){//私有遞歸函數(shù)：在以ptr為根的二叉搜索樹中搜//索含x的結(jié)點。若找到，則函數(shù)返回該結(jié)點的//地址，否則函數(shù)返回NULL值。

if(ptr==NULL)returnNULL;

elseif(x<ptr->data)returnSearch(x,ptr->left);elseif(x>ptr->data)returnSearch(x,ptr->right);elsereturnptr; //搜索成功};數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第44頁。452021/4/6template<classE,classK>BSTNode<E,K>*BST<E,K>::Search(constKx,BSTNode<E,K>*ptr){//非遞歸函數(shù)：作為對比，在當前以ptr為根的二//叉搜索樹中搜索含x的結(jié)點。若找到，則函數(shù)返//回該結(jié)點的地址，否則函數(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;數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第45頁。462021/4/6elsetemp=temp->right;}returnNULL;};搜索過程是從根結(jié)點開始，沿某條路徑自上而下逐層比較判等的過程。搜索成功，搜索指針將停留在樹上某個結(jié)點；搜索不成功，搜索指針將走到樹上某個結(jié)點的空子樹。設樹的高度為h，最多比較次數(shù)不超過h。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第46頁。472021/4/6二叉搜索樹的插入算法為了向二叉搜索樹中插入一個新元素，必須先檢查這個元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如果搜索成功，說明樹中已經(jīng)有這個元素，不再插入；如果搜索不成功，說明樹中原來沒有關鍵碼等于給定值的結(jié)點，把新元素加到搜索操作停止的地方。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第47頁。482021/4/635154550402510203028插入新結(jié)點28二叉搜索樹的插入每次結(jié)點的插入，都要從根結(jié)點出發(fā)搜索插入位置，然后把新結(jié)點作為葉結(jié)點插入。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第48頁。492021/4/6二叉搜索樹的插入算法template<classE,classK>boolBST<E,K>::Insert(constE&e1,

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

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

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

if(ptr==NULL)

{cerr<<"Outofspace"<<endl;exit(1);} returntrue;數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第49頁。502021/4/6}elseif(e1<ptr->data)Insert(e1,ptr->left); //左子樹插入

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

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

數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第50頁。512021/4/6輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}535378537865537865175378658717537865091787537865811787095378651517870981數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第51頁。522021/4/6template<classE,classK>BST<E,K>::BST(Kvalue){//輸入一個元素序列,建立一棵二叉搜索樹

Ex;

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

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

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

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

}};數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第52頁。532021/4/6二叉搜索樹的刪除算法在二叉搜索樹中刪除一個結(jié)點時，必須將因刪除結(jié)點而斷開的二叉鏈表重新鏈接起來，同時確保二叉搜索樹的性質(zhì)不會失去。為保證在刪除后樹的搜索性能不至于降低，還需要防止重新鏈接后樹的高度增加。刪除葉結(jié)點，只需將其雙親結(jié)點指向它的指針清零，再釋放它即可。被刪結(jié)點右子樹為空，可以拿它的左子女結(jié)點頂替它的位置，再釋放它。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第53頁。542021/4/6被刪結(jié)點左子樹為空，可以拿它的右子女結(jié)點頂替它的位置，再釋放它。被刪結(jié)點左、右子樹都不為空，可以在它的右子樹中尋找中序下的第一個結(jié)點(關鍵碼最小),用它的值填補到被刪結(jié)點中，再來處理這個結(jié)點的刪除問題。5378651787092345刪除45右子樹空,用左子女頂替53786517870923數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第54頁。552021/4/68853788817940923刪除78左子樹空,用右子女頂替53948817092353788117940945刪除78在右子樹上找中序下第一個結(jié)點填補2365538188179409452365數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第55頁。562021/4/6二叉搜索樹的刪除算法template<classE,classK>boolBST<E,K>::Remove(constKx,

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

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í)行刪除數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第56頁。572021/4/6elseif(ptr->left!=NULL&&ptr->right!=NULL)

{//ptr指示關鍵碼為x的結(jié)點，它有兩個子女

temp=ptr->right;

//到右子樹搜尋中序下第一個結(jié)點

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

ptr->data=temp->data;

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

Remove(ptr->data,ptr->right);} else{ //ptr指示關鍵碼為x的結(jié)點有一個子女數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第57頁。582021/4/6

temp=ptr; if(ptr->left==NULL)ptr=ptr->right;elseptr=ptr->left;deletetemp;returntrue;} } returnfalse;};注意在刪除算法參數(shù)表引用型指針參數(shù)的使用。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第58頁。592021/4/6

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

(棵)

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

123111132223323數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第59頁。602021/4/6同樣3個數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能。如果輸入序列選得不好，會建立起一棵單支樹，使得二叉搜索樹的高度達到最大。用樹的搜索效率來評價這些二叉搜索樹。為此，在二叉搜索樹中加入外結(jié)點，形成判定樹。外結(jié)點表示失敗結(jié)點，內(nèi)結(jié)點表示搜索樹中已有的數(shù)據(jù)。這樣的判定樹即為擴充的二叉搜索樹。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第60頁。612021/4/6舉例說明。已知關鍵碼集合

{a1,a2,a3}=

{do,if,to}，對應搜索概率p1,p2,p3,在各搜索不成功間隔內(nèi)搜索概率分別為q0,q1,q2,q3?？赡艿亩嫠阉鳂淙缦滤尽oiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第61頁。622021/4/6判定樹doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第62頁。632021/4/6在判定樹中

○表示內(nèi)部結(jié)點，包含了關鍵碼集合中的某一個關鍵碼；□表示外部結(jié)點，代表各關鍵碼間隔中的不在關鍵碼集合中的關鍵碼。在每兩個外部結(jié)點間必存在一個內(nèi)部結(jié)點。一棵判定樹上的搜索成功的平均搜索長度ASLsucc可以定義為該樹所有內(nèi)部結(jié)點上的搜索概率p[i]與搜索該結(jié)點時所需的關鍵碼比較次數(shù)c[i](=l[i],即結(jié)點所在層次)乘積之和：數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第63頁。642021/4/6設各關鍵碼的搜索概率相等：p[i]=1/n搜索不成功的平均搜索長度ASLunsucc為樹中所有外部結(jié)點上搜索概率q[j]與到達外部結(jié)點所需關鍵碼比較次數(shù)c'[j](=l'[j])乘積之和：設外部結(jié)點搜索概率相等：q[j]=1/(n+1)：數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第64頁。652021/4/6設樹中所有內(nèi)、外部結(jié)點的搜索概率都相等：

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)相等搜索概率的情形數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第65頁。662021/4/6

圖(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)的情形所得的平均搜索長度最小。一般把平均搜索長度達到最小的擴充的二叉搜索樹稱作最優(yōu)二叉搜索樹。在相等搜索概率的情形下，所有內(nèi)部、外部結(jié)點的搜索概率都相等，視它們的權(quán)值都為1。同時，第k層有2k-1個結(jié)點，k=1,2,。則有n個內(nèi)部結(jié)點的擴充二叉搜索樹的內(nèi)部路徑長度I至少等于序列

數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第66頁。672021/4/6

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

的前n項的和。因此，最優(yōu)二叉搜索樹的搜索成功的平均搜索長度和搜索不成功的平均搜索長度分別為:數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第67頁。682021/4/6設二叉搜索樹中所有內(nèi)、外部結(jié)點的搜索概率互不相等。

p[1]=0.5,p[2]=0.1,p[3]=0.05

q[0]=0.15,q[1]=0.1,q[2]=0.05,q[3]=0.05分別計算各個可能的擴充二叉搜索樹的搜索性能，判斷哪些擴充二叉搜索樹的平均搜索長度最小。(2)不相等搜索概率的情形數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第68頁。692021/4/6doiftodoiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05q0=0.15q1=0.1q2=0.05q3=0.05p1=0.5p2=0.1p3=0.05(a)(b)圖(a):ASLsucc=0.5*3+0.1*2+0.05*1=1.75，

ASLunsucc=0.15*3+0.1*3+0.05*2+0.05*1=0.9。圖(b):ASLsucc=0.5*2+0.1*1+0.05*2=1.2，

ASLunsucc=(0.15+0.1+0.05+0.05)*2=0.7。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第69頁。702021/4/6doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(d)(c)圖(c):ASLsucc=0.5*1+0.1*2+0.05*3=0.85,ASLunsucc=0.15*1+0.1*2+0.05*3+0.05*3=0.75.圖(d):ASLsucc=0.5*2+0.1*3+0.05*1=1.35,ASLunsucc=0.15*2+0.1*3+0.05*3+0.05*1=0.8.數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第70頁。712021/4/6由此可知，圖(c)和圖(e)的情形下樹的平均搜索長度達到最小，因此，圖(c)和圖(e)的情形是最優(yōu)二叉搜索樹。doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(e)

圖(e)

:

ASLsucc=0.5*1+0.1*3+0.05*2=0.9;

ASLunsucc=0.15*1+0.1*3+0.05*3+0.05*2=0.7;數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第71頁。722021/4/6最優(yōu)二叉搜索樹在相等搜索概率的情形下，因為所有內(nèi)、外部結(jié)點的搜索概率都相等，把它們的權(quán)值都視為1。有n個內(nèi)部結(jié)點的最優(yōu)二叉搜索樹應為完全二叉樹或理想平衡樹。不相等搜索概率情形下的最優(yōu)二叉搜索樹可能不同于完全二叉樹的形態(tài)?？紤]在不相等搜索概率情形下如何構(gòu)造最優(yōu)二叉搜索樹。假設關鍵碼集合放在一個有序的順序表中

{key[1],key[2],key[3],…key[n]}數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第72頁。732021/4/6設最優(yōu)二叉搜索樹為T[0][n]，其平均搜索長度為：l[i]是內(nèi)部結(jié)點a[i]

所在層次，l‘[j]是外部結(jié)點j所在的層次。C[0][n]是樹的代價。為計算方便，將p[i]與q[j]化為整數(shù)。假定：數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第73頁。742021/4/6構(gòu)造最優(yōu)二叉搜索樹構(gòu)造最優(yōu)二叉搜索樹采用自底向上的方法。要構(gòu)造最優(yōu)二叉搜索樹，必須先構(gòu)造它的左子樹和右子樹，它們也是最優(yōu)二叉搜索樹。樹的構(gòu)造從只有一個結(jié)點的二叉搜索樹開始。對于任一棵子樹T[i][j],它由

{key[i+1],key[i+2],…,key[j]}

組成，其內(nèi)、外部結(jié)點的權(quán)值分別為

{p[i+1],p[i+2],…,p[j]} {q[i],q[i+1],q[i+2],…,q[j]}數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第74頁。752021/4/6使用數(shù)組W[i][j]來存放它的累計權(quán)值和：

W[i][j]=q[i]+p[i+1]+q[i+1]+p[i+2]++q[i+2]+…+p[j]+q[j].0

i

j

n計算W[i][j]可以用遞推公式:

W[i][i]=q[i]

//不是二叉樹,只有一個外部結(jié)點

W[i][i+1]=q[i]+p[i+1]+q[i+1] =W[i][i]+p[i+1]+q[i+1]

//有一個內(nèi)部結(jié)點及兩個外部結(jié)點的二叉樹

W[i][i+2]=W[i][i+1]+p[i+2]+q[i+2]

//加一個內(nèi)部結(jié)點和一個外部結(jié)點的二叉樹數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第75頁。762021/4/6一般地，

W[i][j]=W[i][j-1]+p[j]+q[j]

//再加一個內(nèi)部結(jié)點和一個外部結(jié)點對于一棵包括關鍵碼

{key[i+1],…,key[k-1],key[k],key[k+1],…,key[j]}

的子樹T[i][j],若設它的根結(jié)點為k，i<k

j，q[0]p[1]q[1]…q[i]p[i+1]q[i+1]p[i+2]q[i+2]…W[i][i]W[i][i+1]W[i][i+2]數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第76頁。772021/4/6

它的代價C[i][j]為：

C[i][k-1]+W[i][k-1]+p[k]+C[k][j]+W[k][j]C[i][k-1]是其包含關鍵碼

{key[i+1],key[i+2],…,key[k-1]}

的左子樹T[i][k-1]的代價C[i][k-1]+W[i][k-1]等于把左子樹每個結(jié)點的路徑長度加1而計算出的代價C[k][j]是包含關鍵碼

{key[k+1],key[k+2],…,key[j]}

的右子樹T[k][j]的代價C[k][j]+W[k][j]是把右子樹每個結(jié)點的路徑長度加1之后計算出的代價。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第77頁。782021/4/6因此，公式

C[i][j]=C[i][k-1]+W[i][k-1]+p[k]+C[k][j]++W[k][j]表明:整個樹的代價等于其左子樹的代價加上其右子樹的代價，再加上根的權(quán)值。因為

W[i][j]=p[k]+W[i][k-1]+W[k][j]，

故有

C[i][j]=W[i][j]+C[i][k-1]+C[k][j]

可用

k=i+1,i+2,…,j

分別計算上式,選取使得C[i][j]達到最小的k。這樣可將最優(yōu)二叉搜索樹T[i][j]構(gòu)造出來。

數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第78頁。792021/4/6構(gòu)造的步驟第一步，構(gòu)造只有一個內(nèi)部結(jié)點的最優(yōu)二叉搜索樹：T[0][1]，T[1][2]，…，T[n-1][n]。在T[i-1][i](1

i

n)

中只包含關鍵碼

key[i]。其代價分別是

C[i-1][i]=W[i-1][i]。另外設立一個數(shù)組

R[0..n][0..n]

存放各最優(yōu)二叉搜索樹的根。

R[0][1]=1,R[1][2]=2,…,R[n-1][n]=n第二步,

構(gòu)造有兩個內(nèi)部結(jié)點的最優(yōu)二叉搜索樹：T[0][2],T[1][3],…,T[n-2][n]。數(shù)據(jù)結(jié)構(gòu)第七章-搜索結(jié)構(gòu)全文共168頁，當前為第79頁。802021/4/6在T[i-2][i]中包含兩個關鍵碼

key[i-1],

key[i]。其代價取分別以key[i-1],key[i]

做根時計算出的C[i-2][i]

中的小者。第三步,第四步,…，構(gòu)造有3個內(nèi)部結(jié)點，有4個內(nèi)部結(jié)點，…的最優(yōu)二叉搜索樹。最后構(gòu)造出包含有

n

個內(nèi)部結(jié)點的最優(yōu)二叉搜索樹。對于這樣的最優(yōu)二叉搜索樹,若設根為

k,則根

k

的值存于

R[0][n]

中,其代價存于

C[0][n]

中,左子樹的根存于