Chapter-7-搜索結(jié)構(gòu)-數(shù)據(jù)結(jié)構(gòu)課件

靜態(tài)搜索結(jié)構(gòu)二叉搜索樹AVL樹Chapter7搜索結(jié)構(gòu)靜態(tài)搜索結(jié)構(gòu)Chapter7搜索結(jié)構(gòu)靜態(tài)搜索結(jié)構(gòu)靜態(tài)搜索表搜索(Search)的概念搜索:就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù) 據(jù)對象。搜索的結(jié)果通常有兩種可能：

搜索成功

搜索不成功靜態(tài)搜索結(jié)構(gòu)靜態(tài)搜索表搜索(Search)的概念搜索:就是在通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對象(或記錄)組成。在每個(gè)對象中有若干屬性，其中有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對象,稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實(shí)際應(yīng)用時(shí)，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。實(shí)施搜索時(shí)有兩種不同的環(huán)境。靜態(tài)環(huán)境

靜態(tài)搜索表動(dòng)態(tài)環(huán)境

動(dòng)態(tài)搜索表

通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對象定義

二叉搜索樹或者是一棵空樹，或者是具有下列性質(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)鍵碼。

左子樹和右子樹也是二叉搜索樹。7.2二叉搜索樹

(BinarySearchTree)定義7.2二叉搜索樹(BinarySearch351545504025102030二叉搜索樹例如果對一棵二叉搜索樹進(jìn)行中序遍歷？結(jié)點(diǎn)左子樹上所有關(guān)鍵碼小于結(jié)點(diǎn)關(guān)鍵碼。右子樹上所有關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼。351545504025102030二叉搜索樹例如果對一棵二n個(gè)結(jié)點(diǎn)的二叉搜索樹的數(shù)目122133132123123{123}{132}{213}{231}{312}{321}【例】3個(gè)結(jié)點(diǎn)的二叉搜索樹：n個(gè)結(jié)點(diǎn)的二叉搜索樹的數(shù)目122133132123123{二叉搜索樹的類定義#include

<iostream.h>template<classType>classBST;template<classType>ClassBstNode<Type>

:publicBinTreeNode{friendclassBST

<Type>;二叉搜索樹的類定義protected:Type

data;

BstNode<Type>*leftChild,*rightChild;};public:BstNode():leftChild(NULL),rightChild(NULL){}

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

BstNode(constTyped,BstNode<Type>*L=NULL,BstNode<Type>*R=NULL)

:data(d),leftChild(L),rightChild(R){}voidsetData(Typed){data=d;} protected:

TypeGetData(){returndata;}~BstNode(){}

//析構(gòu)函數(shù)};template<classType>classBST

:

publicBinaryTree<Type>

{private: BstNode<Type>*root; //根指針

TypeRefValue; //數(shù)據(jù)輸入停止的標(biāo)志

voidMakeEmpty(BstNode<Type>*&ptr);voidInsert(Typex,BstNode<Type>*&ptr);

//插入TypeGetData(){return

voidRemove(Typex,BstNode<Type>*&ptr); //刪除

voidPrintTree(BstNode<Type>*ptr)const;BstNode<Type>*Copy(constBstNode<Type>*ptr);

//復(fù)制

BstNode<Type>*Find(Typex,BstNode<Type>*ptr); //搜索

BstNode<Type>*Min(BstNode<Type>*ptr)const;

//求最小

BstNode<Type>*Max(BstNode<Type>*ptr)const;

//求最大public:voidRemove(Typex,

BST():root(NULL){}//構(gòu)造函數(shù)

BST(Typevalue);

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

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

constBST&operator=(constBST&Value);

voidMakeEmpty()

{MakeEmpty(root);root=NULL;

}voidPrintTree()const

{PrintTree(root);

}

intFind(Typex)

//搜索元素

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

TypeMin(){

returnMin(root)->data;}

TypeMax(){

returnMax(root)->data;}BST():root(NULL){}

voidInsert(Typex){Insert(x,root);

}

//插入新元素

voidRemove(Typex){Remove(x,root);

}

//刪除含x的結(jié)點(diǎn)}有三種基本操作：查找插入刪除voidInsert(Typex){I二叉搜索樹（二叉排序樹）對于樹中的每個(gè)結(jié)點(diǎn)x，它的左子樹中所有關(guān)鍵碼小于x的關(guān)鍵碼，而它的右子樹中所有關(guān)鍵碼大于x的關(guān)鍵碼。有三種基本操作：查找插入刪除二叉搜索樹（二叉排序樹）對于樹中的每個(gè)結(jié)點(diǎn)x，它的左子樹中所

是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。二叉搜索樹上的搜索搜索45搜索成功351545504025102030

搜索28搜索失敗是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程基本思想：假設(shè)在二叉搜索樹中搜索關(guān)鍵碼為x的元素，搜索過程從根結(jié)點(diǎn)開始。如果根指針為NULL，則搜索不成功；否則用給定值x與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：如果給定值等于根結(jié)點(diǎn)的關(guān)鍵碼，則搜索成功。如果給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹；否則。遞歸搜索根結(jié)點(diǎn)的右子樹?；舅枷耄簍emplate<classType>BstNode<Type>*BST<Type>::Find(Typex,BstNode<Type>*ptr)const{//二叉搜索樹的遞歸的搜索算法

if(ptr==NULL)returnNULL;//搜索失敗

elseif(x<ptr->data)//在左子樹搜索

return

Find(x,ptr->leftChild);

elseif(x>ptr->data)//在右子樹搜索

return

Find(x,ptr->rightChild);

elsereturnptr;

//相等,搜索成功

}template<classType>template<classType>BstNode<Type>*BST<Type>::Find(Typex,BstNode<Type>*ptr)const{//二叉搜索樹的迭代的搜索算法

if(ptr!=NULL){

BstNode<Type>*temp=ptr;//從根搜索

while(temp!=NULL){

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

if(temp->data<x)temp=temp->rightChild;

//右子樹

elsetemp=temp->leftChild;//左子樹

}

}returnNULL;//搜索失敗}template<classType>

二叉搜索樹的插入35154550402510203028插入新結(jié)點(diǎn)28二叉搜索樹的插入351545504025102030基本思想：為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。搜索成功:樹中已有這個(gè)元素,不再插入。搜索不成功:樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方?；舅枷耄簍emplate<classType>voidBST<Type>::

Insert

(Typex,BstNode<Type>*&ptr)

{

if(ptr==NULL) {//空二叉樹

ptr=newBstNode<Type>(x);//創(chuàng)建結(jié)點(diǎn)

if(ptr==NULL)

{cout<<“存儲(chǔ)不足"<<endl;exit(1);

}

}

elseif(x<ptr->data)//在左子樹插入

Insert(x,ptr->leftChild);

elseif(x>ptr->data)//在右子樹插入

Insert(x,ptr->rightChild);}

遞歸的二叉搜索樹插入算法template<classType>voidBST

輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}

，建立二叉搜索樹的過程535378537865537865175378658717537865091787537865811787095378651517870981輸入數(shù)據(jù){53,78,65,17,87,09template<classType>BST<Type>::BST(Typevalue){//輸入數(shù)據(jù),建立二叉搜索樹。RefValue是輸入//結(jié)束標(biāo)志。這個(gè)值應(yīng)取不可能在輸入序列中//出現(xiàn)的值,例如輸入序列的值都是正整數(shù)時(shí),//取RefValue為0或負(fù)數(shù)。

Typex;

root=NULL;RefValue=value;

cin>>x;

while(x!=RefValue)

{Insert(x,root);

cin>>x;

}}template<classType>二叉搜索樹的刪除在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來，同時(shí)確保二叉搜索樹的性質(zhì)不會(huì)失去。為保證在刪除后樹的搜索性能不至于降低，還需要防止重新鏈接后樹的高度增加。351545504025102030二叉搜索樹的刪除在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因刪除結(jié)基本思想：首先查找，確定被刪除結(jié)點(diǎn)是否在二叉搜索樹中。分情況討論：

刪除葉結(jié)點(diǎn)：被刪結(jié)點(diǎn)右子樹或左子樹為空：可以拿它的左子女結(jié)點(diǎn)或右子女結(jié)點(diǎn)頂替它的位置，再釋放它。（刪除結(jié)點(diǎn)為ptr指針?biāo)?，其雙親結(jié)點(diǎn)為f結(jié)點(diǎn)指針?biāo)?，被刪除結(jié)點(diǎn)的左子樹和右子樹分別用pl和pr表示）只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可?；舅枷耄悍智闆r討論：可以拿它的左子女結(jié)點(diǎn)或右子女結(jié)點(diǎn)頂替5378651787092345刪除45右子樹空,用左子女頂替5378651787092353788817940923刪除78左子樹空,用右子女頂替5394881709235378651787092345刪除45右子樹空,用左子女8853788117940945刪除782365538188179409452365被刪結(jié)點(diǎn)左、右子樹都不為空，？可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個(gè)結(jié)點(diǎn)的刪除問題。在右子樹上找中序下第一個(gè)結(jié)點(diǎn)填補(bǔ)8853788117940945刪除782365538188

二叉搜索樹的刪除算法template<classType>voidBST<Type>::Remove(constType&x,BstNode<Type>*&ptr){

BstNode<Type>*temp;

if(ptr!=NULL)

if(x<ptr->data)//在左子樹中刪除

Remove(x,ptr->leftChild);elseif(x>ptr->data)//在右子樹中刪除

Remove(x,ptr->rightChild);elseif(ptr->leftChild!=NULL&&

ptr->rightChild!=NULL){二叉搜索樹的刪除算法template<class

temp=Min(ptr->rightChild);

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

ptr->data=temp->data;//填補(bǔ)上

Remove(ptr->data,ptr->rightChild);

//在ptr的右子樹中刪除temp結(jié)點(diǎn)

}else{ //ptr結(jié)點(diǎn)只有一個(gè)或零個(gè)子女

temp=ptr; if(ptr->leftChild==NULL)ptr=ptr->rightChild;//只有右子女

elseif(ptr->rightChild==NULL)ptr=ptr->leftChild;//只有左子女

deletetemp; }}temp=Min(p同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。

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

如果輸入序列選的不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大平衡處理122133132123123同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起7.3AVL樹AVL樹的定義

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

高度不平衡高度平衡ABCABCDEDE(高度平衡的二叉搜索樹)7.3AVL樹AVL樹的定義一棵AVL樹或者是空每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字,給出該結(jié)點(diǎn)右子樹的高度減去左子樹的高度所得的高度差,這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子balance

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

高度不平衡高度平衡ABCABCDEDE3200001100每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字,給出該結(jié)點(diǎn)右子樹的高度減去左子樹的高關(guān)于AVL樹：AVL樹任一結(jié)點(diǎn)平衡因子只能取-1,0,1如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對值大于1,則這棵二叉搜索樹就失去了平衡,不再是AVL樹。如果一棵二叉搜索樹是高度平衡的,且有n個(gè)結(jié)點(diǎn)，其高度可保持在O(log2n),平均搜索長度也可保持在O(log2n)。ABCDE1100關(guān)于AVL樹：ABCDE1100AVL樹的類定義template<classType>classAVLTree{public:

structAVLNode{ //AVL樹結(jié)點(diǎn)

Typedata;intbalance;AVLNode<Type>*left,*right;AVLNode():

left(NULL),right(NULL),balance(0)

{}AVLNode(Typed,AVLNode<Type>*l=NULL,AVLNode<Type>*r=NULL)

:data(d),left(l),right(r),balance(0){}};AVL樹的類定義template<classType>protected:

TypeRefValue;

AVLNode*root;

intInsert(AVLNode<Type>*&Tree,Typex);

voidRotateLeft(AVLNode<Type>*Tree,AVLNode<Type>*&NewTree);

voidRotateRight(AVLNode<Type>*Tree,AVLNode<Type>*&NewTree);

voidLeftBalance(AVLNode<Type>*&Tree);

voidRightBalance(AVLNode<Type>*&Tree);intHeight(AVLNode<Type>*t)const;

public:protected:

AVLTree():root(NULL){}

AVLNode(TypeRef):RefValue(Ref),root(NULL){}

intInsert(Typex)

{returnInsert(root,x);}

friendistream&operator>>(istream&in,AVLTree<Type>&Tree);

friendostream&operator<<(ostream&out,

constAVLTree<Type>&Tree);

intHeight()const;}AVLTree():root(NULL)平衡化旋轉(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)的平衡因子。平衡化旋轉(zhuǎn)有兩類：如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。12如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起右單旋轉(zhuǎn)(RotateRight)h插入BACEDhhh-1h-2-1-1hhh-1h-1ABDCE-100hhh-1BCEAD-100h右單旋轉(zhuǎn)(RotateRight)h插入BACEDhhh如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。hhACEDh-1h-1BFG-100先左后右EGACDBFhhh-1h1-1-2插入如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)FGDhAh-1CEB00-1hh右單旋轉(zhuǎn)AEhhCDh-1hBFG0-2-2插入hhACEDh-1h-1BFG-100E左單旋轉(zhuǎn)GACDBFhhh-1h1-1-2FGDhAh-1CEB00-1hh右單AEhhCDh-1hB插入hhh-1h-1ACEDBFG100右單旋轉(zhuǎn)ACEBFGDhhhh-1-112先右后左ACEDBFGhhh-1h00-1左單旋轉(zhuǎn)hhh-1hACEBFGD022插入hhh-1h-1ACEDBFG100右ACEBFGDhh右單旋轉(zhuǎn)左單旋轉(zhuǎn)

左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)右單旋轉(zhuǎn)左單旋轉(zhuǎn)左右雙旋轉(zhuǎn)右左雙旋轉(zhuǎn)AVL樹的插入在向一棵本來是高度平衡的AVL樹中插入一個(gè)新結(jié)點(diǎn)時(shí)，如果樹中某個(gè)結(jié)點(diǎn)的平衡因子的絕對值|balance|>1，則出現(xiàn)了不平衡，需要做平衡化處理。在AVL樹上定義了重載操作“>>”和“<<”，以及中序遍歷的算法。利用這些操作可以執(zhí)行AVL樹的建立和結(jié)點(diǎn)數(shù)據(jù)的輸出。算法從一棵空樹開始，通過輸入一系列對象關(guān)鍵碼，逐步建立AVL樹。在插入新結(jié)點(diǎn)時(shí)使用平衡旋轉(zhuǎn)方法進(jìn)行平衡化處理。AVL樹的插入在向一棵本來是高度平衡的AVL樹中插入一個(gè)新結(jié)例，輸入關(guān)鍵碼序列為{16,3,7,11,9,26,18,14,15}，插入和調(diào)整過程如下。161603163-10701-2左右雙旋731600073110-117316161190-1-2右單旋3716900013711269161101122例，輸入關(guān)鍵碼序列為{16,3,7,11,9,181803163-101602右左雙旋739000182611-1732616119-1左單旋971614001711262691111181803163-101602右左雙旋73900018261518231816-2左右雙旋73000117149-1161501112626141-29從空樹開始的建樹過程1518231816-2左右雙旋73000117149-11下面的算法將通過遞歸方式將新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入并逐層修改各結(jié)點(diǎn)的平衡因子。在發(fā)現(xiàn)不平衡時(shí)立即執(zhí)行相應(yīng)的平衡化旋轉(zhuǎn)操作，使得樹中各結(jié)點(diǎn)重新平衡化。在程序中，用變量success記載新結(jié)點(diǎn)是否存儲(chǔ)分配成功，并用它作為函數(shù)的返回值。算法從樹的根結(jié)點(diǎn)開始，遞歸向下找插入位置。在找到插入位置(空指針)后，為新結(jié)點(diǎn)動(dòng)態(tài)分配存儲(chǔ)空間，將它作為葉結(jié)點(diǎn)插入，并置success為1，再將taller置為1，以表明插入成功。在退出遞歸沿插入路徑向上返回時(shí)做必要的調(diào)整。AVL樹的插入算法下面的算法將通過遞歸方式將新結(jié)點(diǎn)作為葉結(jié)點(diǎn)插入并逐層修改各結(jié)template<classType>intAVLTree<Type>::Insert(AVLNode<Type>*&tree,Typex,

int&taller){//AVL樹的插入算法

intsuccess;

if(tree==NULL){

tree=newAVLNode(x);success=(tree!=NULL)?1:0;

if(success)taller=1;

}

elseif(x<tree->data){success=Insert(tree->left,x,taller);

if(taller)template<classType>intAVLT

switch(tree->balance){

case

-1:LeftBalance(tree,taller);break;case0:tree->balance=-1;break;case1:tree->balance=0;taller=0;}

}

elseif(x>tree->data){success=Insert(tree->right,x,taller);

if(taller)

switch(tree->balance){case

-1:tree->balance=0;taller=0;break; case0:tree->balance=1;

break;

case1:RightBalance(tree,taller);switch(tree->balanc

}

}

returnsuccess;

} }AVL樹的刪除將結(jié)點(diǎn)x從樹中刪去。因?yàn)榻Y(jié)點(diǎn)x最多有一個(gè)子女，可以簡單地把x的雙親結(jié)點(diǎn)中原來指向x的指針改指到這個(gè)子女結(jié)點(diǎn)；如果結(jié)點(diǎn)x沒有子女，x雙親結(jié)點(diǎn)的相應(yīng)指針置為NULL。將原來以結(jié)點(diǎn)x為根的子樹的高度減1。1.如果被刪結(jié)點(diǎn)x最多只有一個(gè)子女，那么問題比較簡單:AVL樹的刪除將結(jié)點(diǎn)x從樹中刪去。1.如果被刪結(jié)點(diǎn)x最多只有搜索x

在中序次序下的直接前驅(qū)y

(同樣可以找直接后繼)。把結(jié)點(diǎn)y

的內(nèi)容傳送給結(jié)點(diǎn)x，現(xiàn)在問題轉(zhuǎn)移到刪除結(jié)點(diǎn)y。把結(jié)點(diǎn)y當(dāng)作被刪結(jié)點(diǎn)x。因?yàn)榻Y(jié)點(diǎn)y最多有一個(gè)子女，我們可以簡單地用1給出的方法進(jìn)行刪除。2.如果被刪結(jié)點(diǎn)x有兩個(gè)子女:搜索x在中序次序下的直接前驅(qū)y(同樣可以找直接后繼)必須沿x通向根的路徑反向追蹤高度的變化對路徑上各個(gè)結(jié)點(diǎn)的影響。用一個(gè)布爾變量shorter

來指明子樹的高度是否被縮短。在每個(gè)結(jié)點(diǎn)上要做的操作取決于

shorter

的值和結(jié)點(diǎn)的balance，有時(shí)還要依賴子女的balance。布爾變量shorter的值初始化為True。然后對于從x的雙親到根的路徑上的各個(gè)結(jié)點(diǎn)p，在shorter保持為True時(shí)執(zhí)行下面操作。如果shorter變成False，算法終止。必須沿x通向根的路徑反向追蹤高度的變化對路徑上各個(gè)結(jié)點(diǎn)case1:當(dāng)前結(jié)點(diǎn)p的balance為0。如果它的左子樹或右子樹被縮短，則它的balance改為1或-1，同時(shí)shorter置為False。0hhh-1刪除一個(gè)結(jié)點(diǎn),高度降低一層不旋轉(zhuǎn)1hh-1ppcase1:當(dāng)前結(jié)點(diǎn)p的balance為0。如果它c(diǎn)ase2:結(jié)點(diǎn)p的balance不為0，且較高的子樹被縮短，則p的balance改為0，同時(shí)shorter

置為True。-1h+1hh刪除一個(gè)結(jié)點(diǎn),高度降低一層不旋轉(zhuǎn)0hhpp高度減1case2:結(jié)點(diǎn)p的balance不為0，且較高的case3:結(jié)點(diǎn)p的balance不為0，且較矮的子樹又被縮短，則在結(jié)點(diǎn)p發(fā)生不平衡。需要進(jìn)行平衡化旋轉(zhuǎn)來恢復(fù)平衡。有3種平衡化操作:case3:結(jié)點(diǎn)p的balance不為0，且較矮的case3a:如果q(較高的子樹)的balance為0，執(zhí)行一個(gè)單旋轉(zhuǎn)來恢復(fù)結(jié)點(diǎn)p的平衡，置shorter為False。1hhh-1刪除結(jié)點(diǎn)左單旋ph0q1hh-1phq-1令p的較高的子樹的根為q(該子樹未被縮短),根據(jù)q的balancecase3a:如果q(較高的子樹)的balanccase3b:如果q的balance與p的balance相同，則執(zhí)行一個(gè)單旋轉(zhuǎn)來恢復(fù)平衡,結(jié)點(diǎn)p和q的balance均改為0,同時(shí)置shorter為True。1hh-1刪除結(jié)點(diǎn)左單旋ph1q0h-1phq0h-1h-1case3b:如果q的balance與p的ba0case3c:如果p與q的balance相反,則執(zhí)行一個(gè)雙旋轉(zhuǎn)來恢復(fù)平衡,先圍繞q轉(zhuǎn)再圍繞p轉(zhuǎn)。新根結(jié)點(diǎn)的balance置為0，其他結(jié)點(diǎn)的balance相應(yīng)處理,同時(shí)置shorter為True。1hh-1刪除結(jié)點(diǎn)p-1qh-1或h-2h-1或h-2h-1rh-1h-1h-1h-100pqr右左雙旋高度減10case3c:如果p與q的balance相反ABCDEFGHIJKLMNOPQRST0000000-1-1-1-1-1-1-111111樹的初始狀態(tài)舉例ABCDEFGHIJKLMNOPQRST0000000-1-ABCDEFGHIJKLMNOPQRST0000000-1-1-1-1-1-1-111111刪除結(jié)點(diǎn)P

尋找結(jié)點(diǎn)P在中序下的直接前驅(qū)O,用O頂替P,刪除O。用O取代PABCDEFGHIJKLMNOPQRST0000000-1-ABCDEFGHIJKLMNOQRST000000-1-1-1-1-1-1-111111刪除結(jié)點(diǎn)P左單旋轉(zhuǎn)

O與R的平衡因子同號(hào),以R為旋轉(zhuǎn)軸做左單旋轉(zhuǎn),M的子樹高度減1。ABCDEFGHIJKLMNOQRST000000-1-1-ABCDEFGHIJKLMNOQRST000000-1-1-1-1-1-1-11001刪除結(jié)點(diǎn)P0

M的子樹高度減1,M發(fā)生不平衡。M與E的平衡因子反號(hào),做左右雙旋轉(zhuǎn)。向上繼續(xù)調(diào)整ABCDEFGHIJKLMNOQRST000000-1-1-ABCDEFGHIJNKLMOR00000-100-1-1-1-10100刪除結(jié)點(diǎn)P00TQ0SABCDEFGHIJNKLMOR00000-100-1-1-AVL樹的高度有n個(gè)結(jié)點(diǎn)的AVL樹的高度不超過

1.44*log2(n+2)-1.328在AVL樹刪除一個(gè)結(jié)點(diǎn)并做平衡化旋轉(zhuǎn)所需時(shí)間為O(log2n)。二叉搜索樹適合于組織在內(nèi)存中的較小的索引(或目錄)。對于存放在外存中的較大的文件系統(tǒng)，用二叉搜索樹來組織索引不太合適。在文件檢索系統(tǒng)中大量使用的是用B-樹或B+樹做文件索引。AVL樹的高度有n個(gè)結(jié)點(diǎn)的AVL樹的高度不超過靜態(tài)搜索結(jié)構(gòu)二叉搜索樹AVL樹Chapter7搜索結(jié)構(gòu)靜態(tài)搜索結(jié)構(gòu)Chapter7搜索結(jié)構(gòu)靜態(tài)搜索結(jié)構(gòu)靜態(tài)搜索表搜索(Search)的概念搜索:就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù) 據(jù)對象。搜索的結(jié)果通常有兩種可能：

搜索成功

搜索不成功靜態(tài)搜索結(jié)構(gòu)靜態(tài)搜索表搜索(Search)的概念搜索:就是在通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對象(或記錄)組成。在每個(gè)對象中有若干屬性，其中有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對象,稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實(shí)際應(yīng)用時(shí)，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。實(shí)施搜索時(shí)有兩種不同的環(huán)境。靜態(tài)環(huán)境

靜態(tài)搜索表動(dòng)態(tài)環(huán)境

動(dòng)態(tài)搜索表

通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對象定義

二叉搜索樹或者是一棵空樹，或者是具有下列性質(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)鍵碼。

左子樹和右子樹也是二叉搜索樹。7.2二叉搜索樹

(BinarySearchTree)定義7.2二叉搜索樹(BinarySearch351545504025102030二叉搜索樹例如果對一棵二叉搜索樹進(jìn)行中序遍歷？結(jié)點(diǎn)左子樹上所有關(guān)鍵碼小于結(jié)點(diǎn)關(guān)鍵碼。右子樹上所有關(guān)鍵碼大于結(jié)點(diǎn)關(guān)鍵碼。351545504025102030二叉搜索樹例如果對一棵二n個(gè)結(jié)點(diǎn)的二叉搜索樹的數(shù)目122133132123123{123}{132}{213}{231}{312}{321}【例】3個(gè)結(jié)點(diǎn)的二叉搜索樹：n個(gè)結(jié)點(diǎn)的二叉搜索樹的數(shù)目122133132123123{二叉搜索樹的類定義#include

<iostream.h>template<classType>classBST;template<classType>ClassBstNode<Type>

:publicBinTreeNode{friendclassBST

<Type>;二叉搜索樹的類定義protected:Type

data;

BstNode<Type>*leftChild,*rightChild;};public:BstNode():leftChild(NULL),rightChild(NULL){}

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

BstNode(constTyped,BstNode<Type>*L=NULL,BstNode<Type>*R=NULL)

:data(d),leftChild(L),rightChild(R){}voidsetData(Typed){data=d;} protected:

TypeGetData(){returndata;}~BstNode(){}

//析構(gòu)函數(shù)};template<classType>classBST

:

publicBinaryTree<Type>

{private: BstNode<Type>*root; //根指針

TypeRefValue; //數(shù)據(jù)輸入停止的標(biāo)志

voidMakeEmpty(BstNode<Type>*&ptr);voidInsert(Typex,BstNode<Type>*&ptr);

//插入TypeGetData(){return

voidRemove(Typex,BstNode<Type>*&ptr); //刪除

voidPrintTree(BstNode<Type>*ptr)const;BstNode<Type>*Copy(constBstNode<Type>*ptr);

//復(fù)制

BstNode<Type>*Find(Typex,BstNode<Type>*ptr); //搜索

BstNode<Type>*Min(BstNode<Type>*ptr)const;

//求最小

BstNode<Type>*Max(BstNode<Type>*ptr)const;

//求最大public:voidRemove(Typex,

BST():root(NULL){}//構(gòu)造函數(shù)

BST(Typevalue);

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

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

constBST&operator=(constBST&Value);

voidMakeEmpty()

{MakeEmpty(root);root=NULL;

}voidPrintTree()const

{PrintTree(root);

}

intFind(Typex)

//搜索元素

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

TypeMin(){

returnMin(root)->data;}

TypeMax(){

returnMax(root)->data;}BST():root(NULL){}

voidInsert(Typex){Insert(x,root);

}

//插入新元素

voidRemove(Typex){Remove(x,root);

}

//刪除含x的結(jié)點(diǎn)}有三種基本操作：查找插入刪除voidInsert(Typex){I二叉搜索樹（二叉排序樹）對于樹中的每個(gè)結(jié)點(diǎn)x，它的左子樹中所有關(guān)鍵碼小于x的關(guān)鍵碼，而它的右子樹中所有關(guān)鍵碼大于x的關(guān)鍵碼。有三種基本操作：查找插入刪除二叉搜索樹（二叉排序樹）對于樹中的每個(gè)結(jié)點(diǎn)x，它的左子樹中所

是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的過程。二叉搜索樹上的搜索搜索45搜索成功351545504025102030

搜索28搜索失敗是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程基本思想：假設(shè)在二叉搜索樹中搜索關(guān)鍵碼為x的元素，搜索過程從根結(jié)點(diǎn)開始。如果根指針為NULL，則搜索不成功；否則用給定值x與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：如果給定值等于根結(jié)點(diǎn)的關(guān)鍵碼，則搜索成功。如果給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹；否則。遞歸搜索根結(jié)點(diǎn)的右子樹?；舅枷耄簍emplate<classType>BstNode<Type>*BST<Type>::Find(Typex,BstNode<Type>*ptr)const{//二叉搜索樹的遞歸的搜索算法

if(ptr==NULL)returnNULL;//搜索失敗

elseif(x<ptr->data)//在左子樹搜索

return

Find(x,ptr->leftChild);

elseif(x>ptr->data)//在右子樹搜索

return

Find(x,ptr->rightChild);

elsereturnptr;

//相等,搜索成功

}template<classType>template<classType>BstNode<Type>*BST<Type>::Find(Typex,BstNode<Type>*ptr)const{//二叉搜索樹的迭代的搜索算法

if(ptr!=NULL){

BstNode<Type>*temp=ptr;//從根搜索

while(temp!=NULL){

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

if(temp->data<x)temp=temp->rightChild;

//右子樹

elsetemp=temp->leftChild;//左子樹

}

}returnNULL;//搜索失敗}template<classType>

二叉搜索樹的插入35154550402510203028插入新結(jié)點(diǎn)28二叉搜索樹的插入351545504025102030基本思想：為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。搜索成功:樹中已有這個(gè)元素,不再插入。搜索不成功:樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方?；舅枷耄簍emplate<classType>voidBST<Type>::

Insert

(Typex,BstNode<Type>*&ptr)

{

if(ptr==NULL) {//空二叉樹

ptr=newBstNode<Type>(x);//創(chuàng)建結(jié)點(diǎn)

if(ptr==NULL)

{cout<<“存儲(chǔ)不足"<<endl;exit(1);

}

}

elseif(x<ptr->data)//在左子樹插入

Insert(x,ptr->leftChild);

elseif(x>ptr->data)//在右子樹插入

Insert(x,ptr->rightChild);}

遞歸的二叉搜索樹插入算法template<classType>voidBST

輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}

，建立二叉搜索樹的過程535378537865537865175378658717537865091787537865811787095378651517870981輸入數(shù)據(jù){53,78,65,17,87,09template<classType>BST<Type>::BST(Typevalue){//輸入數(shù)據(jù),建立二叉搜索樹。RefValue是輸入//結(jié)束標(biāo)志。這個(gè)值應(yīng)取不可能在輸入序列中//出現(xiàn)的值,例如輸入序列的值都是正整數(shù)時(shí),//取RefValue為0或負(fù)數(shù)。

Typex;

root=NULL;RefValue=value;

cin>>x;

while(x!=RefValue)

{Insert(x,root);

cin>>x;

}}template<classType>二叉搜索樹的刪除在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新鏈接起來，同時(shí)確保二叉搜索樹的性質(zhì)不會(huì)失去。為保證在刪除后樹的搜索性能不至于降低，還需要防止重新鏈接后樹的高度增加。351545504025102030二叉搜索樹的刪除在二叉搜索樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，必須將因刪除結(jié)基本思想：首先查找，確定被刪除結(jié)點(diǎn)是否在二叉搜索樹中。分情況討論：

刪除葉結(jié)點(diǎn)：被刪結(jié)點(diǎn)右子樹或左子樹為空：可以拿它的左子女結(jié)點(diǎn)或右子女結(jié)點(diǎn)頂替它的位置，再釋放它。（刪除結(jié)點(diǎn)為ptr指針?biāo)福潆p親結(jié)點(diǎn)為f結(jié)點(diǎn)指針?biāo)?，被刪除結(jié)點(diǎn)的左子樹和右子樹分別用pl和pr表示）只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。基本思想：分情況討論：可以拿它的左子女結(jié)點(diǎn)或右子女結(jié)點(diǎn)頂替5378651787092345刪除45右子樹空,用左子女頂替5378651787092353788817940923刪除78左子樹空,用右子女頂替5394881709235378651787092345刪除45右子樹空,用左子女8853788117940945刪除782365538188179409452365被刪結(jié)點(diǎn)左、右子樹都不為空，？可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個(gè)結(jié)點(diǎn)的刪除問題。在右子樹上找中序下第一個(gè)結(jié)點(diǎn)填補(bǔ)8853788117940945刪除782365538188

二叉搜索樹的刪除算法template<classType>voidBST<Type>::Remove(constType&x,BstNode<Type>*&ptr){

BstNode<Type>*temp;

if(ptr!=NULL)

if(x<ptr->data)//在左子樹中刪除

Remove(x,ptr->leftChild);elseif(x>ptr->data)//在右子樹中刪除

Remove(x,ptr->rightChild);elseif(ptr->leftChild!=NULL&&

ptr->rightChild!=NULL){二叉搜索樹的刪除算法template<class

temp=Min(ptr->rightChild);

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

ptr->data=temp->data;//填補(bǔ)上

Remove(ptr->data,ptr->rightChild);

//在ptr的右子樹中刪除temp結(jié)點(diǎn)

}else{ //ptr結(jié)點(diǎn)只有一個(gè)或零個(gè)子女

temp=ptr; if(ptr->leftChild==NULL)ptr=ptr->rightChild;//只有右子女

elseif(ptr->rightChild==NULL)ptr=ptr->leftChild;//只有左子女

deletetemp; }}temp=Min(p同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉搜索樹的形態(tài)也不同。

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

如果輸入序列選的不好，會(huì)建立起一棵單支樹，使得二叉搜索樹的高度達(dá)到最大平衡處理122133132123123同樣3個(gè)數(shù)據(jù){1,2,3}，輸入順序不同，建立起7.3AVL樹AVL樹的定義

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

高度不平衡高度平衡ABCABCDEDE(高度平衡的二叉搜索樹)7.3AVL樹AVL樹的定義一棵AVL樹或者是空每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字,給出該結(jié)點(diǎn)右子樹的高度減去左子樹的高度所得的高度差,這個(gè)數(shù)字即為結(jié)點(diǎn)的平衡因子balance

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

高度不平衡高度平衡ABCABCDEDE3200001100每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字,給出該結(jié)點(diǎn)右子樹的高度減去左子樹的高關(guān)于AVL樹：AVL樹任一結(jié)點(diǎn)平衡因子只能取-1,0,1如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對值大于1,則這棵二叉搜索樹就失去了平衡,不再是AVL樹。如果一棵二叉搜索樹是高度平衡的,且有n個(gè)結(jié)點(diǎn)，其高度可保持在O(log2n),平均搜索長度也可保持在O(log2n)。ABCDE1100關(guān)于AVL樹：ABCDE1100AVL樹的類定義template<classType>classAVLTree{public:

structAVLNode{ //AVL樹結(jié)點(diǎn)

Typedata;intbalance;AVLNode<Type>*left,*right;AVLNode():

left(NULL),right(NULL),balance(0)

{}AVLNode(Typed,AVLNode<Type>*l=NULL,AVLNode<Type>*r=NULL)

:data(d),left(l),right(r),balance(0){}};AVL樹的類定義template<classType>protected:

TypeRefValue;

AVLNode*root;

intInsert(AVLNode<Type>*&Tree,Typex);

voidRotateLeft(AVLNode<Type>*Tree,AVLNode<Type>*&NewTree);

voidRotateRight(AVLNode<Type>*Tree,AVLNode<Type>*&NewTree);

voidLeftBalance(AVLNode<Type>*&Tree);

voidRightBalance(AVLNode<Type>*&Tree);intHeight(AVLNode<Type>*t)const;

public:protected:

AVLTree():root(NULL){}

AVLNode(TypeRef):RefValue(Ref),root(NULL){}

intInsert(Typex)

{returnInsert(root,x);}

friendistream&operator>>(istream&in,AVLTree<Type>&Tree);

friendostream&operator<<(ostream&out,

constAVLTree<Type>&Tree);

intHeight()const;}AVLTree():root(NULL)平衡化旋轉(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)的平衡因子。平衡化旋轉(zhuǎn)有兩類：如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起，沿剛才回溯的路徑取直接下兩層的結(jié)點(diǎn)。如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。12如果在某一結(jié)點(diǎn)發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點(diǎn)起右單旋轉(zhuǎn)(RotateRight)h插入BACEDhhh-1h-2-1-1hhh-1h-1ABDCE-100hhh-1BCEAD-100h右單旋轉(zhuǎn)(RotateRight)h插入BACEDhhh如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。hhACEDh-1h-1BFG-100先左后右EGACDBFhhh-1h1-1-2插入如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)FGDhAh-1CEB00-1hh右單旋轉(zhuǎn)AEhhCDh-1hBFG0-2-2插入hhACEDh-1h-1BFG-100E左單旋轉(zhuǎn)GACDBFhhh-1h