《chapter 数据集合上的搜索(Searching)算法》由会员分享，可在线阅读，更多相关《chapter 数据集合上的搜索(Searching)算法（92页珍藏版）》请在金锄头文库上搜索。
1、计算机算法 设计与分析导论南开大学 计算机科学与技术系刘璟1Chapter 4.Chapter 4. 数据集合上的搜索数据集合上的搜索 (Searching)(Searching)算法算法 v 4.1 动态数据集(Dynamic Set)与抽象数据类型(ADT)v 4.2 二叉搜索树(Binary Search Trees)v 4.3 随机二叉搜索树(Randomly Built Binary Search Tree)v 4.4 红黑树(Red-Black Tree)v 4.5 2-3-4树 v 4.6 Hashing技术 24.1 动态数据集(Dynamic Set)与抽象 数据类型(ADT
2、)静态数据集（Static Set）中的数据是固定不变的。 动态数据集（Dynamic Set）则是由不断变动的同类型数据元 素组成的数据集合。动态数据集（Dynamic Set）可以表示为一个数据元素的数组 ： class DynamicSet int setSize;ObjectarraySize elements;. /Object为数据元素的类型，setSize为当前集合中的元素个数3用数组表示集合操作方便，但当集合中的元素个数不断增加 时，数组的长度必须扩大。一般采用空间倍增（array doubling）技术，即另外申请一个加倍长度的新数组，把集合 中的数据传送过来，取代原有的空间
3、。 其过程为：arrayDouble(set) newSize = 2*arraySize ;newElements = new Object(newSize) ;Transfer all elements from the set.elements to the newElement;set.elements = newElements ;set.setSize = newSize ; 更为灵活的存储形式是利用指针和链表（例如线性链表和树 结构），这种存储形式在搜索算法中经常用到。 4搜索问题：在集合中检索出其关键字域的值等于给定值的数 据元素。 已知：动态数据集类型DynamicSet的一
4、个实例set和值x。 求：集合set中一个元素Object element，使element.key = x。数据集合上的操作（operation）可以分为两类： 查询（queries）操作：对数据集不做任何变动，仅仅返回有 关集合的某些信息；修改（modifying operations）操作：要对数据集合的某些域 进行改动。 一些典型的操作： Search(S,k)：搜索，一个查询操作。对于给定的数据集合S 和一个关键字值k，返回S中一个元素（element）的指针x， 使得x-key=k。当S中没有符合条件的元素时，返回的指针为 空（NULL）。5 Insert(S,x)：插入，一个修改
5、操作。把由x指向的数据元素加 入到集合S中，一般假定在x指向的数据元中，与集合运算相 关的所有分量（域）都已经初始化。 Delete(S,x)：删除，一个修改操作。给定指向集合S中一个 元素的指针x，将此元素从S中删除。 Minimum(S)：求最小元，一个查询操作。若集合S中所有 数据元素的关键字值为一全序集，则返回具有最小关键字值 的数据元素的指针。 Maximum(S)：求最大元，一个查询操作。返回具有最大关 键字值的数据元素的指针。 Deletemin(S)：删除最小元，一个修改操作。它相当于 Minimum(S)和Delete(S,x)的联合， 即：Delete(S,Minimum(
6、S)。 6 Successor(S,x)：求后继数据元，一个查询操作。若S中的数 据元素按关键字值从小到大排列，x是指向S中某一数据元素 的指针，则返回x所指向的数据元素的下一个数据元素的指针 。若x指向最后一个数据元素，则返回NULL。 Predecessor(S,x)：求前导数据元，一个查询操作。返回x所 指向的数据元素的前一个数据元素的指针。若x指向第一个数 据元素，则返回NULL。 搜索算法（及相关操作算法）的设计实际上是实现适合各种 不同应用需要的ADT，例如： 字典（Dictionary）作为抽象数据类型，可以分为两类：静态字典：（静态数据集S，Search）；动态字典：（动态数据
7、集S，Search，Insert，Delete）。 优先队列（Priority Queue）：（动态数据集S，Insert， Deletemin）。 74.2 二叉搜索树二叉搜索树又称为二元字典树，是一种最常用的动态数据集 的数据结构，可以用于实现字典和优先队列等ADT。 v4.2.1 二叉搜索树（Binary Search Trees） BST的一个结点与一个数据项相对应，除了数据项Object或数 据项的指针之外，结点主要由关键字key域和指针域组成，即 关键字key与指针left、right和p，三个指针分别指向该结点的 左儿子、右儿子和父结点。 BST中结点的关键字值应满足BST性质：
8、 即，设x是二叉搜索树的一个结点，结点y位于结点x的子树中 ，x、y的关键字值应满足以下关系：8如果y是x的左子树中的一个结点，则y-keyx-key； 如果y是x的右子树中的一个结点，则y-keyx-key。Fig.4.1给出了由6个结点（数据项）组成的两个二叉搜索树。 两个BST(a)和(b)有不同的树高，前者比后者的查询效率更高 。 9遍历二叉搜索树的所有结点可以采用中序遍历（inorder tree walk）算法，即可将与二叉搜索树树结点相对应的数据项按 关键字从小到大排列出来。 中序遍历（Inorder_Tree_Walk）算法v4.2.2 查询（Querying）的实现对二叉搜索
9、树的查询主要是Search、Minimum、Maximum、 Successor、Predecessor等操作，这些操作都可在O(h)时间内 完成，其中h是二叉树的高。如Fig.4.2所示，BST查询操作 为Tree_Search(root,k)，即搜 索BST上关键字值为k的结点。 Tree_Search算法 10求最小元（或最大元）的操作只需从根开始沿着左指针（或 右指针）一直搜索至某一结点x，其left或right指针为NULL， 这时结点x的关键字x-key为最小（或最大）。 求最小元的算法Tree_Minimum(root) 求最大元的算法Tree_Maximum(root) 求数据
10、项的后继与前导项的操作要相对复杂，如Fig.4.2，结点 15（指关键字为15的结点)的后继是结点17，它是结点15的右 子树中的最小元。然而对于没有右子树的结点，例如13、4和 17，其后继分别为15、6和18，显然计算这三个结点的后继时 需要使用父结点指针x-p。求后继项的操作算法 Successor(x) 11Successor(x)操作根据条件x-right!=NULL决定两种情形：第 一种情况从结点x下行，直到叶结点，其路长显然不超过树高 h；第二种情况从结点x上行，路长同样不超过h。因此有下面的结论： 定理4.1 动态数据集合的查询操作Search、Minimum、 Maximum
11、、Successor、Predecessor可通过二叉搜索树实现， 其算法可在O(h)时间内完成，其中h为二叉搜索树的高。v4.2.3 插入与删除操作动态数据集上的Insert(S,x)、Delete(S,x)操作与查询操作不同 ，它们会引起二叉搜索树本身的变化。 插入操作算法Tree_Insert 12Fig.4.3表示把新的数据项14（关键字值为14）作为新结点插入 到二叉搜索树的过程。13从二叉搜索树中删除一个结点的算法比较复杂，假定待删除 结点指针z不为NULL，有三种情形： （1）结点z没有子结点，可直接删除； （2）结点z只有一个子结点，可使z的父结点z-p直接指向z的子结点z-
12、left或z-right； （3）结点z有两个子结点，则z的后继结点y必然在z的右子树中，且y无左 子结点，按步骤（1）或（2）删除结点y，用y的数据取代z的数据。 过程如图所示： 1415删除操作算法 Tree_Delete这个算法除了调用函数Tree_Successor(root,z)的时间代价为 O(h)外，其余各处的时间代价均为O(1)阶。 Tree_Insert(root,z)的运行是在从根到某一个叶结点的一条路 径上进行的，因此有下面的结论。 定理4.2 动态数据集的Insert(S,x)、Delete(S,x)操作可通过二 叉搜索树实现，其算法可在O(h)时间内完成，其中h为二叉
13、搜 索树的高。164.3 随机二叉搜索树随机二叉搜索树（Randomly Built Binary Search Tree）： 一个由n个结点（具有n个不同的关键字）按随机顺序，经过n 次Tree_Insert操作插入到一个原始空树而得到的二叉搜索树 ，称为随机二叉搜索树（RBST）。这里的按随机顺序是指， n个不同关键字的n!种不同排列的出现是等可能的。 定理4.3 由n个不同的关键字组成的随机二叉搜索树的平均树 高为h=O(logn)。 该定理的证明基本思路与步骤： 1. 有关概率分布的假设： 假定关键字输入序列k1,k2,.,kn为n个不同值的一种排列，设各 种不同排序为等可能的，因此这
14、一特定排序出现的可能性为 1/n!。 17假定：对任一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）的祖先的充要条件是：18在Fig.4.5中，kj=17。从图(a)中可以看到，从根到结点17的路 径上的4个结点的关键字都符合上述条件，而且，从(b)表中的 关键字序列中可以看出，关键字17前面的10个关键字中满足 命题4.1条件
15、的关键字21、19、9、12全是结点17的祖先。193. 求RBST中任一结点的深度d(kj,T)： 从命题4.1立即可以计算出T中任一（与关键字kj对应的）结点 的深度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|。 20从Fig4.5的实例中可以看到，对于kj =17，Gj=21，9， Lj =9
16、。12，所以kj的深度为4。 214.4 红黑树（Red-Black Tree）v4.4.1 Red-Black树的性质 Red-Black(RB)树是一种二叉搜索树，它的每个结点有五个域 ：color（取值为red或black ）、key、left、right和p（省略了 相关数据或指针）。RB树把包含key域的结点作为内部结点，而以NULL（空）作 为其“外部结点”，这些外部结点与left、right、p域中的NULL 指针值相对应（见Fig.4.6），空结点与实际的数据元素或关键 字都无关。一个在结构上做了上述改变的二叉搜索树称为一个RB树 。 2223RB树满足下面的性质： 1. 每个结点的color域必须为red或black； 2. 每个叶结点（NULL）的color为black； 3. 如果一个结点的color为red，则其子结点全为black结点。 4. 从某一结点到其子树上任意一个叶
