chapter4-数据集合上的搜(Searching)算法教学课件

计算机算法计算机算法设计与分析导论设计与分析导论南开大学南开大学 计算机科学与技算机科学与技术系系刘璟1Chapter 4.数据集合上的搜索数据集合上的搜索(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)静态数据集静态数据集（Static Set）中的数据是固定不变的。）中的数据是固定不变的。动态数据集动态数据集（Dynamic Set）则是由不断变动的同类型数据元）则是由不断变动的同类型数据元素组成的数据集合。素组成的数据集合。动态数据集（动态数据集（Dynamic Set）可以表示为一个数据元素的数组：）可以表示为一个数据元素的数组：class DynamicSet int setSize;ObjectarraySize elements;./Object为数据元素的类型，为数据元素的类型，setSize为当前集合中的元素个数为当前集合中的元素个数3用用数数组组表表示示集集合合操操作作方方便便，但但当当集集合合中中的的元元素素个个数数不不断断增增加加时时，数数组组的的长长度度必必须须扩扩大大。一一般般采采用用空空间间倍倍增增（array doubling）技技术术，即即另另外外申申请请一一个个加加倍倍长长度度的的新新数数组组，把把集集合合中的数据传送过来，取代原有的空间。中的数据传送过来，取代原有的空间。其过程为：其过程为：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的一个实例的一个实例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)：插插入入，一一个个修修改改操操作作。把把由由x指指向向的的数数据据元元素素加加入入到到集集合合S中中，一一般般假假定定在在x指指向向的的数数据据元元中中，与与集集合合运运算算相相关的所有分量（域）都已经初始化。关的所有分量（域）都已经初始化。Delete(S,x)：删除，一个修改操作。给定指向集合删除，一个修改操作。给定指向集合S中一个中一个元素的指针元素的指针x，将此元素从，将此元素从S中删除。中删除。Minimum(S)：求最小元，一个查询操作。若集合求最小元，一个查询操作。若集合S中所有数中所有数据元素的关键字值为一全序集，则返回具有最小关键字值的据元素的关键字值为一全序集，则返回具有最小关键字值的数据元素的指针。数据元素的指针。Maximum(S)：求求最最大大元元，一一个个查查询询操操作作。返返回回具具有有最最大大关关键字值的数据元素的指针。键字值的数据元素的指针。Deletemin(S)：删删除除最最小小元元，一一个个修修改改操操作作。它它相相当当于于Minimum(S)和和Delete(S,x)的联合，的联合，即：即：Delete(S,Minimum(S)。6 Successor(S,x)：求求后后继继数数据据元元，一一个个查查询询操操作作。若若S中中的的数数据据元元素素按按关关键键字字值值从从小小到到大大排排列列，x是是指指向向S中中某某一一数数据据元元素素的的指指针针，则则返返回回x所所指指向向的的数数据据元元素素的的下下一一个个数数据据元元素素的的指指针针。若若x指向最后一个数据元素，则返回指向最后一个数据元素，则返回NULL。Predecessor(S,x)：求求前前导导数数据据元元，一一个个查查询询操操作作。返返回回x所所指指向向的的数数据据元元素素的的前前一一个个数数据据元元素素的的指指针针。若若x指指向向第第一一个个数数据元素，则返回据元素，则返回NULL。搜搜索索算算法法（及及相相关关操操作作算算法法）的的设设计计实实际际上上是是实实现现适适合合各各种种不同应用需要的不同应用需要的ADT，例如：，例如：字典（字典（Dictionary）作为抽象数据类型，可以分为两类：）作为抽象数据类型，可以分为两类：静态字典：（静态数据集静态字典：（静态数据集S，Search）；）；动态字典：（动态数据集动态字典：（动态数据集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性质：性质：即，设即，设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）的实现）的实现对对二二叉叉搜搜索索树树的的查查询询主主要要是是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)求求数数据据项项的的后后继继与与前前导导项项的的操操作作要要相相对对复复杂杂，如如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、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-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为为二二叉叉搜搜索树的高。索树的高。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个不同值的一种排列，设各个不同值的一种排列，设各种不同排序为等可能的，因此这一特定排序出现的可能性为种不同排序为等可能的，因此这一特定排序出现的可能性为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条件的关键字条件的关键字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。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.从某一结点到其子树上任意一个叶结点的所有简单路径，包含相同个数从某一结点到其子树上任意一个叶结点的所有简单路径，包含相同个数的的black结点。结点。从一个结点从一个结点x到（其子树中的）任一叶结点的简单路径上的黑到（其子树中的）任一叶结点的简单路径上的黑结点的个数称为结点结点的个数称为结点x的的black高（高（black-height），表示为），表示为bh(x)。定理定理4.4 具有具有n个内部结点的个内部结点的RB树的树高树的树高 h 2ln(n+1)。证明：证明：1.首先用归纳法证明以首先用归纳法证明以RB树上任一结点树上任一结点x为根的子树至少为根的子树至少包含包含 个内部结点。个内部结点。241递递归归基基础础：对对于于高高度度为为0的的结结点点x，即即x为为叶叶结结点点（NULL），以其为根的子树有以其为根的子树有0个内部结点，即至少有个内部结点，即至少有 个内部结点。命题成立。个内部结点。命题成立。2设对于高度为设对于高度为h-1的结点命题成立。的结点命题成立。3考考察察高高为为h(0)的的结结点点x，由由于于h0，x是是RB树树的的内内部部结结点点，必有两个子结点必有两个子结点x1、x2，其高为，其高为h-1，且有，且有根据归纳假设，以根据归纳假设，以x1、x2为根的两子树分别至少有为根的两子树分别至少有 个内部结点，个内部结点，以以x为根的子树至少有为根的子树至少有 个内部结点。个内部结点。归纳完成。归纳完成。252.证明对于证明对于RB树的根树的根r，设其高为，设其高为h，bh(r)h/2。这这一一点点由由性性质质3，即即从从根根到到叶叶的的任任一一条条路路上上，red结结点点数数不不超超过一半即可证明。过一半即可证明。3.由上面两个命题可知：高为由上面两个命题可知：高为h的的RB树，其内部结点数树，其内部结点数n至少为至少为 ，即即 。故有故有 ，定理得证。，定理得证。定定理理4.4说说明明，动动态态数数据据集集上上的的基基本本操操作作在在RB树树上上的的执执行行代代价价为为O(h)=O(logn)阶阶。换换句句话话说说，用用RB树树的的形形式式实实现现动动态态数数据据集，在任何时刻，树高集，在任何时刻，树高h总能保持在总能保持在O(logn)阶。阶。26v4.4.2 Red-Black树的树的插入插入与与删除删除算法算法 在插入或删除结点时，为了使树重新具有在插入或删除结点时，为了使树重新具有Red-Black性质，除性质，除了要改变结点间的指针链接关系外，还要对某些结点的着色了要改变结点间的指针链接关系外，还要对某些结点的着色进行调整。进行调整。对于结点间指针链接关系的修改归结为对于结点间指针链接关系的修改归结为旋转旋转（Rotation）操作，）操作，旋转是调整树的平衡状态的基本手段。旋转是调整树的平衡状态的基本手段。Rotation操作对二叉搜索树上的某一局部进行调整，通过交换操作对二叉搜索树上的某一局部进行调整，通过交换一对父子结点的父子关系，在保持树结点间的有序关系的条一对父子结点的父子关系，在保持树结点间的有序关系的条件下（即保持其中序遍历的结果为单调序列），改变该子树件下（即保持其中序遍历的结果为单调序列），改变该子树的平衡状态。的平衡状态。27Rotation操作分为左旋（操作分为左旋（Left-Rotation）和）和右旋右旋(Right-Rotation)，如，如Fig.4.7所示。所示。28左旋算法左旋算法Left_Rotation(root,x)Fig.4.8给给 出出 一一 次次 左左 旋旋 转转 的的 实实 例例 的的 图图 示示。Right_Rotation(root,x)的算法与的算法与Left_Rotation(root,x)类似。类似。29这个算法主要完成两件事：这个算法主要完成两件事：1把结点把结点x与其左子结点与其左子结点y的父子关系进行调整，的父子关系进行调整，即把即把x-pxy的父子关系改变为的父子关系改变为x-pyx的顺序；的顺序；2把把y的左子树变为的左子树变为x的右子树。的右子树。算法不存在与结点数算法不存在与结点数n相关的操作，因此时间代价为相关的操作，因此时间代价为O(1)阶。阶。RB树的插入操作，首先调用树的插入操作，首先调用Tree_Insert(root,x)函数完成二叉函数完成二叉搜索树的插入操作，然后调用搜索树的插入操作，然后调用Tree_Rotation(root.x)函数，并函数，并对结点的着色进行调整，使之恢复为一个对结点的着色进行调整，使之恢复为一个RB树。树。插入操作算法插入操作算法RB_Insert(root,x)30Fig.4.9给给出出了了一一个个简简 单单 的的 实实 例例，作作 为为 RB_Insert()算算法法运运行行的的示示意意图。图。31从算法从算法RB_Insert()的执行过程可以看出：的执行过程可以看出：1对于空树或插入后对于空树或插入后x-p为为black结点的情形，无需进一步处结点的情形，无需进一步处理；理；2x-p为为red结点时，首先按结点时，首先按case1处理，对以处理，对以x-p-p为根的为根的子树进行调整，然后向上扩展，分别按子树进行调整，然后向上扩展，分别按case2、case3处理。处理。RB树的树的Delete算法与算法与RB_Insert()算法的思路是一致的，首先算法的思路是一致的，首先按二叉搜索树的删除方法删去需要删除的结点。在删除过程按二叉搜索树的删除方法删去需要删除的结点。在删除过程中会出现三种情形，在第二、三种情形中，若被摘除中会出现三种情形，在第二、三种情形中，若被摘除（spliced-out）结点是）结点是black结点，这时结点，这时Red-Black性质性质4可能可能被破坏，就需要对被破坏，就需要对RB树进行恢复，恢复方法与插入操作后的树进行恢复，恢复方法与插入操作后的修复类似。修复类似。32v4.4.3 关于关于Red-Black树的几点树的几点讨论讨论 1.RB树树是是一一种种二二叉叉搜搜索索树树，在在其其上上进进行行的的查查询询操操作作Search、Minimum、Maximum、Successor、Predecessor等等与与一一般般二二叉叉搜搜索索树树的的查查询询操操作作完完全全相相同同，而而且且算算法法简简明明，也也即即RB树树具具有一般二叉搜索树的优点。有一般二叉搜索树的优点。2.如如定定理理4.4所所指指出出的的，RB树树是是平平衡衡树树，在在其其上上进进行行的的所所有有操操作作的的时时间间代代价价都都是是O(logn)阶阶的的，RB树树的的树树高高h总总是是保保持持在在一一个很小的范围，即个很小的范围，即h2ln(n-1)。3.RB树树与与一一般般平平衡衡树树的的平平衡衡机机制制不不同同，虽虽然然它它不不需需要要计计算算平平衡衡因因子子，但但Red-Black性性质质（特特别别是是性性质质4）保保证证了了整整棵棵树树的的平衡性，即绝大多数内部结点有两个子结点。平衡性，即绝大多数内部结点有两个子结点。事事实实上上，red结结点点不不可可能能仅仅有有一一个个black子子结结点点，而而只只可可能能为为以以下下两两种种情情形形之之一一：有有两两个个black（数数据据）子子结结点点；或或左左、右右子子结点均为结点均为NULL。33black结结点点的的子子结结点点有有三三种种情情形形：有有两两个个（数数据据）子子结结点点；左左右右子子结结点点为为NULL；第第三三种种情情形形只只可可能能出出现现在在树树的的下下层层，只只有有一一个个数数据据子子结结点点，这这时时该该子子结结点点必必为为red，且且子子结结点点左左右右儿儿子子为空。如为空。如Fig.4.10所示。所示。RB树树几几乎乎是是一一个个2-树树，不不可可能能出出现现单单链链的的情情形形，从从而而保保证证了了整棵树的平衡性。整棵树的平衡性。4.另另一一种种非非二二叉叉的的平平衡衡搜搜索索树树2-3-4树树，很很容容易易转转变变为为Red-Black树。树。344.5 2-3-4树 v4.5.1 2-3-4树树及其实例及其实例 1.2-3-4树有三种不同的结点：树有三种不同的结点：2-结点、结点、3-结点和结点和4-结点。结点。2-结点与二叉树的结点相同，除了关键字域结点与二叉树的结点相同，除了关键字域key外，有三个指外，有三个指针域针域p、p1、p2，p指针指向父结点、指针指向父结点、p1指针为左指针、指针为左指针、p2指指针为右指针。另外增加一个结点类型域针为右指针。另外增加一个结点类型域type，用来区分结点类，用来区分结点类型。数据域保持数据元素的内容或指向数据元素的指针型。数据域保持数据元素的内容或指向数据元素的指针。3-结点有两个关键字域结点有两个关键字域key1和和key2，其中，其中key1key与与key1、key2进行进行比较，如相等即找到，不相等则根据比较结果的三种情形转比较，如相等即找到，不相等则根据比较结果的三种情形转入该结点的子树：入该结点的子树：x-key key1 转向转向p1；key1 key key key2 转向转向p3。354-结点与结点与3-结点类似，增加了结点类似，增加了key3域和域和p4指针。在指针。在2-3-4树种，树种，4-结点是一种临时结点，在插入和删除过程中可能产生结点是一种临时结点，在插入和删除过程中可能产生4-结点，结点，但该结点可随时由三个但该结点可随时由三个2-结点取代。结点取代。2.2-3-4树的最主要的特征是其所有的叶结点都在同一深度。树的最主要的特征是其所有的叶结点都在同一深度。如如Fig.4.11所示：所示：假定动态数据集的关键字值域为英语字母集合，即从小到大假定动态数据集的关键字值域为英语字母集合，即从小到大为为A,B,C,D,E,.,X,Y,Z。图中的结点图中的结点I是根，是一个是根，是一个2-结点，其左子树中的关键结点，其左子树中的关键字值均小于字值均小于I，右子树中的，右子树中的关键字值均大于关键字值均大于I，该树，该树T中中只有只有2-结点和结点和3-结点。结点。36v4.5.2 2-3-4树上的树上的查询操作查询操作算法算法 2-3-4树树上上的的搜搜索索算算法法与与二二叉叉搜搜索索树树上上的的搜搜索索算算法法差差别别不不大大，只需要区别只需要区别2-结点和结点和3-结点。结点。2-3-4树的搜索算法树的搜索算法v4.5.3 2-3-4树的树的构造过程构造过程 2-3-4树树的的插插入入算算法法是是保保证证树树的的基基本本特特征征（即即所所有有叶叶结结点点在在同同一一深深度度）的的关关键键。在在插插入入时时，2-结结点点可可以以变变为为3-结结点点，3-结结点点可可以以变变为为4-结结点点，当当出出现现4-结结点点时时，自自动动分分裂裂为为三三个个2-结结点点，并且把中间的并且把中间的2-结点插入到上一层的父结点中。结点插入到上一层的父结点中。在在一一般般二二叉叉搜搜索索树树中中，每每插插入入一一个个结结点点是是在在最最下下层层添添加加一一个个叶结点，而叶结点，而2-3-4树是在整体扩大的情况下进行向上扩展。树是在整体扩大的情况下进行向上扩展。每当树增加一层时，即是把根结点上升一层，于是树中所有每当树增加一层时，即是把根结点上升一层，于是树中所有结点的深度同时加结点的深度同时加1。3738在在插插入入算算法法中中，一一旦旦产产生生了了4-结结点点就就要要进进行行分分裂裂，这这时时就就会会利利用到父结点指针用到父结点指针p。在。在4-结点分裂时，存在三种情形：结点分裂时，存在三种情形：(1)4-结点是结点是2-3-4树的根，这时，中间的树的根，这时，中间的2-结点作为新的根，结点作为新的根，树增加一层；树增加一层；(2)4-结点的父结点是一个结点的父结点是一个2-结点，只需把结点，只需把4-结点中的中间关结点中的中间关键字插入到键字插入到2-结点，该结点，该2-结点变为结点变为3-结点；结点；(3)4-结点的父结点是一个结点的父结点是一个3-结点，把结点，把4-结点的中间关键字插结点的中间关键字插入到这个入到这个3-结点中，该结点中，该3-结点又变成一个新的结点又变成一个新的4-结点，于是继结点，于是继续向上分裂。续向上分裂。假设插入时树高为假设插入时树高为h，插入过程在最坏情形下是从根到叶、再，插入过程在最坏情形下是从根到叶、再从叶到根，至多进行从叶到根，至多进行2h次处理，因此插入算法的时间代价仍次处理，因此插入算法的时间代价仍是是O(h)阶的。阶的。39v4.5.4 2-3-4树的性能分析树的性能分析 定定理理4.5 由由n个个关关键键字字生生成成的的2-3-4树树实实际际上上是是一一个个完完全全的的2-3树树，设设其其高高为为h，结结点点数数为为m，则则其其结结点点数数m介介于于同同样样高高度度为为h的的完完全二叉树和完全三叉树的结点数之间，即：全二叉树和完全三叉树的结点数之间，即：2h+1-1 m (3h+1-1)/2且关键字个数且关键字个数nm，故有，故有n 2h+1-1 即即 h ln(n+1)-1 或或 h=(logn)，定理得证。，定理得证。由由定定理理4.5可可知知，2-3-4树树上上的的基基本本操操作作的的代代价价在在最最坏坏情情形形下下也也是是O(logn)阶的。阶的。v4.5.5 有关有关2-3-4树的几点讨论树的几点讨论 1.2-3-4树树实实际际上上是是一一种种2-3树树，4-结结点点是是临临时时结结点点，不不会会占占用用较多空间，可以分配临时性的工作单元存放较多空间，可以分配临时性的工作单元存放4-结点。结点。402.可以采用同一种数据类型来表示可以采用同一种数据类型来表示2-结点和结点和3-结点（按结点（按3-结点结点来设计），只在来设计），只在type域用不同的标记来区分结点类型即可。域用不同的标记来区分结点类型即可。3.为了减少插入算法的代价，还有一种把分裂为了减少插入算法的代价，还有一种把分裂4-结点的工作分结点的工作分摊到不同的操作中去的方案，即每次生成摊到不同的操作中去的方案，即每次生成4-结点时进行一次分结点时进行一次分裂，如果其父结点又变为裂，如果其父结点又变为4-结点，则不在这一次插入操作中继结点，则不在这一次插入操作中继续分裂。当进行下次插入或搜索操作时，每遇到一个续分裂。当进行下次插入或搜索操作时，每遇到一个4-结点就结点就进行一次分裂，这样可以减少一次插入操作的代价。进行一次分裂，这样可以减少一次插入操作的代价。4.与插入算法相比，删除操作与插入算法相比，删除操作Delete算法是一个逆过程。插入算法是一个逆过程。插入操作中，关键字要按规则逐层向上插入，而删除操作应在删操作中，关键字要按规则逐层向上插入，而删除操作应在删除其关键字后按一定规则逐层向下压，除其关键字后按一定规则逐层向下压，415.2-3-4树树获获得得平平衡衡性性的的方方法法很很巧巧妙妙，但但缺缺点点是是结结点点类类型型较较为为复复杂杂，可可以以通通过过一一种种简简单单的的变变换换把把2-3-4树树转转化化为为二二叉叉搜搜索索树树。方方法法是是把把2-3-4树树中中的的3-结结点点（或或4-结结点点）用用一一个个2-结结点点结结构构来来取代，取代的方法如取代，取代的方法如Fig.4.13所示。所示。42用用上上述述变变换换将将Fig.4.11中中的的2-3-4树树转转化化为为一一个个二二叉叉搜搜索索树树，不不难难发发现现，这这是是一一棵棵RB树树。从从中中也也可可以以看看出出RB树树与与2-3-4树树的的内在联系。内在联系。434.6 Hashing技技术 v4.6.1 Hash算法的基本思想与一般模型算法的基本思想与一般模型 Hash方法的基本思想是，首先产生从可能的关键字集合（又方法的基本思想是，首先产生从可能的关键字集合（又称全域）称全域）U=0.N-1到存储空间（到存储空间（Hash表）地址集合表）地址集合T=0.m-1的一个映射函数：的一个映射函数：h:U0.m-1。于是，要存储或检索关键。于是，要存储或检索关键字为字为xU的数据项只需计算函数的数据项只需计算函数h(x)，直接得到该数据项应，直接得到该数据项应在的地址。在的地址。Fig.4.15中给出了一个简单中给出了一个简单的实例，其中的实例，其中N=100，m=7，h(x)=xmod7。44然然而而对对不不同同的的关关键键字字x,yU，h(x)=h(y)的的情情况况可可能能出出现现，这这种种情情形形称称为为冲冲突突（collision）。由由于于一一般般的的|U|远远远远大大于于m，冲冲突难以避免，因此突难以避免，因此Hash技术研究的基本问题是：技术研究的基本问题是：(1)设计一个好的设计一个好的Hash函数，计算简单，而又使数据项分布均函数，计算简单，而又使数据项分布均匀以减少冲突；匀以减少冲突；(2)设计解决冲突的策略和算法。设计解决冲突的策略和算法。集合集合 为实际存于为实际存于Hash表中的关键字集合，表中的关键字集合，|S|=nN。=n/m 称为负载因子（称为负载因子（load factor）,值是决定哈希算法值是决定哈希算法性能的主要因素。性能的主要因素。Hash算法的算法的“散列散列”存储方式，使得它不能支持存储方式，使得它不能支持Minimum、Maximum、Successor、Predecessor、Mindelete这类的操作，这类的操作，而对于而对于Search、Insert、Delete操作不但可以支持而且有较高操作不但可以支持而且有较高的性能。的性能。45从从抽抽象象数数据据类类型型（ADT）的的观观点点来来说说，Hash算算法法用用于于实实现现字字典典（Dictionary）类类型型，实实际际关关键键字字集集合合S为为固固定定不不变变时时，称称为为静静态态字字典典，只只支支持持Search操操作作，S为为可可变变时时，即即动动态态数数据据集集，称为称为动态字典动态字典，动态字典支持搜索、插入和删除操作。，动态字典支持搜索、插入和删除操作。v4.6.2 Hash函数的设计函数的设计 Hash函函数数的的设设计计一一般般应应能能兼兼顾顾计计算算简简单单和和分分布布均均匀匀，在在大大多多数数应应用用问问题题中中，可可能能的的关关键键字字集集合合U往往往往远远远远大大于于地地址址空空间间的的规规模模。例例如如以以姓姓名名字字符符串串作作为为关关键键字字，|U|=N是是一一个个极极大大的的值值，而而Hash表表的的长长度度m和和实实际际关关键键字字集集合合S（|S|=n）与与N相相比比小小得得多。因此，分布均匀的要求就是要对于多。因此，分布均匀的要求就是要对于使使 尽量小，尽量小，其中其中h-1(i)为被为被h映射至地址映射至地址i的关键字全体。的关键字全体。46当且仅当当且仅当 时达到最小值，意味着时达到最小值，意味着将将无无任任何何冲冲突突产产生生。无无冲冲突突的的Hash函函数数称称为为完完备备HashHash函函数数（Perfect Hash Function），简称），简称PHF。事事实实上上，无无冲冲突突的的要要求求是是极极难难达达到到的的。“生生日日悖悖论论”指指出出，在在23个个人人中中，有有两两个个人人的的生生日日在在同同一一天天的的概概率率为为0.51，即即当当|S|=n=23，m=365时时，发发生生冲冲突突的的概概率率已已经经在在50%以以上上。而而当当n=50时时，发发生生冲冲突突的的概概率率已已达达0.97。在在D.Knuth所所举举的的实实例例中中指指出出，当当n=31，m=41时时，无无冲冲突突的的映映射射函函数数只只占占全全部部可可能能映映射射函函数数的的1/107。因因此此，在在大大多多数数情情形形下下只只能能追追求求将将冲冲突突尽尽可可能减少。能减少。常用的常用的Hash函数设计方法：函数设计方法：1.除式法（除式法（Division method）令令h(x)取用取用m除除x的余数，即的余数，即h(x)=xmodm。47这这种种Hash函函数数计计算算速速度度最最快快。在在设设计计时时，m取取值值不不要要习习惯惯性性地地取取为为2的的n次次幂幂。因因为为这这会会使使得得h(x)的的取取值值只只依依赖赖于于关关键键字字的的2进进制制值值的的最最后后几几位位，这这不不利利于于数数据据在在Hash表表中中的的均均匀匀分分布布。一般情况下一般情况下m值最好取为不与某个值最好取为不与某个2n值相近的素数。值相近的素数。2.乘式法（乘式法（Multiplication method）可方便地取可方便地取m=2p，映射函数可表示为：，映射函数可表示为：其中其中a为常数为常数0a0.95 时，扩大时，扩大Hash区，区，即即所所谓谓空空间间倍倍增增（array doubling）技技术术，需需要要把把数数据据集集中中的的所所有有数数据据按按照照新新的的Hash函函数数重重新新转转存存入入新新的的Hash区区，这这一一工工作代价很大。作代价很大。为为解解决决空空间间倍倍增增所所需需的的高高代代价价问问题题，可可采采用用线线性性扩扩张张Hash算算法。基本思想是指定一对负载因子法。基本思想是指定一对负载因子 的上限的上限 和下限和下限 ，在可能关键字集合在可能关键字集合S的大小的大小n改变的过程中，一旦改变的过程中，一旦 超过超过 ，存储区扩充一个桶（可存放存储区扩充一个桶（可存放b条数据项），当条数据项），当 小于小于 时，时，存存储储区区缩缩减减一一个个桶桶。这这样样就就保保证证动动态态数数据据集集上上的的操操作作总总是是在在良好的性能下工作。良好的性能下工作。v*4.6.5 Hash技术的几种新发展技术的几种新发展 1.完备完备Hash函数（函数（Perfect Hash Function）63完完备备哈哈希希函函数数（PHF）又又称称无无冲冲突突哈哈希希函函数数。即即PHF的的地地址址映映射射不不产产生生冲冲突突，一一次次计计算算即即可可找找到到目目标标数数据据项项。因因此此，用用PHF实实现现的的检检索索算算法法的的最最好好平平均均和和最最坏坏情情形形时时间间复复杂杂度度都都为为O(1)阶。其定义可叙述为：阶。其定义可叙述为：对任一时间关键字集合对任一时间关键字集合 ，函数函数h：称为称为S的完备哈希函数（的完备哈希函数（PHF），），如果对任意如果对任意 ，必有，必有 。当当m=n时，时，h称为集合称为集合S的最小完备哈希函数（的最小完备哈希函数（MPHF）。）。给给定定n（n不不太太大大）个个关关键键字字集集合合和和Hash表表长长m，有有几几种种PHF的构造技术：的构造技术：1）针对字符串关键字集合的启发式算法）针对字符串关键字集合的启发式算法假假定定集集合合 中中的的关关键键字字为为字字符符串串，设设关关键键字字kU为为一一个个=a,b,c,x,y,z上上的的字字符符串串，length(k)为为字字符符串串的的长长，F(k)，L(k)分别为分别为k的首末字符。的首末字符。64求形如求形如h(k)=length(k)+Value(F(k)+Value(L(k)的的Hash函数。函数。为为了了使使h(k)为为完完备备Hash函函数数，须须对对于于函函数数Value：Z的的值值进进行行适适当当的的定定义义，即即要要为为Value(a)，Value(b)，Value(z)赋赋予予适适当当的的值值，使使得得对对于于S中中的的所所有有关关键键字字，h(k)0m-1有有不不同的值。同的值。Sager提出的一种改进方法，是求形如：提出的一种改进方法，是求形如：h(k)=(h0(k)+g(h1(k)+g(h2(k)mod n 的最小完备的最小完备Hash函数。函数。这种方法首先选定适当的函数这种方法首先选定适当的函数h0(k)，h1(k)，h2(k)，然后根据，然后根据h0，h1，h2来确定函数来确定函数g。2）Hash索引表法索引表法（HIT法）法）对于关键字集合对于关键字集合S和和Hash表地址集表地址集0m-1，取，取t个个Hash函数函数hj：S0m-1(j=1t)。按一定的算法计算出一个一维数组：按一定的算法计算出一个一维数组：array0m-1 of 1t，称为，称为HIT表。表。65在在h1，h2，ht和和HIT确定的条件下，定义完备确定的条件下，定义完备Hash函数：函数：h：S0m-1，使得，使得对于关键字对于关键字kS，h(k)=hj(k)，其中，其中j1,2,t，满足条件：，满足条件：HIThj(k)=j。在已知在已知t个个Hash函数函数h1，h2，ht和和HIT表的条件下，用这个表的条件下，用这个PHF把关键字把关键字kS插入到插入到Hash表表T0m-1的算法为：的算法为：void writeHIT(key K)int j=1;while(HIThj(k)!=j)&(j=t)j+;if(j=t)Thj(k)=k;elsecout failure!;66如如果果h1，h2，ht和和HIT表表选选择择正正确确，“failure”的的情情况况不不会会出现。相应的检索算法为：出现。相应的检索算法为：int h(key k)int j=1;while(HIT hj(k)!=j)&(j=t)j+;if(j=t)return hj(k);elsereturn(-1);与与第第一一种种方方法法类类似似，PHF的的构构造造过过程程是是：首首先先选选择择t个个Hash函函数数h1h2ht，然然后后，确确定定HIT表表HIT0m-11,2,t的的m个个值值，使使得得所定义的函数所定义的函数h为为PHF，即对任何，即对任何x,yS，xy有有h(x)h(y)。67这个确定这个确定HIT表的过程类似于迷宫问题，八后问题，等组合问表的过程类似于迷宫问题，八后问题，等组合问题，可以用回溯等搜索算法完成。题，可以用回溯等搜索算法完成。如果满足条件的如果满足条件的HIT表不存在，可以在调整表不存在，可以在调整t值和值和t个个Hash函数函数后重新构造满足条件的后重新构造满足条件的HIT表。表。3）Fredman构造法构造法 Fredman通过构造法证明了，对任意的关键字集合通过构造法证明了，对任意的关键字集合至多取至多取m=3n（即（即 ），一定可以在形如），一定可以在形如 的的Hash函数中找到函数中找到S的完备的完备哈希函数。哈希函数。构造方法：构造方法：已知：已知：实际关键字集合实际关键字集合 ，且，且|U|=N为素数。为素数。对此对此S，先构造函数，先构造函数 h(x)=(kx)mod N)mod n。68用枚举法选择用枚举法选择k值，使得值，使得其中其中bi=|Si|，(i=0,1,n-1)，Si=x|xS,h(x)=i。Si是被是被h映射为映射为i的关键字集合。的关键字集合。已经证明，满足条件的已经证明，满足条件的k值一定存在。值一定存在。对此每个对此每个Si，(i=0,1,n-1)选择适当的选择适当的ki，构造函数，构造函数hi(x)=(kix)mod n)mod Ci。其中。其中Ci=1+bi(bi-1)，使得，使得 为单一映射函数（无冲突）。为单一映射函数（无冲突）。由于这时的集合由于这时的集合Si较小，较小，Ci值也不大，因此值也不大，因此ki一定存在。一定存在。取取 ，定义函数，定义函数 使对于任意使对于任意xSh(x)=C0+C1+Ci-1+(kix)mod N)mod Ci。其中其中i=h(x)=(kx)mod N)mod n。69不难证明，函数不难证明，函数h(x)是是SU的一个完备哈希函数。的一个完备哈希函数。上述构造过程实际上要计算上述构造过程实际上要计算2n+1个值：个值：k，k0，k1，kn-1和和C0，C1，Cn-1。时间代价估计为时间代价估计为O(nN)，空间代价为，空间代价为5n+C。4）利用中国余数定理构造）利用中国余数定理构造MPHF 中国余数定理指出：中国余数定理指出：对于任意的对于任意的n个整数个整数R1，R2，Rn，和，和n个互素整数个互素整数M1，M2，Mn，总可以找到一个常数，总可以找到一个常数C，使得，使得Ri=C mod Mi 对对 i=1n成立。成立。为了对关键字集合为了对关键字集合S=k1,k2,kn构造构造MPHF，只须把地址，只须把地址空间空间 0m-1=0n-1(m=n)的每一地址的每一地址0，1，2，n-1视为中国余数定理中的视为中国余数定理中的R1，R2，Rn。k1k2kn与与n个素数个素数建立建立11对应关系：对应关系：P(ki)=Mi i=1,2,n。70于是构造于是构造MPHF的任务归结为找到中国余数定理中的常数的任务归结为找到中国余数定理中的常数C。即令即令h(ki)=C mod P(ki)i=1,2,n。这这种种方方法法的的难难点点是是当当n较较大大时时，C值值的的计计算算代代价价很很高高，下下面面是是一种实用的构造方法，设关键字一种实用的构造方法，设关键字ki为字符串型。为字符串型。对对关关键键字字集集合合S=k1,k2,kn中中的的每每一一个个ki选选其其中中两两个个（或或三三个个）字字符符ki1，ki2，使使不不同同关关键键字字ki，kj对对应应的的字字符符对对ki1,ki2和和kj1,kj2也不同。也不同。按按每每个个关关键键字字ki的的第第一一个个字字符符ki1把把集集合合S分分为为r组组，使使每每组组关关键键字字对对应应的的字字符符对对的的第第一一个个字字符符相相同同，不不同同组组相相异异。这这r个个关键字组按字典顺序记为关键字组按字典顺序记为G1,G2,Gr。若关键字若关键字kiGj，则令，则令 为前为前j-1组的关键字总和。组的关键字总和。71 把把n个关键字对应的个关键字对应的n个字符对中的第二个字符个字符对中的第二个字符k12，k22，kn2（它们中可能有相同的字符）按不同字符在其中出现的（它们中可能有相同的字符）按不同字符在其中出现的频率由大到小分别对应于最小的若干素数：频率由大到小分别对应于最小的若干素数：2，3，5，7，。例如，字符例如，字符e在其中出现频率排在第三位，则令在其中出现频率排在第三位，则令P(e)=5。对于关键字组对于关键字组Gj(j=1,2,r)，设其对应的字符对中第一，设其对应的字符对中第一字符位字符位u（相同），第二字符位（相同），第二字符位v1，v2，vt，则依中国余，则依中国余数定理一定可