第-7-章-集合與搜索數(shù)據(jù)結(jié)構(gòu)課件

第7章集合與搜索1.集合及其表示1)集合的基本概念2)抽象數(shù)據(jù)類型（基本操作）3)用位向量實現(xiàn)集合的基本操作4)用有序鏈表實現(xiàn)集合的基本操作.2.等價類和并查集1)等價類的概念2)實現(xiàn)等價類的鏈表方法3)實現(xiàn)等價類的并查集Union,Find操作（改進(jìn)算法）3.靜態(tài)搜索表1)順序搜索2)基于有序表的折半搜索4.二叉搜索樹1)定義2)二叉搜索樹的操作：查找，插入，刪除5.最優(yōu)二叉搜索樹第7章集合與搜1討論了在靜態(tài)關(guān)鍵碼集合，而且是等概率情況下構(gòu)造最優(yōu)二叉搜索樹.6.AVL樹（平衡的二叉搜索樹）動態(tài)地插入，刪除后為了使該二叉搜索樹能接近最優(yōu)二叉搜索樹.最優(yōu)二叉樹（等概率）-------->平衡的二叉樹高度O(log2n)3/2*log2(n+1)1)定義2)外側(cè)------一次旋轉(zhuǎn)內(nèi)側(cè)------二次旋轉(zhuǎn)3)AVL樹的插入①插入一定在葉子結(jié)點

②找到發(fā)生不平衡的最小子樹③進(jìn)行單旋或雙旋

討論了在靜態(tài)關(guān)鍵碼集合，而且是等概率情況下24)AVL樹的刪除

①按一般的二叉搜索樹進(jìn)行刪除②但刪除后的不平衡會傳遞一直到根，因此要進(jìn)行多次的樹平衡動作.5)AVL樹的高度(算法分析)4)AVL樹的刪除3

第7章集合與搜索

第7章集合與搜索41.集合及其表示1)集合的基本概念集合是成員（對象或元素）的一個群集。例子：colour={red,orange,yellow,green,black,blue,purple,white}集合的特點：①集合的成員必須互不相同②集合中的成員一般是無序的—即沒有先后次序關(guān)系，并用{，，}括住,如s={s1,s2,s3,…sm}③集合中的所有成員有相同的數(shù)據(jù)類型集合的性質(zhì)：成員原子（單元素）集合1.集合及其表示例子：colour={red,o5

①集合的兩個單元素a,b,則必存在a<b,a==b,a>b之一?！啊础保涸O(shè)定集合中單元素具有線性有序關(guān)系。表示“優(yōu)先于”或“小于”②傳遞性：a>b,b>c,則a>c對于整數(shù)，字符和字符串都有一個自然的線性順序{1,2,3,…}集合的基本操作：求集合的并（union),交(intersection),差（difference),判元素是否包含在某集合（contain)例如：A={a,b,c},B={b,d}

AUB={a,b,c,d};AB=;A-B={a,c}ABABAB①集合的兩個單元素a,b,則必存在a<b,a=62)集合的抽象數(shù)據(jù)類型Template<classType>classset{//對象：set(intMaxSetSiZe):MaxSiZe(MaxSetSiZe);//構(gòu)造函數(shù)voidMakeEmpty(set&s);intAddMember(set&s,constTypex);intDelMember(set&s,constType&x);voidAssign(set&s1,set&s2);voidUnion(set&s1,set&s2);voidIntersection(set&s1,set&s2);voidDifference(set&s1,set&s2);intContains(set&s,constType&x);intEgual(set&s1,set&s2);intSubSet(set&s1,set&s2);判別s2是否是集合s1的子集}2)集合的抽象數(shù)據(jù)類型73)用位向量實現(xiàn)集合的抽象數(shù)據(jù)類型bitvector:0123maxsize-10/1討論全集合{0，1，2…n}的一個子集，集合元素是由連續(xù)整數(shù)組成。成員變量為：bitvector，maxsize例如：構(gòu)造函數(shù)：①分配maxsize大小的整數(shù)位向量②置每個下標(biāo)元素為0構(gòu)造函數(shù)set::set(intMaxSetSize):Maxsize(MaxSetSize){assert(Maxsize>0);bitvector=newint[Maxsize];assert(bitvector!=0);for(inti=0;i<Maxsize;i++)bitvector[i]=0;}注意：用位向量來實現(xiàn),對每個集合都分配Maxsize的bit位3)用位向量實現(xiàn)集合的抽象數(shù)據(jù)類型0/1討論全集合{0，18插入Xintset::Addmember(constintx){assert(x>=0&&x<Maxsize);if(!bitvector[x]){bitvector[x]=1;return1;}return0;}求并集A+Bset&set::operator+(set&right){assert(Maxsize==rught.Maxsize);for(inti=0;i<Maxsize;i++)bitvector[i]=bitvector[i]||right.Bitvector[i];retutrn*this;}插入Xset&set::operator+(set9求交集A*Bset&set::operator*(set&right){assert(Maxsize==right.Maxsize);for(inti=0;i<Maxsize;i++)bitvector[i]=bitvector[i]&&right.bitvector[i];return*this;}求差集A-Bset&set::operator-(set&right){assert(Maxsize==right.Maxsize);for(inti=0;i<Maxsize;i++)bitvector[i]=bitvector[i]&&!right.Bitvector[i];return*this;}求交集A*B104)用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型集合中各成員對應(yīng)于鏈表中各結(jié)點，并且e0<e1<…<en}代表集合中各成員（元素）例如：first<(空集合）lastFirst08231735496372last<datalink4)用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型}代表集合中各成員（11成員變量：first,last分別為表頭指針，表尾指針。結(jié)點類的成員變量：data,link.插入一個元素

s<…………xdataglinkplastfirst成員變量：first,last分別為表頭指針，表尾指針12求并集

當(dāng)兩鏈都有元素時：?padata=pbdata:pclink指向pa;pa,pb前進(jìn)，pc前進(jìn)?padata<pbdata:pclink指向pa;pa,pc都前進(jìn)?padata>pbdata:建立一個新結(jié)點（pbdata),pclink

指向新結(jié)點，pb,pc都向前。

B.firstrightpblast<…pb鏈不變pclastpathis…<pc放結(jié)果指針A.first求并集當(dāng)兩鏈都有元素時：B.firstrightpbla13當(dāng)一鏈為空：如果pa為空，則將pb鏈?zhǔn)Ｓ嗟慕Y(jié)點一個個復(fù)制到pc鏈上。如果pb為空，則將pc鏈指向當(dāng)前的pa就可以了。當(dāng)一鏈為空：如果pa為空，則將pb鏈?zhǔn)Ｓ嗟慕Y(jié)點一個個復(fù)制到p14求交集<lastthis3papc…

B?first<pblast3right…A.first求交集<lastthis3papc…B?first15兩鏈都有元素：?pa->data=pb->data:pc,pa,pb前進(jìn)。pc=pc->link;pa=pa->link;pb=pb->link;?pa->data<pb->data:刪除pa.Pc->link=pa->link;deletepa;pa=pc->link;?pa->data>pb->data:pb前進(jìn)。pb=pb->link;一鏈為空時：如果pb非空，則結(jié)束。如果pa非空，則逐個刪去pa中的其余結(jié)點。

2.等價類和并查集

1)等價關(guān)系與等價類等價類：是一個對象（或成員）的集合，在此集合中的所有對象應(yīng)滿足等價關(guān)系。兩鏈都有元素：16例如：判別3個數(shù)a,b,c能否構(gòu)成三角形的三條邊能構(gòu)成三角形的等價類：{（3,4,5）,（4,5,6），(5,6,7）……}對象——滿足構(gòu)成三角形不能構(gòu)成三角形的等價類：{（1,2,3）,（2,3,5），……}?等價類的性質(zhì)：假設(shè)符號表示集合上的等價關(guān)系，x,y,z為該集合中的任意對象。(1)自反的（reflexive)xx稱為自反的(2)對稱的（symmetric)xy,yx稱為對稱的(3)傳遞的（transitive)xy且yz,則xz，稱為傳遞的

等價關(guān)系是集合上的一個自反，對稱，傳遞的關(guān)系。2)確定等價類的鏈表方法。

例如：判別3個數(shù)a,b,c能否構(gòu)成三角形的三條邊對象173)并查集（Union-Findsets)(1)對以上劃分的等價類可以通過并查集（DisjointSet)來實現(xiàn)。并查集的主要操作：?Union(Root1,Root2):把子集合Root2并入集合Root1中。?Find(x):搜索單元素x所在的集合，并返回該集合的名字。?UFSets(s):構(gòu)造函數(shù)。將并查集中s個元素初始化為s個只有一個單元素的子集合。(2)并查集的實現(xiàn)把劃分的各等價類（子集）用樹形來表示。例如：S1={0,6,7,8},S2={4,1,9},S3={2,3,5}它們都屬于集合S={0,1,2,3,4,5,6,7,8,9}3)并查集（Union-Findsets)181023456789具體在機器中采用樹的雙親表示.集合元素的編號從0到size-10parent10002-1-1-122444356789size-1用負(fù)數(shù)表示該集合元素的個數(shù)(不一定是-1,如果是-1則表示單元素子集）∵根結(jié)點無雙親,∴用負(fù)數(shù)表示該集合的個數(shù).i)利用UFSets操作,建立UFSets型集合this,集合中每一個元素初始化為0.

(3)利用并查集來解決等價問題的步驟1023456789具體在機器中采用樹的雙親表示.集合元素的19

各自形成一個單元素的子集合，i=1,2,…,n.ii)重復(fù)以下步驟，直到所有等價對讀入并處理完為止。?讀入一個等價對[i][j]1-1-1-109………parent:0-1-1-1-2-22033149④①③(04)(31)0….....?用Find(i),Find(j)搜索i,j所屬子集合的名字x和y?若x≠y,用Union(x,y)或Union(y,x)將它們合并，前者根在x,后者根在y并查集的樹的類聲明：constintDefaultseze=10;classUFSets各自形成一個單元素的子集合，i=1,2,…,20{public:UFSets(ints=Defaultsize);//構(gòu)造函數(shù)~UFSets(){delete[]parent;}//析構(gòu)函數(shù)ConstUFSet&operator=(UFSetsConst&Value);//集合賦值VoidUnion(intRoot1,intRoot2);//兩子集合并intFind(intx);//尋找集合x的根VoidUnionByHeight(intRoot1,intRoot2);//改進(jìn)的//壓縮高度的合并算法private:int*parent;//集合元素的數(shù)組intsize;//集合元素的數(shù)組}；

{public:21?UFSets::UFSets(ints)構(gòu)造函數(shù){size=S;parent=newint[size+1];//創(chuàng)建雙親指針數(shù)組for(inti=0,i<=size;i++)parent[i]=-1;}?unsignedintUFSets::Find(intx){if(parent[x]<0)returnx;//x是根

elsereturnFind(parent[x];//遞歸找x的雙親的根}?VoidUFSets::Union(intRoot1,intRoot2){parent[Root2]=Root1;}Root1Root2?UFSets::UFSets(ints)22(4)算法分析：Union,Find的效率。?Union的好壞十分影響Find的效率。例子：S={0,1,2,…,n-1},分為n個互不相交的集合。{0}，{1}，{2}，…，{n-1}執(zhí)行n-1次Union操作：Union(0,1),Union(1,2),Union(2,3),…,Union(n-2,n-1)…012n-1則可產(chǎn)生退化的樹一次Union操作所需時間為0(1）n-1次Union,可在0(n)時間內(nèi)完成。(4)算法分析：Union,Find的效率。…012n23若再執(zhí)行Find(0),Find(1),…,Find(n-1)比較次數(shù)1次2次n次

一共需用0(i)=0(n2)

為了減少Find時間，應(yīng)該改進(jìn)Union操作，使樹高不要成線性增長。改進(jìn)的Union算法：比較兩集合（即兩根結(jié)點的parent域）的元素個數(shù)，個數(shù)大的作根，個數(shù)小的作子女。例如上面的例子：ni=1Union(0,4)parent[0]<parent[4]0467819[-4][-3]078491[-7]Parent[4]=06若再執(zhí)行Find(0),Find(1),…,Fin24

實現(xiàn)算法為：VoidUFSets::weightedUnion(intRoot1,intRoot2){inttemp=parent[Root1]+parent[Root2];if(parent[Root2]<parent[Root1]){parent[Root1]=Root2;parent[Root2]=temp;}elce{parent[Root2]=Root1;parent[Root1]=temp;}}

利用加權(quán)求并的算法:0123n-1…[-1][-1][-1][-1]012n-13Union(0,1)…[-1][-1][-2]1023n-1…Union(1,2)實現(xiàn)算法為：0123n-1…[-125最后得到Union(0,n-1)

……012n-1-n?Find算法的改進(jìn)——利用路徑壓縮技術(shù)

改進(jìn)背景：是處理一個等價對，需兩次執(zhí)行Find操作，一次WeightedUnion

上面的例子。如果有m個等價對，需2m次Find操作。

改進(jìn)思想：Find(i)

把i到根的路徑上的每個結(jié)點都成為根的子女。最后得到Union(0,n-1)……012n-1-26

0678913506789135intUFSets::CollapsingFind(inti){for(intj=i;parent[j]>=0;j=parent[j];//j指向根while(i!=j){inttemp=parent[i];parent[i]=j;i=temp;}returnj;}Find(5)0678913506789135intUFSe271)搜索（search):又稱檢索（Retrieval),查找。

給定一個值(key),在集合中找出其關(guān)鍵碼等于給定值的對象。

例子：按學(xué)號檢索成績。

查找結(jié)果:找到，找不到（靜態(tài)環(huán)境——被搜索的結(jié)構(gòu)不改變。）找到，找不到+插入（刪除）（動態(tài)環(huán)境—被搜索的結(jié)構(gòu)發(fā)生改變。）查找種類：

內(nèi)查找

3.靜態(tài)搜索表1)搜索（search):又稱檢索（Retrieva28靜態(tài)搜索表：順序搜索，有序順序表的折半搜索（實際上還有：索引，散列)動態(tài)搜索表:二叉搜索樹(查找樹)

AVL樹（平衡的二叉搜索樹）

外查找B樹，B+樹（放在第10章）2)靜態(tài)搜索結(jié)構(gòu)基于數(shù)組的數(shù)據(jù)表類

靜態(tài)搜索表：順序搜索，有序順序表的折半搜索（實29otherkeyelement01.........:::Currentsize-1Arraysize-1}otherkeyelement01.........::30template<classtype>classdatalist;template<classtype>classNode{friendclassdatalist<type>;public:Node(consttype&value):key(value){}//構(gòu)造函數(shù)Typegetkey()const{returnkey;}//讀取關(guān)鍵碼Voidsetkey(typek){key=k;}//修改關(guān)鍵碼private:typekey;other;};template<classtype>classdatalist{public:template<classtype>class31dataList(intsz=10):Arraysize(sz),Element(newNode<type>[sz]){}virtual~dataList(){delete[]Element;}friendostream&operator<<(ostream&outStream,constdataList<type>&outList);friendistream&operator>>(istream&InStream,dataList<type>&InList);protected:Node<Type>*Element;intArraySize,CurrentSize;};搜索表的類定義template<classtype>classsearchList:publicdataList<type>{public:dataList(intsz=10):Arra32searchList(intsz=10):dataList<Type>(sz){}virtual~searchList(){}virtualintsearch(constType&x)const;};3)順序搜索.又稱線性搜索。方法：從頭開始逐個查找直止找到或最后找不到。具體算法：使用了“監(jiān)視哨”

0123CurrentSizeArraySizeelementxa1a2a…...

查找XsearchList(intsz=33時間復(fù)雜度的分析—平均搜索長度ASLASLsucc=Pi.Ci

搜索概率比較次數(shù)搜索第i個對象(i=0,1,2,…,n-1)需要比較i+1次，Ci=i+1n-1i=0時間復(fù)雜度的分析—平均搜索長度ASLn-1i=034

ASLSUCC=Pi.(i+1)假設(shè)等概率Pi=—=—(i+1)=—.——=——≈0(n)

=—(1+2+…+n)

不成功的比較次數(shù)為n+14)折半搜索（二分搜索）BinarySearch前題：n個對象組成了有序的順序表方法：把x與表的中間元素比較，有三種可能性:i=0n-11n1nn-1i=01nn(n+1)2n+121ni=0n-111n-1i=35Element[mid].getkey()=x,成功，返回下標(biāo)值Element[mid].getkey()>x,x在前半部分，再折半搜索Element[mid].getkey()<x,x在后半部分，再折半搜索。例子：012345678-10134681012x=63次lowmid1mid3mid2high算法：非遞歸的.有序表的類聲明

template<classtype>classorderedlist:publicdatalist<type>{public:Element[mid].getkey36orderedList(intsz=10):dataList<Type>(sz){}virtual~orderedList(){}virtualintsearch(constType&x)const;};template<classType>intorderedList<Type>::BinarySearch(constType&x)const{inthigh=currentSize-1,low=0,mid;while(low<=high){mid=(low+high)/2;if(element[mid].Getkey()<x)low=mid+1;elseif(element[mid].Getkey()>x)high=mid-1;elsereturnmid;}return-1;}orderedList(intsz=10):37算法分析012345678-10134681012

：內(nèi)部結(jié)點，：外部結(jié)點二叉搜索樹（擴充二叉樹）4

0-1186010123<-1-1-00-11-33-44-66-88-1010-12>12410678253122232420123算法分析：內(nèi)部結(jié)點，：外部結(jié)點二叉搜索樹38最好的情況:比較一次最多比較次數(shù)不超過樹的高度h=log2(n+1)平均比較次數(shù)：最好的情況:比較一次39設(shè)n=2-1,ASLSUCC=P.C=Ci=(1*1+2*2+3*2+…(h-1).2+h*2)=—((h-1)*2+1)歸納法可證明=—(h*2-2+1)=—((n+1)log2(n+1)-n)

=——log

2(n+1)-1≈log

2(n+1)-1hn-1i=0ii—1nn-1i=01n—h-1h-212h1n1n1nhhn+1n設(shè)n=2-1,hn-1i=0ii—1nn404.二叉搜索樹（BinarySearchTree)(二叉查找樹）1)二叉搜索樹T的定義或者是一棵空樹,或者是具有下列性質(zhì)的二叉樹T:每個結(jié)點的關(guān)鍵碼互不相同。對T及其任一子樹，一定都滿足K左<K根<K右

其中K左代表K根左子樹中任一key,K右代表K根右子樹中任一key.4.二叉搜索樹（BinarySearchTree)41例子：10045123533724617890查找37，找到查找5，49找不到例子：10045123533724617890查找37，42二叉搜索樹的類聲明:

二叉搜索樹:root根指針,Refvalue數(shù)據(jù)輸入停止的標(biāo)志,用于輸入主要操作:搜索,插入,刪除.

*二叉搜索樹如果按中序遍歷，則得一有序序列。

2)二叉搜索樹上的搜索（尋找x)

方法：從根結(jié)點開始，沿某一個分支逐層向下比較。如果相等，則當(dāng)前結(jié)點就是;如果x<當(dāng)前結(jié)點的key,則沿左子樹進(jìn)行搜索;否則沿右子樹進(jìn)行搜索。

Leftchilddatarighchild二叉搜索樹的類聲明:二叉搜索樹:root根指針,43迭代算法template<classType>Bstnode<Type>*BST<Type>::Find(constType&X,Bstnode<Type>*ptr)const{if(ptr!=NULL){Node<Type>*temp=ptr;while(temp!=NULL){if(tempdata==x)returntemp;if(tempdata<x)temp=temprightchild;elsetemp=templeftchild;}}returnNULL;}Ptrtemp迭代算法Ptrtemp443)二叉搜索樹的插入（插入x)方法：先搜索x,如果x已存在則不插入，如果x不存在，則插入。如插入8853174523786587819488093)二叉搜索樹的插入（插入x)5317452378658745template<classType>voidBST<Type>::insert(ConstType&x,BstNode<Type>*&ptr){if(ptr==NULL){ptr=newBstNode<Type>(x);if(ptr==NULL){cerr<<“outofspace”<<endl;exit(1);}}elseif(x<ptrdata)Insert(x,ptrleftchild);elseif(x>ptrdata)Insert(x,ptrrightchild);}

從一棵空二叉搜索樹，通過輸入一系列關(guān)鍵碼來建立一棵二叉搜索樹的算法：假設(shè)輸入的值都是正整數(shù)，輸入結(jié)束用Refvalue為0或負(fù)數(shù)來示.

template<classType>voidBS46template<classType>BST<Type>::BST(TypeValue){Typex;root=NULL;Refvalue=Value;cin>>x;while(x.key!=Refvalue){insert(x,root);cin>>x;}}4)二叉搜索樹的刪除。刪除后要調(diào)整，使調(diào)整后仍要滿足二叉搜索樹。刪除葉子，刪除即可。刪除的結(jié)點一枝為空：把一枝提升。刪除的結(jié)點兩側(cè)均有子樹:則可以把它的右子樹中尋找中序下的第一個結(jié)點（關(guān)鍵碼最小），用它的值填補到被刪結(jié)點中，然后再處理這個結(jié)點的刪除問題。template<classType>BST<Ty47

以下算法取右子樹中的最小節(jié)點值填補上去：以下算法取右子樹中的最小結(jié)點值填補上去1510811242117232726252832353331302016122918以下算法取右子樹中的最15108112421172485.最優(yōu)二叉搜索樹前面已經(jīng)提到同一個關(guān)鍵碼集合,如果關(guān)鍵碼插入二叉搜索樹的次序不同，就構(gòu)成不同的二叉搜索樹。

n個關(guān)鍵碼有多少種不同次序的排列，有n!種，可構(gòu)成的不同二叉搜索樹有1/(n+1)C棵.在這些樹中如何評價這些搜索樹呢?用樹的搜索效率來衡量.n2n5.最優(yōu)二叉搜索樹n49例子：5325762048146084

如果將它排好序插入1420254853607684

14202548536076845325762048608414如果按上述次序例子：5325762048146050

6.AVL樹（平衡的二叉搜索樹）

1962年，二位俄羅斯數(shù)學(xué)家G.M.Adel’son-vel’sky和E.M.Landis提出的。1)引入目的：提高二叉搜索樹的效率，減少樹的平均搜索長度。一般的二叉搜索樹經(jīng)過插入，刪除操作后，會變得很高，這會影響速度。所以每當(dāng)在二叉搜索樹插入一個新結(jié)點時，應(yīng)調(diào)整樹結(jié)構(gòu)，使之保持平衡。

512838485868422）AVL樹的定義：是一棵二叉搜索樹。樹中每個結(jié)點的左右子樹高度之差的絕對值小于等于1。

樹的高度：根結(jié)點到葉結(jié)點的最大路徑長。

結(jié)點的平衡因子：結(jié)點的右子樹高度—結(jié)點的左子樹高度。

每個結(jié)點leftdatarightbalance2838485868422）AVL樹的定義：leftdata52

AVL樹的高度:保持在O(log2n),平均搜索長度也保持在O(log2n)3）AVL樹的類聲明。因為插入了一個新結(jié)點，可能引入不平衡，要調(diào)整，使之平衡化。平衡化旋轉(zhuǎn)：單旋轉(zhuǎn)（左旋，右旋）雙旋轉(zhuǎn)（左平衡，右平衡）下面先以插入為例來說明平衡化旋轉(zhuǎn)。

ABCDE+0hhhAVL樹的高度:保持在O(log2n),平均搜索長度53

情況1:插入C的右子樹__外側(cè)加高(對A而言)單旋轉(zhuǎn)(左)ABCDEhh}h+1ABCDE1345678910111213456789101112左單旋轉(zhuǎn)調(diào)整后:樹高不變.原h(huán)+2,插入后h+3,調(diào)整后h+2,不平衡不會向外傳遞.h+1+ABCDEhhh}情況1:插入C的右子樹__外側(cè)加高(對A而言)單旋54情況2：插入C的左子樹—內(nèi)側(cè)加高（對A而言）雙旋轉(zhuǎn)（先右后左）ACD13456789101112ACD13456789101112C右下旋A左下旋C右旋轉(zhuǎn)A左旋轉(zhuǎn)ABCDEGFhhh-1h-1orABCDEGFhhh-1h-1orACD13468910111257BACDEGFhhh-1h-1or情況2：插入C的左子樹—內(nèi)側(cè)加高（對A而言）雙旋轉(zhuǎn)（先右后左55

調(diào)整后：樹高不變。原h(huán)+2,插入后h+3,調(diào)整后h+2.小結(jié)一下：以A為根的子樹，調(diào)整前后，其高度不變，調(diào)整不會影響到以A為根的子樹以外的結(jié)點。例如：134567891011121518202224沒有變化*調(diào)整只要在包含插入結(jié)點的最小不平衡子樹中進(jìn)行,即從根到達(dá)插入結(jié)點的路徑上,離插入結(jié)點最近的,并且平衡系數(shù)≠0的結(jié)點為根的子樹。-113456781011121518202224+100009調(diào)整后：樹高不變。原h(huán)+2,插入后h+3,調(diào)整后56以上以右外側(cè)，右內(nèi)側(cè)為例，左外側(cè)，左內(nèi)側(cè)是對稱的。單旋轉(zhuǎn)：外側(cè)—從不平衡結(jié)點沿剛才回溯的路徑取直接下兩層如果三個結(jié)點處于一直線A，C，E雙旋轉(zhuǎn)：內(nèi)側(cè)—從不平衡結(jié)點沿剛才回溯的路徑取直接下兩層如果三個結(jié)點處于一折線A，C，D與前面對稱的情況：左外側(cè)，左內(nèi)側(cè)ABCDEhhhABhCDEhhA右下旋以上以右外側(cè)，右內(nèi)側(cè)為例，左外側(cè)，左內(nèi)側(cè)是對稱的。AB57

ABCDEFGhhh-1h-1ABCDEFGhhorh-1h-1DhABCEFGhh-1h-1orB左下旋A右下旋ABCDEFGhhh-1h-1ABCDEFGhhor58

orh-1h-1ABCDEFGhhhh-1h-1ABCDEFGhorh-1hh-1ABCDEFGhor

4)AVL樹的插入（Insert)把元素x插入到以tree為根的AVL樹中template<classType>intAVLTree<Type>::Insert(AVLNode*&tree,Typex,int&tallar)orh-1h-1A59

從空的AVL樹建樹的算法。我們先從一個例子出發(fā)：7個關(guān)鍵碼發(fā)生四種轉(zhuǎn)動A，Z，C，W，D，X，YAAZAZCAZCWAZC右內(nèi)右雙旋轉(zhuǎn)ADZCW左外從空的AVL樹建樹的算法。我們先從一個例子出發(fā)：A60左單旋轉(zhuǎn)左雙旋轉(zhuǎn)右單旋轉(zhuǎn)ACDZW右外ACDZXWACDZXWY左內(nèi)ACDZXWAYCDZXW左單旋轉(zhuǎn)左雙旋轉(zhuǎn)右單旋轉(zhuǎn)ACDZW右外ACDZXWACDZX615)AVL樹的刪除方法：與二叉搜索樹的刪除方法一樣。WX假設(shè)被刪除結(jié)點為W,它的中序后繼為X,則用X代替W,并刪除X.所不同的是:刪除X后,以X為根的子樹高度減1,這一高度變化可能影響到從X到根結(jié)點上每個結(jié)點的平衡因子,因此要進(jìn)行一系列調(diào)整.5)AVL樹的刪除WX62例子:bacdefghijklmnoprstq現(xiàn)要刪除Cab右內(nèi)defgh(1)abdefghijklmnoprstq右內(nèi)(2)例子:bacdefghijklmnoprstq現(xiàn)要刪除Cab63(3)labdefghijktmnpoqrs

因為刪除操作不平衡要傳遞，所以設(shè)置一個布爾變量shorter來指明子樹的高度是否被縮短。在每個結(jié)點上的操作取決于shorter的值和結(jié)點的平衡因子，有時還要依賴子女的平衡因子。如果從被刪結(jié)點（指真正被刪結(jié)點，如上例中的d）的雙親到根的路徑上的各個結(jié)點p，在shorter保持為true時執(zhí)行下面的操作,如果shorter變?yōu)镕alse,算法終止。綜合為一般情況：（假設(shè)都在左子樹上刪除）(3)labdefghijktmnpoqrs64情況1:}}+_T1T2T3Pqhhh-1{情況2：情況3：(1)shorter為false整個子樹高度不變shorter為true整個子樹高度減少shorter為false高度不變一次旋轉(zhuǎn)PP}+T1T2h..}{}_T1T1T2T2PPh+1hh.{{+T1T2T3Pqhh.qb=0情況1:}}+_T1T2T3Pqhhh-1{情況2：情況3：65(2)P,q的平衡因子符號相同ph}{{hh-1++qT1T2T3q}}{hh-1h-1..pT1T2T3rh-1}{h-1pqT1T2T3T4ph-1}{{hh-1_+qrT1T2T3T4P,q的平衡因子符號不同Shorter為true高度減少Shorter為true高度減少一次旋轉(zhuǎn)雙旋轉(zhuǎn)(3)(2)P,q的平衡因子符號相同ph}{{hh-1++qT1T66

6)算法分析具有n個結(jié)點的平衡二叉樹，進(jìn)行一次插入或刪除的時間最壞情況≦O(log2n)

證明：實際上要考慮n個結(jié)點的平衡二叉樹的最大高度（≦(3/2)log2(n+1))

設(shè)Th

為一棵高度為h，且結(jié)點個數(shù)最少的平衡二叉樹}h-1{h-2h假設(shè)右子樹高度為h-1因結(jié)點個數(shù)最少,左子樹高度只能是h-2這兩棵左子樹,右子樹高度分別為h-2,h-1,也一定是結(jié)點數(shù)最少的:n=7h=3T3h=1T1n=2h=2T2n=4h=4T4n=12h=0T0n=16)算法分析}h-1{h-2h假設(shè)右子樹高度為h-1n67

以上五棵平衡二叉樹，又稱為Fibonacci樹。也可以這樣說一棵高度為h的樹，其右子樹高度為h-1的Fibonacci樹，左子樹是高度為h-2的Fibonacci樹，即Th-2Th-1假設(shè)Nh表示一棵高度為h的Fibonacci樹的結(jié)點個數(shù)，則Nh=Nh-1+Nh-2+1N0=1,N1=2,N2=4,N3=7,N4=12,...N0+1=2,N1+1=3,N2+1=5,N3+1=8,N4+1=13,...

Nh+1滿足費波那契數(shù)的定義，并且Nh+1=Fh+3f0f1f2f3f4f5f6...0112358...費波那契數(shù)Fi滿足下列公式以上五棵平衡二叉樹，又稱為Fibonacci樹。Th68Fi=——(———)-——(———)

1√5

1-√52iii

∵|———|<1,∴——(———)相當(dāng)小1+√521-√521-√521√51√5iNh+1=——(———)+0(1)∵費波那契數(shù)樹是具有相同高度的所有平衡二叉樹中結(jié)點個數(shù)最少的n+1≥Nh+1=——(———)+0(1)

∴h≤————log(n+1)+0(1)≈—log(n+1)log——1+√521+√521+√521√51√5132h+3222h+311-√5iii∵|———|<69習(xí)題、考題：1.7-82.7-123.2004.五.2)AVL4.2002.五.3習(xí)題、考題：70第7章集合與搜索1.集合及其表示1)集合的基本概念2)抽象數(shù)據(jù)類型（基本操作）3)用位向量實現(xiàn)集合的基本操作4)用有序鏈表實現(xiàn)集合的基本操作.2.等價類和并查集1)等價類的概念2)實現(xiàn)等價類的鏈表方法3)實現(xiàn)等價類的并查集Union,Find操作（改進(jìn)算法）3.靜態(tài)搜索表1)順序搜索2)基于有序表的折半搜索4.二叉搜索樹1)定義2)二叉搜索樹的操作：查找，插入，刪除5.最優(yōu)二叉搜索樹第7章集合與搜71討論了在靜態(tài)關(guān)鍵碼集合，而且是等概率情況下構(gòu)造最優(yōu)二叉搜索樹.6.AVL樹（平衡的二叉搜索樹）動態(tài)地插入，刪除后為了使該二叉搜索樹能接近最優(yōu)二叉搜索樹.最優(yōu)二叉樹（等概率）-------->平衡的二叉樹高度O(log2n)3/2*log2(n+1)1)定義2)外側(cè)------一次旋轉(zhuǎn)內(nèi)側(cè)------二次旋轉(zhuǎn)3)AVL樹的插入①插入一定在葉子結(jié)點

②找到發(fā)生不平衡的最小子樹③進(jìn)行單旋或雙旋

討論了在靜態(tài)關(guān)鍵碼集合，而且是等概率情況下724)AVL樹的刪除

①按一般的二叉搜索樹進(jìn)行刪除②但刪除后的不平衡會傳遞一直到根，因此要進(jìn)行多次的樹平衡動作.5)AVL樹的高度(算法分析)4)AVL樹的刪除73

第7章集合與搜索

第7章集合與搜索741.集合及其表示1)集合的基本概念集合是成員（對象或元素）的一個群集。例子：colour={red,orange,yellow,green,black,blue,purple,white}集合的特點：①集合的成員必須互不相同②集合中的成員一般是無序的—即沒有先后次序關(guān)系，并用{，，}括住,如s={s1,s2,s3,…sm}③集合中的所有成員有相同的數(shù)據(jù)類型集合的性質(zhì)：成員原子（單元素）集合1.集合及其表示例子：colour={red,o75

①集合的兩個單元素a,b,則必存在a<b,a==b,a>b之一?！啊础保涸O(shè)定集合中單元素具有線性有序關(guān)系。表示“優(yōu)先于”或“小于”②傳遞性：a>b,b>c,則a>c對于整數(shù)，字符和字符串都有一個自然的線性順序{1,2,3,…}集合的基本操作：求集合的并（union),交(intersection),差（difference),判元素是否包含在某集合（contain)例如：A={a,b,c},B={b,d}

AUB={a,b,c,d};AB=;A-B={a,c}ABABAB①集合的兩個單元素a,b,則必存在a<b,a=762)集合的抽象數(shù)據(jù)類型Template<classType>classset{//對象：set(intMaxSetSiZe):MaxSiZe(MaxSetSiZe);//構(gòu)造函數(shù)voidMakeEmpty(set&s);intAddMember(set&s,constTypex);intDelMember(set&s,constType&x);voidAssign(set&s1,set&s2);voidUnion(set&s1,set&s2);voidIntersection(set&s1,set&s2);voidDifference(set&s1,set&s2);intContains(set&s,constType&x);intEgual(set&s1,set&s2);intSubSet(set&s1,set&s2);判別s2是否是集合s1的子集}2)集合的抽象數(shù)據(jù)類型773)用位向量實現(xiàn)集合的抽象數(shù)據(jù)類型bitvector:0123maxsize-10/1討論全集合{0，1，2…n}的一個子集，集合元素是由連續(xù)整數(shù)組成。成員變量為：bitvector，maxsize例如：構(gòu)造函數(shù)：①分配maxsize大小的整數(shù)位向量②置每個下標(biāo)元素為0構(gòu)造函數(shù)set::set(intMaxSetSize):Maxsize(MaxSetSize){assert(Maxsize>0);bitvector=newint[Maxsize];assert(bitvector!=0);for(inti=0;i<Maxsize;i++)bitvector[i]=0;}注意：用位向量來實現(xiàn),對每個集合都分配Maxsize的bit位3)用位向量實現(xiàn)集合的抽象數(shù)據(jù)類型0/1討論全集合{0，178插入Xintset::Addmember(constintx){assert(x>=0&&x<Maxsize);if(!bitvector[x]){bitvector[x]=1;return1;}return0;}求并集A+Bset&set::operator+(set&right){assert(Maxsize==rught.Maxsize);for(inti=0;i<Maxsize;i++)bitvector[i]=bitvector[i]||right.Bitvector[i];retutrn*this;}插入Xset&set::operator+(set79求交集A*Bset&set::operator*(set&right){assert(Maxsize=