数据结构7搜索结构.ppt

《数据结构7搜索结构.ppt》由会员分享，可在线阅读，更多相关《数据结构7搜索结构.ppt（74页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第七章第七章 搜索结构搜索结构本章要点：静态搜索表的顺序搜索与折半搜索 二叉搜索树的表示、搜索、插入、删除算法 AVL树的平衡化及相应算法静态搜索表静态搜索表搜索搜索(Search)的概念的概念n n所谓所谓搜索搜索，就是，就是在数据集合中寻找满足某种条在数据集合中寻找满足某种条 件的数据对象。件的数据对象。n n 搜索的结果通常有两种可能：搜索的结果通常有两种可能：uu 搜索成功搜索成功，即找到满足条件的数据对象。这，即找到满足条件的数据对象。这uu 时，作为结果，可报告该对象在结构中的位时，作为结果，可报告该对象在结构中的位uu 置，还可进一步给出该对象中的具体信息。置，还可进一步给出该对

2、象中的具体信息。uu 搜索不成功搜索不成功，或搜索失败。作为结果，也应，或搜索失败。作为结果，也应uu 报告一些信息，如失败标志、失败位置等。报告一些信息，如失败标志、失败位置等。通常称用于搜索的数据集合为通常称用于搜索的数据集合为搜索结构搜索结构，它是，它是由由同一数据类型的对象同一数据类型的对象(或记录或记录)组成。组成。在每一个对象中有若干属性，其中应当有一个属性，在每一个对象中有若干属性，其中应当有一个属性，在每一个对象中有若干属性，其中应当有一个属性，在每一个对象中有若干属性，其中应当有一个属性，其值可唯一地标识这个对象。它称为关键码。其值可唯一地标识这个对象。它称为关键码。其值可唯

3、一地标识这个对象。它称为关键码。其值可唯一地标识这个对象。它称为关键码。使用基使用基使用基使用基于关键码的搜索，搜索结果应是唯一的。于关键码的搜索，搜索结果应是唯一的。于关键码的搜索，搜索结果应是唯一的。于关键码的搜索，搜索结果应是唯一的。但在实际应但在实际应但在实际应但在实际应用时，搜索条件是多方面的，这样，可以用时，搜索条件是多方面的，这样，可以用时，搜索条件是多方面的，这样，可以用时，搜索条件是多方面的，这样，可以使用基于属使用基于属使用基于属使用基于属性的搜索方法，但搜索结果可能不唯一性的搜索方法，但搜索结果可能不唯一性的搜索方法，但搜索结果可能不唯一性的搜索方法，但搜索结果可能不唯一

4、。实施搜索时有两种不同的环境。实施搜索时有两种不同的环境。实施搜索时有两种不同的环境。实施搜索时有两种不同的环境。静态环境静态环境，搜索结构在执行插入和删除等操作，搜索结构在执行插入和删除等操作的前后不发生改变。的前后不发生改变。静态搜索表静态搜索表 动态环境动态环境，为保持较高的搜索效率，搜索结构，为保持较高的搜索效率，搜索结构在执行插入和删除等操作的前后将自动进行调在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。整，结构可能发生变化。动态搜索表动态搜索表动态搜索表动态搜索表静态搜索表结构静态搜索表结构template class dataList;template class

5、 Node friend class dataList;public:Node(const Type&value):key(value)Type getKey()const return key;void setKey(Type k)key=k;private:Type key;other;template class dataList public:dataList(int sz=10):ArraySize(sz),Element(new Node sz)virtual dataList()delete Element;friend ostream&operator (ostream&Out

6、Stream,const dataList&OutList);friend istream&operator (istream&InStream,dataList&InList);protected:Type*Element;int ArraySize,CurrentSize;template class searchList:public dataList/作为派生类的静态搜索表的类定义作为派生类的静态搜索表的类定义public:searchList(int sz=10):dataList(sz)virtual searchList()virtual int Search(const Typ

7、e&x)const;template istream&operator (istream&InStream,dataList&InList)/从输入流对象从输入流对象InStream输入数据到数据表输入数据到数据表InList cout InList.CurrentSize;cout “输入数组元素值输入数组元素值输入数组元素值输入数组元素值:n”;for(int i=0;i InList.CurrentSize;i+)cout “元素元素元素元素”i InList.Elementi;return InStream;template ostream&operator(ostream&OutSt

8、ream,const dataList&OutList)/将数据表将数据表OutList内容输出到输出流对象内容输出到输出流对象OutStream OutStream “数组内容数组内容数组内容数组内容 :n”;for(int i=0;i OutList.CurrentSize;i+)OutStream OutList.Elementi ;OutStream endl;OutStream “数组当前大小数组当前大小数组当前大小数组当前大小:”OutList.CurrentSize endl;return OutStream;衡量一个搜索算法的时间效率的标准是：衡量一个搜索算法的时间效率的标准是

9、：在搜索在搜索过程中关键码的平均比较次数或平均读写磁盘次过程中关键码的平均比较次数或平均读写磁盘次数数(只适合于外部搜索只适合于外部搜索)，这个标准也称为，这个标准也称为平均搜平均搜索长度索长度ASL(Average Search Length)，通常它是，通常它是搜索结构中对象总数搜索结构中对象总数m 或文件结构中物理块总数或文件结构中物理块总数 n 的函数的函数。另外衡量一个搜索算法还要考虑算法所需要的存另外衡量一个搜索算法还要考虑算法所需要的存储量和算法的复杂性等问题。储量和算法的复杂性等问题。在静态搜索表中，数据对象存放于数组中，在静态搜索表中，数据对象存放于数组中，利用数组元素的下标

10、作为数据对象的存放地址。利用数组元素的下标作为数据对象的存放地址。搜索算法搜索算法根据给定值根据给定值x，在数组中进行搜索，在数组中进行搜索。直。直到找到到找到x在数组中的存放位置或可确定在数组中在数组中的存放位置或可确定在数组中找不到找不到x为止。为止。顺序搜索顺序搜索(Sequential Search)所谓顺序搜索，又称线性搜索，主要用所谓顺序搜索，又称线性搜索，主要用于在线性结构中进行搜索。于在线性结构中进行搜索。设若表中有设若表中有 CurrentSize 个对象，则顺序个对象，则顺序搜索从表的先端开始，顺序用各对象的关键搜索从表的先端开始，顺序用各对象的关键码与给定值码与给定值x进

11、行比较，直到找到与其值相进行比较，直到找到与其值相等的对象，则搜索成功，给出该对象在表中等的对象，则搜索成功，给出该对象在表中的位置。的位置。若整个表都已检测完仍未找到关键码与若整个表都已检测完仍未找到关键码与x相等的对象，则搜索失败。给出失败信息。相等的对象，则搜索失败。给出失败信息。template int searchList:Search(const Type&x)const/顺序搜索的迭代算法，顺序搜索的迭代算法，顺序搜索的迭代算法，顺序搜索的迭代算法，0 0号元素为监视哨号元素为监视哨号元素为监视哨号元素为监视哨 Element0.setKey(x);int i=CurrentSi

12、ze;while(Elementi.getKey()!=x)i-;return i;template int earchList:Search(const Type&x,int&loc)const/顺序搜索的递归算法顺序搜索的递归算法顺序搜索的递归算法顺序搜索的递归算法 if(loc=CurrentSize)return-1;else if(Elementloc.getKey()=x)return loc;else return Search(x,loc+1);const int Size=10;main()/顺序搜索的主过程顺序搜索的主过程顺序搜索的主过程顺序搜索的主过程searchList

13、 List1(Size);float Target;int Location;cin List1;cout List1;/输入输入输入输入/输出数据表输出数据表输出数据表输出数据表List1 cout Target;if(Location=List1.search(Target)!=0)cout “找到下标找到下标”Location endl;else cout()x x，把搜索区间缩小到，把搜索区间缩小到，把搜索区间缩小到，把搜索区间缩小到表的表的表的表的前半部分前半部分前半部分前半部分，再继续进行对分搜索；，再继续进行对分搜索；，再继续进行对分搜索；，再继续进行对分搜索；ElementEl

14、ement midmid.getKeygetKey()()x x，把搜索区间缩小到，把搜索区间缩小到，把搜索区间缩小到，把搜索区间缩小到表的表的表的表的后半部分后半部分后半部分后半部分，再继续进行对分搜索。，再继续进行对分搜索。，再继续进行对分搜索。，再继续进行对分搜索。每比较一次，搜索区间缩小一半。如果搜索区间已每比较一次，搜索区间缩小一半。如果搜索区间已每比较一次，搜索区间缩小一半。如果搜索区间已每比较一次，搜索区间缩小一半。如果搜索区间已缩小到一个对象，仍未找到想要搜索的对象，则搜缩小到一个对象，仍未找到想要搜索的对象，则搜缩小到一个对象，仍未找到想要搜索的对象，则搜缩小到一个对象，仍未

15、找到想要搜索的对象，则搜索失败。索失败。索失败。索失败。template class orderedList:public dataList /有序表的类定义有序表的类定义,继承了数据表继承了数据表public:orderedList(int sz=10):dataList(sz)virtual orderedList()virtual int Search(const Type&x)const;template int orderedList:BinarySearch(const Type&x,const int low,const int high)const/折半搜索的递归算法折半搜索的

16、递归算法折半搜索的递归算法折半搜索的递归算法 int mid=-1;if(low=high)mid=(low+high)/2;if(Elementmid.getKey()x)mid=BinarySearch(x,low,mid-1);return mid;template in orderedList:BinarySearch(const Type&x)const /折半搜索的迭代算法折半搜索的迭代算法折半搜索的迭代算法折半搜索的迭代算法 int high=CurrentSize-1,low=0,mid;while(low=high)mid=(low+high)/2;if(Elementmid

17、.getKey()x)high=mid-1;else return mid;return-1;从有序表构造出的二叉搜索树(判定树)n n若设若设若设若设 n n=2=2h h-1-1，则描述对分搜索的二叉搜索树是，则描述对分搜索的二叉搜索树是，则描述对分搜索的二叉搜索树是，则描述对分搜索的二叉搜索树是高度为高度为高度为高度为 h h-1-1 的满二叉树。的满二叉树。的满二叉树。的满二叉树。2 2h h=n n+1+1,h h=log=log2 2(n n+1)+1)。n n 第第第第0 0层结点有层结点有层结点有层结点有1 1个，搜索第个，搜索第个，搜索第个，搜索第0 0层结点要比较层结点要比

18、较层结点要比较层结点要比较1 1次；次；次；次；第第第第1 1层结点有层结点有层结点有层结点有2 2个，搜索第个，搜索第个，搜索第个，搜索第1 1层结点要比较层结点要比较层结点要比较层结点要比较2 2次；次；次；次；，第第第第 i i(0(0 i i h h)层结点有层结点有层结点有层结点有 2 2i i 个，搜索第个，搜索第个，搜索第个，搜索第 i i 层结点要比较层结点要比较层结点要比较层结点要比较 i i+1+1次，次，次，次，。假定每个结点的搜索概率相等，即。假定每个结点的搜索概率相等，即。假定每个结点的搜索概率相等，即。假定每个结点的搜索概率相等，即p pi i =1/=1/n n，

19、则，则，则，则搜索成功的平均搜索长度为搜索成功的平均搜索长度为搜索成功的平均搜索长度为搜索成功的平均搜索长度为二叉搜索树二叉搜索树(Binary Search Tree)二叉搜索树或者是一棵空树，或者是具有下二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：列性质的二叉树：每个结点都有一个作为搜索依据的关键每个结点都有一个作为搜索依据的关键码码(key)，所有结点的关键码互不相同。，所有结点的关键码互不相同。左子树左子树(如果存在如果存在)上所有结点的关键码上所有结点的关键码都小于根结点的关键码。都小于根结点的关键码。右子树右子树(如果存在如果存在)上所有结点的关键码上所有结点的关键码都大

20、于根结点的关键码。都大于根结点的关键码。左子树和右子树也是二叉搜索树。左子树和右子树也是二叉搜索树。如果对一棵二叉搜索树进行中序遍如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树关键码排列起来，所以也称二叉搜索树为二叉排序树为二叉排序树。二叉搜索树的类定义二叉搜索树的类定义二叉搜索树的类定义二叉搜索树的类定义#include template class BST;template Class BstNode:public BinTreeNode /二叉搜索树结点类二叉搜索树结点类二叉搜索树结点类二叉搜索树结点类

21、friend class BST;public:BstNode():leftChild(NULL),BstNode(const Type d):data(d),rightChild(NULL),BstNode(const Type d=0,BstNode*L=NULL,BstNode*R=NULL):data(d),leftChild(L),rightChild(R)BstNode()protected:Type data;BstNode*leftChild,*rightChild;template class BST:public:BinaryTree private:BstNode*roo

22、t;/二叉搜索树的根指针二叉搜索树的根指针二叉搜索树的根指针二叉搜索树的根指针 Type RefValue;/数据输入停止的标志数据输入停止的标志数据输入停止的标志数据输入停止的标志 BstNode*lastfound;/最近搜索到的结点的指针最近搜索到的结点的指针最近搜索到的结点的指针最近搜索到的结点的指针 void MakeEmpty(BstNode*&ptr);void Insert(const Type&x,BstNode*&ptr);/插入插入插入插入 void Remove(const Type&x,BstNode*&ptr);/删除删除删除删除 void PrintTree(Bs

23、tNode*ptr)const;BstNode*Copy (const BstNode*ptr);/复制复制复制复制 BstNode*Find(const Type&x,BstNode*ptr)const;/搜索搜索搜索搜索 BstNode*Min(BstNode*ptr)const;/求最小求最小求最小求最小 BstNode*Max(BstNode*ptr)const;/求最大求最大求最大求最大 friend class BSTIterator;/中序游标类中序游标类中序游标类中序游标类public:BST():root(NULL)BST(Type value):RefValue(value

24、),root(NULL)BST();const BST&operator=(const BST&Value);void MakeEmpty()MakeEmpty();root=NULL;void PrintTree()const PrintTree(root);int Find(const Type&x)const return Find(x,root)!=NULL;Type Min()return Min(root)data;Type Max()return Max(root)data;void Insert(const Type&x)Insert(x,root);void Remove(c

25、onst Type&x)Remove(x,root);二叉搜索树上的搜索二叉搜索树上的搜索在二叉搜索树上进行搜索，在二叉搜索树上进行搜索，在二叉搜索树上进行搜索，在二叉搜索树上进行搜索，是一个从根结点开始，是一个从根结点开始，是一个从根结点开始，是一个从根结点开始，沿某沿某沿某沿某一个分支逐层向下进行比较判一个分支逐层向下进行比较判一个分支逐层向下进行比较判一个分支逐层向下进行比较判等的过程等的过程等的过程等的过程。它。它。它。它可以是一个递归的过程。可以是一个递归的过程。可以是一个递归的过程。可以是一个递归的过程。假设想要在二叉搜索树中搜索关键码为假设想要在二叉搜索树中搜索关键码为假设想要在

26、二叉搜索树中搜索关键码为假设想要在二叉搜索树中搜索关键码为x x的元素，的元素，的元素，的元素，搜索过程从根结点开始。如果根指针为搜索过程从根结点开始。如果根指针为搜索过程从根结点开始。如果根指针为搜索过程从根结点开始。如果根指针为NULLNULL，则搜索不成功；否则用给定值则搜索不成功；否则用给定值则搜索不成功；否则用给定值则搜索不成功；否则用给定值x x与根结点的关键与根结点的关键与根结点的关键与根结点的关键码进行比较：码进行比较：码进行比较：码进行比较：如果给定值等于根结点的关键码，则搜索成功。如果给定值等于根结点的关键码，则搜索成功。如果给定值等于根结点的关键码，则搜索成功。如果给定值

27、等于根结点的关键码，则搜索成功。如果给定值小于根结点的关键码，则继续递归搜如果给定值小于根结点的关键码，则继续递归搜如果给定值小于根结点的关键码，则继续递归搜如果给定值小于根结点的关键码，则继续递归搜索根结点的左子树；索根结点的左子树；索根结点的左子树；索根结点的左子树；否则。递归搜索根结点的右子树。否则。递归搜索根结点的右子树。否则。递归搜索根结点的右子树。否则。递归搜索根结点的右子树。template BstNode*BST:Find (const Type&x,BstNode*ptr)const/二叉搜索树的递归的搜索算法二叉搜索树的递归的搜索算法二叉搜索树的递归的搜索算法二叉搜索树的递

28、归的搜索算法 if(ptr=NULL)return NULL;/搜索失败搜索失败搜索失败搜索失败 else if(x ptrdata)/在右子树递归搜索在右子树递归搜索在右子树递归搜索在右子树递归搜索 return Find(x,ptrrightChild);else return ptr;/相等相等相等相等,搜索成功搜索成功搜索成功搜索成功template BstNode *BST :Find (const Type&x,BstNode*ptr)const/二叉搜索树的迭代的搜索算法二叉搜索树的迭代的搜索算法二叉搜索树的迭代的搜索算法二叉搜索树的迭代的搜索算法 if(ptr!=NULL)Bs

29、tNode*temp=ptr;while(temp!=NULL)if(tempdata=x)return temp;/成功成功成功成功 if(tempdata x)temp=temprightChild;/右子树右子树右子树右子树 else temp=templeftChild;/左子树左子树左子树左子树 return NULL;/搜索失败搜索失败搜索失败搜索失败 每次结点的插入，都要从根结点出发搜索插每次结点的插入，都要从根结点出发搜索插每次结点的插入，都要从根结点出发搜索插每次结点的插入，都要从根结点出发搜索插入位置，然后把新结点作为叶结点插入。入位置，然后把新结点作为叶结点插入。入位置，

30、然后把新结点作为叶结点插入。入位置，然后把新结点作为叶结点插入。二叉搜索树的插入二叉搜索树的插入为了向二叉搜索树中插入一个新元素，必须为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。先检查这个元素是否在树中已经存在。在插入之前，先使用搜索算法在树中检查要在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。插入元素有还是没有。搜索成功搜索成功:树中已有这个元素，不再插树中已有这个元素，不再插入。入。搜索不成功搜索不成功:树中原来没有关键码等于树中原来没有关键码等于给定值的结点，把新元素加到搜索操作给定值的结点，把新元素加到搜索操作停止的地方。停止的地方。templa

31、te void BST:Insert(const Type&x,BstNode*&ptr)/递归的二叉搜索树插入算法递归的二叉搜索树插入算法递归的二叉搜索树插入算法递归的二叉搜索树插入算法 if(ptr=NULL)/空二叉树空二叉树空二叉树空二叉树 ptr=new BstNode(x);/创建含创建含创建含创建含 x x 结点结点结点结点 if(ptr=NULL)cout Out of space endl;exit(1);else if(x ptrdata)/在右子树插入在右子树插入在右子树插入在右子树插入 Insert(x,ptrrightChild);输入数据，建立二叉搜索树的过程输入数

32、据序列输入数据序列输入数据序列输入数据序列 53,78,65,17,87,09,81,45,23 53,78,65,17,87,09,81,45,23 template BST:BST(Type value)/输入数据，建立二叉搜索树的算法输入数据，建立二叉搜索树的算法输入数据，建立二叉搜索树的算法输入数据，建立二叉搜索树的算法,RefValueRefValue是是是是/输入结束标志输入结束标志输入结束标志输入结束标志 Type&x;root=NULL;RefValue=value;cin x;while(x.key!=RefValue)Insert(x,root);cin x;从空树开始建树

33、，输入序列以输入一个结束标志从空树开始建树，输入序列以输入一个结束标志从空树开始建树，输入序列以输入一个结束标志从空树开始建树，输入序列以输入一个结束标志valuevalue结束。这个值应当取不可能在输入序列中出现结束。这个值应当取不可能在输入序列中出现结束。这个值应当取不可能在输入序列中出现结束。这个值应当取不可能在输入序列中出现的值，例如输入序列的值都是正整数时，取的值，例如输入序列的值都是正整数时，取的值，例如输入序列的值都是正整数时，取的值，例如输入序列的值都是正整数时，取RefValueRefValue为为为为0 0或负数。或负数。或负数。或负数。同样同样同样同样 3 3 个数据个数

34、据个数据个数据 1,2,3 1,2,3 ，输入顺序不同，建立起来，输入顺序不同，建立起来，输入顺序不同，建立起来，输入顺序不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉的二叉搜索树的形态也不同。这直接影响到二叉的二叉搜索树的形态也不同。这直接影响到二叉的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。搜索树的搜索性能。搜索树的搜索性能。搜索树的搜索性能。如果输入序列选得不好，会建立起一棵单支树，如果输入序列选得不好，会建立起一棵单支树，如果输入序列选得不好，会建立起一棵单支树，如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大，这样必然会降使得二叉搜索树

35、的高度达到最大，这样必然会降使得二叉搜索树的高度达到最大，这样必然会降使得二叉搜索树的高度达到最大，这样必然会降低搜索性能。低搜索性能。低搜索性能。低搜索性能。2,1,3 2,1,3 1,2,3 1,3,2 2,3,1 3,1,2 3,2,11,2,3 1,3,2 2,3,1 3,1,2 3,2,1 123111122223333二叉搜索树的删除二叉搜索树的删除 在二叉搜索树中删除一个结点时，必须将因删除在二叉搜索树中删除一个结点时，必须将因删除在二叉搜索树中删除一个结点时，必须将因删除在二叉搜索树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉结点而断开的二叉链表

36、重新链接起来，同时确保二叉结点而断开的二叉链表重新链接起来，同时确保二叉结点而断开的二叉链表重新链接起来，同时确保二叉搜索树的性质不会失去。搜索树的性质不会失去。搜索树的性质不会失去。搜索树的性质不会失去。为保证在执行删除后，树的搜索性能不至于降低，为保证在执行删除后，树的搜索性能不至于降低，为保证在执行删除后，树的搜索性能不至于降低，为保证在执行删除后，树的搜索性能不至于降低，还需要防止重新链接后树的高度增加。还需要防止重新链接后树的高度增加。还需要防止重新链接后树的高度增加。还需要防止重新链接后树的高度增加。删除叶结点删除叶结点，只需将其双亲结点指向它的指针，只需将其双亲结点指向它的指针清

37、零，再释放它即可。清零，再释放它即可。被删结点缺右子树被删结点缺右子树，可以拿它的左子女结点顶，可以拿它的左子女结点顶替它的位置，再释放它。替它的位置，再释放它。被删结点缺左子树被删结点缺左子树，可以拿它的右子女结点顶，可以拿它的右子女结点顶替它的位置，再释放它。替它的位置，再释放它。被删结点左、右子树都存在被删结点左、右子树都存在，可以在它的右，可以在它的右子树中寻找中序下的第一个结点子树中寻找中序下的第一个结点(关键码最小关键码最小),),用它的值填补到被删结点中，再来处理这用它的值填补到被删结点中，再来处理这个结点的删除问题。个结点的删除问题。二叉搜索树的删除算法二叉搜索树的删除算法te

38、mplate void BST:Remove(const Type&x,BstNode*&ptr)BstNode*temp;if(ptr!=NULL)if(x ptrdata)Remove(x,ptrrightChild);else if(ptrleftChild!=NULL&ptrrightChild!=NULL)temp=Min(ptrrightChild);ptrdata=tempdata;Remove(ptrdata,temp);else temp=ptr;if(ptrleftChild=NULL)ptr=ptrrightChild;else if(ptrrightChild=NULL

39、)ptr=ptrleftChild;delete temp;最优二叉搜索树最优二叉搜索树对于有对于有对于有对于有 n n 个关键码的集合，其关键码有个关键码的集合，其关键码有个关键码的集合，其关键码有个关键码的集合，其关键码有 n n!种不同的排种不同的排种不同的排种不同的排列，可构成的不同二叉搜索树有列，可构成的不同二叉搜索树有列，可构成的不同二叉搜索树有列，可构成的不同二叉搜索树有 (棵棵棵棵)如何评价这些二叉搜索树，可以用树的搜索效率来衡如何评价这些二叉搜索树，可以用树的搜索效率来衡如何评价这些二叉搜索树，可以用树的搜索效率来衡如何评价这些二叉搜索树，可以用树的搜索效率来衡量。量。量。量

40、。例如，已知关键码集合例如，已知关键码集合例如，已知关键码集合例如，已知关键码集合 a1,a2,a3 a1,a2,a3 =do,if,to do,if,to ，对，对，对，对应搜索概率为应搜索概率为应搜索概率为应搜索概率为 p1=0.5p1=0.5,p2=0.1p2=0.1,p3=0.05p3=0.05,在各个搜索不在各个搜索不在各个搜索不在各个搜索不成功的间隔内搜索概率又分别为成功的间隔内搜索概率又分别为成功的间隔内搜索概率又分别为成功的间隔内搜索概率又分别为 q0=0.15q0=0.15,q1=0.1q1=0.1,q2=0.05q2=0.05,q3=0.05q3=0.05。可能的二叉搜索树

41、如下所示。可能的二叉搜索树如下所示。可能的二叉搜索树如下所示。可能的二叉搜索树如下所示。3个结点的5种不同的（扩充）二叉树在扩充二叉搜索树中在扩充二叉搜索树中在扩充二叉搜索树中在扩充二叉搜索树中 表示内部结点表示内部结点表示内部结点表示内部结点，包含了关键码集合中的某一个，包含了关键码集合中的某一个，包含了关键码集合中的某一个，包含了关键码集合中的某一个关键码；关键码；关键码；关键码；表示外部结点表示外部结点表示外部结点表示外部结点，代表造成搜索失败的各关键码，代表造成搜索失败的各关键码，代表造成搜索失败的各关键码，代表造成搜索失败的各关键码间隔中的不在关键码集合中的关键码。间隔中的不在关键码

42、集合中的关键码。间隔中的不在关键码集合中的关键码。间隔中的不在关键码集合中的关键码。在每两个外部结点之间必然存在一个内部结点在每两个外部结点之间必然存在一个内部结点在每两个外部结点之间必然存在一个内部结点在每两个外部结点之间必然存在一个内部结点。设二叉树的内部结点有设二叉树的内部结点有设二叉树的内部结点有设二叉树的内部结点有 n n 个，外部结点有个，外部结点有个，外部结点有个，外部结点有 n n+1+1 个。个。个。个。如果定义每个结点的路径长度为该结点的层次，如果定义每个结点的路径长度为该结点的层次，如果定义每个结点的路径长度为该结点的层次，如果定义每个结点的路径长度为该结点的层次，并用并

43、用并用并用 I I 表示所有表示所有表示所有表示所有 n n 个内部结点的路径长度之和个内部结点的路径长度之和个内部结点的路径长度之和个内部结点的路径长度之和，用，用，用，用 E E 表示表示表示表示 n n+1+1 个外部结点的路径长度之和个外部结点的路径长度之和个外部结点的路径长度之和个外部结点的路径长度之和，可以用归，可以用归，可以用归，可以用归纳法证明，纳法证明，纳法证明，纳法证明，E E=I I+2+2n n。一棵扩充二叉搜索树的一棵扩充二叉搜索树的一棵扩充二叉搜索树的一棵扩充二叉搜索树的搜索成功的平均查找长搜索成功的平均查找长搜索成功的平均查找长搜索成功的平均查找长度度度度ASLA

44、SLsuccsucc可以定义为可以定义为可以定义为可以定义为该树所有内部结点上的权值该树所有内部结点上的权值该树所有内部结点上的权值该树所有内部结点上的权值ppi i 与搜索该结点时所需的与搜索该结点时所需的与搜索该结点时所需的与搜索该结点时所需的关键码比较次数关键码比较次数关键码比较次数关键码比较次数 c c i i (=(=l l i i+1)+1)乘积之和：乘积之和：乘积之和：乘积之和：扩充二叉搜索树扩充二叉搜索树扩充二叉搜索树扩充二叉搜索树搜索不成功的平均搜索长度搜索不成功的平均搜索长度搜索不成功的平均搜索长度搜索不成功的平均搜索长度ASLASLunsuccunsucc为树中所有外部结

45、点上权值为树中所有外部结点上权值为树中所有外部结点上权值为树中所有外部结点上权值qqj j 与到达外部与到达外部与到达外部与到达外部结点所需关键码比较次数结点所需关键码比较次数结点所需关键码比较次数结点所需关键码比较次数c c j j(=(=l l j j)乘积之和：乘积之和：乘积之和：乘积之和：扩充二叉搜索树总的平均搜索长度为：扩充二叉搜索树总的平均搜索长度为：ASL=ASLsucc+ASLunsucc 所有内、外部结点上的权值关系为所有内、外部结点上的权值关系为(1)相等搜索概率的情形相等搜索概率的情形若设树中所有内、外部结点的搜索概率都相等：若设树中所有内、外部结点的搜索概率都相等：若设

46、树中所有内、外部结点的搜索概率都相等：若设树中所有内、外部结点的搜索概率都相等：ppi i=q=qj j=1/7=1/7，1 1 i i 3,0 3,0 j j 3 3 图图图图(a)(a)：ASLASLsuccsucc=1/7*3+1/7*2+1/7*1=6/7,=1/7*3+1/7*2+1/7*1=6/7,ASLASLunsuccunsucc=1/7*3*2+1/7*2+1/7*1=9/7=1/7*3*2+1/7*2+1/7*1=9/7。总平均搜索长度总平均搜索长度总平均搜索长度总平均搜索长度 ASLASL=6/7+9/7=15/7=6/7+9/7=15/7。图图图图(a)(a)：ASLA

47、SL=15/7 =15/7 图图图图(d)(d)：ASLASL=15/7=15/7 图图图图(b)(b)：ASLASL=13/7 =13/7 图图图图(e)(e)：ASLASL=15/7=15/7 图图图图(c)(c)：ASLASL=15/7=15/7 图图图图(b)(b)的情形所得的平均搜索长度最小。一般把平均的情形所得的平均搜索长度最小。一般把平均的情形所得的平均搜索长度最小。一般把平均的情形所得的平均搜索长度最小。一般把平均搜索长度达到最小的扩充二叉搜索树称作最优二叉搜搜索长度达到最小的扩充二叉搜索树称作最优二叉搜搜索长度达到最小的扩充二叉搜索树称作最优二叉搜搜索长度达到最小的扩充二叉搜

48、索树称作最优二叉搜索树，索树，索树，索树，在相等搜索概率的情形下，因为所有内部结点、外在相等搜索概率的情形下，因为所有内部结点、外在相等搜索概率的情形下，因为所有内部结点、外在相等搜索概率的情形下，因为所有内部结点、外部结点的搜索概率都相等，把它们的权值都视为部结点的搜索概率都相等，把它们的权值都视为部结点的搜索概率都相等，把它们的权值都视为部结点的搜索概率都相等，把它们的权值都视为 1 1。同时，第同时，第同时，第同时，第 k k 层有层有层有层有 2 2k k 个结点，个结点，个结点，个结点，k k=0,1,=0,1,。则有。则有。则有。则有 n n 个个个个内部结点的扩充二叉搜索树的内部

49、路径长度内部结点的扩充二叉搜索树的内部路径长度内部结点的扩充二叉搜索树的内部路径长度内部结点的扩充二叉搜索树的内部路径长度 I I 至少至少至少至少等于序列等于序列等于序列等于序列 0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,的前的前的前的前n n项的和。项的和。项的和。项的和。因此，最优二叉搜索树的搜索成功的平均搜索长因此，最优二叉搜索树的搜索成功的平均搜索长因此，最优二叉搜索树的搜索成功的平均搜索长因此，最优二叉搜索树的搜索成功的平均搜索长度和搜索不成功的平均搜索长度分别为度和搜索不成功的平均搜索长

50、度分别为度和搜索不成功的平均搜索长度分别为度和搜索不成功的平均搜索长度分别为:(2)不相等搜索概率的情形不相等搜索概率的情形设树中所有内、外部结点的搜索概率互不相等，设树中所有内、外部结点的搜索概率互不相等，设树中所有内、外部结点的搜索概率互不相等，设树中所有内、外部结点的搜索概率互不相等，p1=0.5p1=0.5，p2=0.1p2=0.1，p3=0.05p3=0.05 q0=0.15 q0=0.15，q1=0.1q1=0.1，q2=0.05q2=0.05，q3=0.05q3=0.05 图图图图(a)(a)：ASLASLsuccsucc=0.5*3+0.1*2+0.05*1=1.75=0.5*