《计算机算法设计与分析-Chapter4数据集合上的搜索(Searching)算法》由会员分享，可在线阅读，更多相关《计算机算法设计与分析-Chapter4数据集合上的搜索(Searching)算法（105页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析,Chapter4.数据集合上的搜索(Searching)算法,4.1动态数据集(DynamicSet)与抽象数据类型(ADT)4.2二叉搜索树(BinarySearchTrees)4.3随机二叉搜索树(RandomlyBuiltBinarySearchTree)4.4红黑树(Red-BlackTree)4.52-3-4树4.6Hashing技术,4.1动态数据集(DynamicSet)与抽象数据类型(ADT),静态数据集（StaticSet）中的数据是固定不变的。动态数据集（DynamicSet）则是由不断变动的同类型数据元素组成的数据集合。动态数据集（DynamicSe
2、t）可以表示为一个数据元素的数组：classDynamicSetintsetSize;ObjectelementssetSize;./Object为数据元素的类型，setSize为当前集合中的元素个数,用数组表示集合操作方便，但当集合中的元素个数不断增加时，数组的长度必须扩大。一般采用空间倍增（arraydoubling）技术，即另外申请一个加倍长度的新数组，把集合中的数据传送过来，取代原有的空间。其过程为：arrayDouble(set)newSize=2*arraySize;newElements=newObject(newSize);Transferallelementsfromthes
3、et.elementstothenewElement;set.elements=newElements;set.setSize=newSize;更为灵活的存储形式是利用指针和链表（例如线性链表和树结构），这种存储形式在搜索算法中经常用到。,搜索问题：在集合中检索出其关键字域的值等于给定值的数据元素。已知：动态数据集类型DynamicSet的一个实例set和值x。求：集合set中一个元素Objectelement，使element.key=x。数据集合上的操作（operation）可以分为两类：.查询（queries）操作：对数据集不做任何变动，仅仅返回有关集合的某些信息；.修改（modifyi
4、ngoperations）操作：要对数据集合的某些域进行改动。一些典型的操作：.Search(S,k)：搜索，一个查询操作。对于给定的数据集合S和一个关键字值k，返回S中一个元素（element）的指针x，使得x-key=k。当S中没有符合条件的元素时，返回的指针为空（NULL）。,.Insert(S,x)：插入，一个修改操作。把由x指向的数据元素加入到集合S中，一般假定在x指向的数据元中，与集合运算相关的所有分量（域）都已经初始化。.Delete(S,x)：删除，一个修改操作。给定指向集合S中一个元素的指针x，将此元素从S中删除。.Minimum(S)：求最小元，一个查询操作。若集合S中所有
5、数据元素的关键字值为一全序集，则返回具有最小关键字值的数据元素的指针。.Maximum(S)：求最大元，一个查询操作。返回具有最大关键字值的数据元素的指针。.Deletemin(S)：删除最小元，一个修改操作。它相当于Minimum(S)和Delete(S,x)的联合，即：Delete(S,Minimum(S)。,.Successor(S,x)：求后继数据元，一个查询操作。若S中的数据元素按关键字值从小到大排列，x是指向S中某一数据元素的指针，则返回x所指向的数据元素的下一个数据元素的指针。若x指向最后一个数据元素，则返回NULL。.Predecessor(S,x)：求前导数据元，一个查询操作
6、。返回x所指向的数据元素的前一个数据元素的指针。若x指向第一个数据元素，则返回NULL。搜索算法（及相关操作算法）的设计实际上是实现适合各种不同应用需要的ADT，例如：字典（Dictionary）作为抽象数据类型，可以分为两类：静态字典：（静态数据集S，Search）；动态字典：（动态数据集S，Search，Insert，Delete）。优先队列（PriorityQueue）：（动态数据集S，Insert，Deletemin）。,4.2二叉搜索树,二叉搜索树又称为二元字典树，是一种最常用的动态数据集的数据结构，可以用于实现字典和优先队列等ADT。4.2.1二叉搜索树（BinarySearchT
7、rees）BST的一个结点与一个数据项相对应，除了数据项Object或数据项的指针之外，结点主要由关键字key域和指针域组成，即关键字key与指针left、right和p，三个指针分别指向该结点的左儿子、右儿子和父结点。BST中结点的关键字值应满足BST性质：即，设x是二叉搜索树的一个结点，结点y位于结点x的子树中，x、y的关键字值应满足以下关系：,P,KEY,Left,Right,如果y是x的左子树中的一个结点，则y-keyx-key；如果y是x的右子树中的一个结点，则y-keyx-key。Fig.4.1给出了由6个结点（数据项）组成的两个二叉搜索树。两个BST(a)和(b)有不同的树高，前
8、者比后者的查询效率更高。,遍历二叉搜索树的所有结点可以采用中序遍历（inordertreewalk）算法，即可将与二叉搜索树结点相对应的数据项按关键字从小到大排列出来。中序遍历（Inorder_Tree_Walk）算法4.2.2查询（Querying）的实现对二叉搜索树的查询主要是Search、Minimum、Maximum、Successor、Predecessor等操作，这些操作都可在O(h)时间内完成，其中h是二叉树的高。,如Fig.4.2所示，BST查询操作为Tree_Search(root,k)，即搜索BST上关键字值为k的结点。Tree_Search算法,求最小元（或最大元）的操作
9、只需从根开始沿着左指针（或右指针）一直搜索至某一结点x，其left或right指针为NULL，这时结点x的关键字x-key为最小（或最大）。求最小元的算法Tree_Minimum(root)求最大元的算法Tree_Maximum(root)求数据项的后继与前导项的操作要相对复杂，如Fig.4.2，结点15（指关键字为15的结点)的后继是结点17，它是结点15的右子树中的最小元。然而对于没有右子树的结点，例如13、4和17，其后继分别为15、6和18，显然计算这三个结点的后继时需要使用父结点指针x-p。,求后继项的操作算法Successor(x),15的前导是左子树中的最大元,17的前导是其第一
10、个左祖先,Successor(x)操作根据条件x-right!=NULL决定两种情形：第一种情况从结点x下行，直到叶结点，其路长显然不超过树高h；第二种情况从结点x上行，路长同样不超过h。因此有下面的结论：定理4.1动态数据集合的查询操作Search、Minimum、Maximum、Successor、Predecessor可通过二叉搜索树实现，其算法可在O(h)时间内完成，其中h为二叉搜索树的高。4.2.3插入与删除操作动态数据集上的Insert(S,x)、Delete(S,x)操作与查询操作不同，它们会引起二叉搜索树本身的变化。(插入一定是插入到最底层)插入操作算法Tree_Insert,
11、Fig.4.3表示把新的数据项14（关键字值为14）作为新结点插入到二叉搜索树的过程。,从二叉搜索树中删除一个结点的算法比较复杂，假定待删除结点指针z不为NULL，有三种情形：（1）结点z没有子结点，可直接删除；（2）结点z只有一个子结点，可使z的父结点z-p直接指向z的子结点z-left或z-right；（3）结点z有两个子结点，则z的后继结点y必然在z的右子树中，且y无左子结点，按步骤（1）或（2）删除结点y，用y的数据取代z的数据。过程如图所示：,删除操作算法Tree_Delete这个算法除了调用函数Tree_Successor(root,z)的时间代价为O(h)外，其余各处的时间代价均
12、为O(1)阶。Tree_Insert(root,z)的运行是在从根到某一个叶结点的一条路径上进行的，因此有下面的结论。定理4.2动态数据集的Insert(S,x)、Delete(S,x)操作可通过二叉搜索树实现，其算法可在O(h)时间内完成，其中h为二叉搜索树的高。,4.3随机二叉搜索树,随机二叉搜索树（RandomlyBuiltBinarySearchTree）：一个由n个结点（具有n个不同的关键字）按随机顺序，经过n次Tree_Insert操作插入到一个原始空树而得到的二叉搜索树，称为随机二叉搜索树（RBST）。这里的按随机顺序是指，n个不同关键字的n!种不同排列的出现是等可能的。定理4.
13、3由n个不同的关键字组成的随机二叉搜索树的平均树高为h=O(logn)。该定理的证明基本思路与步骤：1.有关概率分布的假设：假定关键字输入序列k1,k2,.,kn为n个不同值的一种排列，设各种不同排序为等可能的，因此这一特定排序出现的可能性为1/n!。,假定：对任一j值（1jn），kj取n个关键字其中任意一个的概率为1/n，也是等可能的。2.在RBST中结点x为结点y的祖先的充要条件：首先分析从根到树上任一结点y（y-key=kj,1key=ki）都具有下列特征：其对应的关键字ki在输入关键字序列中位于kj之前，即1ikey=ki）在T中是结点y(y-key=kj)的祖先的充要条件是：,在Fi
14、g.4.5中，kj=17。从图(a)中可以看到，从根到结点17的路径上的4个结点的关键字都符合上述条件，而且，从(b)表中的关键字序列中可以看出，关键字17前面的10个关键字中满足命题4.1条件的关键字21、19、9、12全是结点17的祖先。,命题4.1证明,证明：分为两种情况，1）证明Ki是从1（根）至i中值大于kj的结点中值最小者（命题前部）设k为从1（根）至ki中路径上的点，且kkj，则为证明上述命题，只需证明kki。为证明这一点，采用反证法，设kkj矛盾。2)同理可证命题右部.,3.求RBST中任一结点的深度d(kj,T)：从命题4.1立即可以计算出T中任一（与关键字kj对应的）结点的
15、深度d(kj,T)恰恰等于满足命题4.1条件的（祖先）结点的个数，即：命题4.2在上述的随机二叉搜索树T中，对于给定的关键字kj(1jn)，令即kl是所有的先于ki输入并大于kj的值；令即kl是所有的先于ki输入并小于kj的值。则从根到y（y-key=kj）的路径上，结点的关键字集合恰为GjLj，且d(kj,T)=|Gj|+|Lj|。,从Fig4.5的实例中可以看到，对于kj=17，Gj=21，9，Lj=9。12，所以kj的深度为4。,定理:对于n1,插入n个随机元素到初始为空的二叉搜索树,需要的期望比较次数为:,证明:由序列a1,a2,an创建一棵二叉查找树时,令T(n)为序列元素之间需要的
16、比较次数。T(0)=0，令b1,b2,bn为已按升序排好的序列。如果a1,a2,an是随机的，则对于某元素ai,任意j(1jn),ai等可能地为bj，(ai)bj为最终树的根，则b1,b2,bj-1位于bj的左子树(j-1个元素)，bj+1,bn位于右子树(n-j)个元素。),ai,b1,bj-1,bj+1,bn,b1,bj-1插入到最终树中，每个都一定与根比较一次，然后就是插入到左子树中(与ai插入到整棵树中过程相同，即递归实现)，对于j-1个结点，共需要j-1+T(j-1)次比较；同理bj+1,bn插入到右子树中的比较次数为：n-j+T(n-j)，即将ai插入最终n个结点的搜索树中且ai为bj(根)的比较次数为上述两部分之和，即n-1+T(j-1)+T(n-j)。由于j等可能地取1,2,n中的任意值，所以：,也即：,由此可得：T(n)cnlogn,该定理:建一棵n个结点的二叉搜索树的期望比较次数为O(nlogn),由于插入n个结点的总时间代价为:O(nlogn),因此对于树中的某一个结点而言,找到该结点的总比较次数为T(n)/
