《chaptr4 数据集合上的搜(Searching)算法》由会员分享，可在线阅读，更多相关《chaptr4 数据集合上的搜(Searching)算法（92页珍藏版）》请在金锄头文库上搜索。
1、计算机算法计算机算法设计与分析导论设计与分析导论南开大学南开大学 计算机科学与技术系计算机科学与技术系刘璟坡蜜翌秘呢火窒侗酝幅耪老玻菌药描丛糯恨消杰耽台瑰砧蚂问傀铸蓬掠倘chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法1Chapter 4. 数据集合上的搜索数据集合上的搜索(Searching)算法算法 v 4.1 动态数据集动态数据集(Dynamic Set)与抽象数据类型与抽象数据类型(ADT)v 4.2 二叉搜索树二叉搜索树(Binary Search Trees)v 4.3 随机二叉搜索树随机二叉搜索树(Randomly
2、Built Binary Search Tree)v 4.4 红黑树红黑树(Red-Black Tree)v 4.5 2-3-4树树 v 4.6 Hashing技术技术 匆腿助怨说撒榔晓宪矮舍斑兑夯贷渺糟员斤吸页从淹普刚憋内锨魔荷塑跺chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法24.1 动态数据集动态数据集(Dynamic Set)与抽象与抽象数据类型数据类型(ADT)静态数据集静态数据集（Static Set）中的数据是固定不变的。）中的数据是固定不变的。动态数据集动态数据集（Dynamic Set）则是由不断变动的同类型数
3、据元）则是由不断变动的同类型数据元素组成的数据集合。素组成的数据集合。动态数据集（动态数据集（Dynamic Set）可以表示为一个数据元素的数组：）可以表示为一个数据元素的数组： class DynamicSet int setSize; ObjectarraySize elements; . /Object为数据元素的类型，为数据元素的类型，setSize为当前集合中的元素个数为当前集合中的元素个数晚般泌竖谣菏峭厌肘苍赞患韵屎评欢蹦孝埋池冤滞玖靴怪漫瀑效配淆帜坑chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法3用用数数组组表表
4、示示集集合合操操作作方方便便，但但当当集集合合中中的的元元素素个个数数不不断断增增加加时时，数数组组的的长长度度必必须须扩扩大大。一一般般采采用用空空间间倍倍增增（array doubling）技技术术，即即另另外外申申请请一一个个加加倍倍长长度度的的新新数数组组，把把集集合合中的数据传送过来，取代原有的空间。中的数据传送过来，取代原有的空间。其过程为：其过程为： arrayDouble(set) newSize = 2*arraySize ; newElements = new Object(newSize) ; Transfer all elements from the set.elem
5、ents to the newElement; set.elements = newElements ; set.setSize = newSize ; 更为灵活的存储形式是利用指针和链表（例如线性链表和树更为灵活的存储形式是利用指针和链表（例如线性链表和树结构），这种存储形式在搜索算法中经常用到。结构），这种存储形式在搜索算法中经常用到。 危看暑躬任娠隧兆寿薄一适奇苗博梢躺炭周壳侥晶铸夸洗悸侥宋菌慎轿坝chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法4搜搜索索问问题题：在在集集合合中中检检索索出出其其关关键键字字域域的的值值等等
6、于于给给定定值值的的数数据元素。据元素。已知：已知：动态数据集类型动态数据集类型DynamicSet的一个实例的一个实例set和值和值x。求：求：集合集合set中一个元素中一个元素Object element，使，使element.key = x。数据集合上的操作（数据集合上的操作（operation）可以分为两类：）可以分为两类： 查查询询（queries）操操作作：对对数数据据集集不不做做任任何何变变动动，仅仅仅仅返返回回有有关集合的某些信息；关集合的某些信息；修修改改（modifying operations）操操作作：要要对对数数据据集集合合的的某某些些域域进行改动。进行改动。一些典型
7、的操作：一些典型的操作： Search(S,k)：搜索，一个查询操作。对于给定的数据集合搜索，一个查询操作。对于给定的数据集合S和一个关键字值和一个关键字值k，返回，返回S中一个元素（中一个元素（element）的指针）的指针x，使得使得x-key=k。当。当S中没有符合条件的元素时，返回的指针为中没有符合条件的元素时，返回的指针为空（空（NULL）。）。旗掸拒潭店何赐稍蚀霹晕讲侈渊儒劈股饿残匡嚼铃雍滤尔股唱效满揍梯惹chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法5 Insert(S,x)：插插入入，一一个个修修改改操操作作。把
8、把由由x指指向向的的数数据据元元素素加加入入到到集集合合S中中，一一般般假假定定在在x指指向向的的数数据据元元中中，与与集集合合运运算算相相关的所有分量（域）都已经初始化。关的所有分量（域）都已经初始化。 Delete(S,x)：删除，一个修改操作。给定指向集合删除，一个修改操作。给定指向集合S中一个中一个元素的指针元素的指针x，将此元素从，将此元素从S中删除。中删除。 Minimum(S)：求最小元，一个查询操作。若集合求最小元，一个查询操作。若集合S中所有数中所有数据元素的关键字值为一全序集，则返回具有最小关键字值的据元素的关键字值为一全序集，则返回具有最小关键字值的数据元素的指针。数据元
9、素的指针。 Maximum(S)：求求最最大大元元，一一个个查查询询操操作作。返返回回具具有有最最大大关关键字值的数据元素的指针。键字值的数据元素的指针。 Deletemin(S)：删删除除最最小小元元，一一个个修修改改操操作作。它它相相当当于于Minimum(S)和和Delete(S,x)的联合，的联合，即：即：Delete(S,Minimum(S)。 走缮骚陡贤若石趟回牛栽婉丘死傍幻娄迷屋剃筑精蒙惩丑讽京纤株央撅柜chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法6 Successor(S,x)：求求后后继继数数据据元元，一一个
10、个查查询询操操作作。若若S中中的的数数据据元元素素按按关关键键字字值值从从小小到到大大排排列列，x是是指指向向S中中某某一一数数据据元元素素的的指指针针，则则返返回回x所所指指向向的的数数据据元元素素的的下下一一个个数数据据元元素素的的指指针针。若若x指向最后一个数据元素，则返回指向最后一个数据元素，则返回NULL。 Predecessor(S,x)：求求前前导导数数据据元元，一一个个查查询询操操作作。返返回回x所所指指向向的的数数据据元元素素的的前前一一个个数数据据元元素素的的指指针针。若若x指指向向第第一一个个数数据元素，则返回据元素，则返回NULL。 搜搜索索算算法法（及及相相关关操操作
11、作算算法法）的的设设计计实实际际上上是是实实现现适适合合各各种种不同应用需要的不同应用需要的ADT，例如：，例如： 字典（字典（Dictionary）作为抽象数据类型，可以分为两类：）作为抽象数据类型，可以分为两类： 静态字典：（静态数据集静态字典：（静态数据集S，Search）；）； 动态字典：（动态数据集动态字典：（动态数据集S，Search，Insert，Delete）。）。优先队列优先队列（Priority Queue）：（动态数据集）：（动态数据集S，Insert，Deletemin）。）。 斗磊拾梯溢缠粉堪味巩臀茁护屈削拉涡辗巴绪队遮别毫类碍仟粹攻桔擎漾chaptr4 数据集合上的
12、搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法74.2 二叉搜索树二叉搜索树二叉搜索树又称为二元字典树，是一种最常用的动态数据集二叉搜索树又称为二元字典树，是一种最常用的动态数据集的数据结构，可以用于实现字典和优先队列等的数据结构，可以用于实现字典和优先队列等ADT。 v4.2.1 二叉搜索树（二叉搜索树（Binary Search Trees） BST的一个结点与一个数据项相对应，除了数据项的一个结点与一个数据项相对应，除了数据项Object或数或数据项的指针之外，结点主要由关键字据项的指针之外，结点主要由关键字key域和指针域组成，即域和指针域组成，即
13、关键字关键字key与指针与指针left、right和和p，三个指针分别指向该结点的，三个指针分别指向该结点的左儿子、右儿子和父结点。左儿子、右儿子和父结点。 BST中结点的关键字值应满足中结点的关键字值应满足BST性质：性质： 即，设即，设x是二叉搜索树的一个结点，结点是二叉搜索树的一个结点，结点y位于结点位于结点x的子树中，的子树中，x、y的关键字值应满足以下关系：的关键字值应满足以下关系：酥阁羞啸能朽伺蝴截奉压培锡垃钞阉裁喀蚀叙菜收月岗间一却扇痹达广帜chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法8如果如果y是是x的左子树中
14、的一个结点，则的左子树中的一个结点，则y-keyx-key；如果如果y是是x的右子树中的一个结点，则的右子树中的一个结点，则y-keyx-key。Fig.4.1给出了由给出了由6个结点（数据项）组成的两个二叉搜索树。个结点（数据项）组成的两个二叉搜索树。两个两个BST(a)和和(b)有不同的树高，前者比后者的查询效率更高。有不同的树高，前者比后者的查询效率更高。 谨夺谁督量执排缴戏片雍胚扛胞当绞她韩首屎腻坦吊恶琐蚜朵钵垦簧党陡chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法9遍遍历历二二叉叉搜搜索索树树的的所所有有结结点点可可以以
15、采采用用中中序序遍遍历历（inorder tree walk）算算法法，即即可可将将与与二二叉叉搜搜索索树树树树结结点点相相对对应应的的数数据据项项按按关键字从小到大排列出来。关键字从小到大排列出来。 中序遍历（中序遍历（Inorder_Tree_Walk）算法）算法v4.2.2 查询（查询（Querying）的实现）的实现对对二二叉叉搜搜索索树树的的查查询询主主要要是是Search、Minimum、Maximum、Successor、Predecessor等等操操作作，这这些些操操作作都都可可在在O(h)时时间间内内完成，其中完成，其中h是二叉树的高。是二叉树的高。如如Fig.4.2所示，所
16、示，BST查询操作查询操作为为Tree_Search(root,k)，即搜索，即搜索BST上关键字值为上关键字值为k的结点。的结点。 Tree_Search算法算法 紫脑捶纬平缺苹畔钞憾健狐粘童欢稻扑毁抠吞遁悟大莫诅浸狰拯河撒呢岳chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法10求求最最小小元元（或或最最大大元元）的的操操作作只只需需从从根根开开始始沿沿着着左左指指针针（或或右右指指针针）一一直直搜搜索索至至某某一一结结点点x，其其left或或right指指针针为为NULL，这时结点这时结点x的关键字的关键字x-key为最小（或
17、最大）。为最小（或最大）。求最小元的算法求最小元的算法Tree_Minimum(root)求最大元的算法求最大元的算法Tree_Maximum(root)求求数数据据项项的的后后继继与与前前导导项项的的操操作作要要相相对对复复杂杂，如如Fig.4.2，结结点点15（指指关关键键字字为为15的的结结点点)的的后后继继是是结结点点17，它它是是结结点点15的的右右子子树树中中的的最最小小元元。然然而而对对于于没没有有右右子子树树的的结结点点，例例如如13、4和和17，其其后后继继分分别别为为15、6和和18，显显然然计计算算这这三三个个结结点点的的后后继继时时需要使用父结点指针需要使用父结点指针x
18、-p。求后继项的操作算法求后继项的操作算法 Successor(x) 督全傍聪漓赤蛊姚塑缎赢据沤今钻照蜕屉浩肠笋黔迅婉试阁狼拢拯氢歉闹chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法11Successor(x)操操作作根根据据条条件件x-right!=NULL决决定定两两种种情情形形：第第一一种种情情况况从从结结点点x下下行行，直直到到叶叶结结点点，其其路路长长显显然然不不超超过过树树高高h；第二种情况从结点；第二种情况从结点x上行，路长同样不超过上行，路长同样不超过h。因此有下面的结论：因此有下面的结论： 定定理理4.1 动动态
19、态数数据据集集合合的的查查询询操操作作Search、Minimum、Maximum、Successor、Predecessor可可通通过过二二叉叉搜搜索索树树实实现现，其算法可在其算法可在O(h)时间内完成，其中时间内完成，其中h为二叉搜索树的高。为二叉搜索树的高。v4.2.3 插入与删除操作插入与删除操作动动态态数数据据集集上上的的Insert(S,x)、Delete(S,x)操操作作与与查查询询操操作作不不同同，它们会引起二叉搜索树本身的变化。它们会引起二叉搜索树本身的变化。插入操作算法插入操作算法Tree_Insert 乙针栓霞奴肖贫匣葡飞颧道纵医衅蒙舰痪贱敦硒浇侨裸督旦钵蛛抠孝肝铆ch
20、aptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法12Fig.4.3表表示示把把新新的的数数据据项项14（关关键键字字值值为为14）作作为为新新结结点点插插入入到二叉搜索树的过程。到二叉搜索树的过程。膳擞滞仲劫枢填驼腐笛号净参糟诞竞麓食往外皆翁炕仓夜夕钧臃捌峦乒卤chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法13从从二二叉叉搜搜索索树树中中删删除除一一个个结结点点的的算算法法比比较较复复杂杂，假假定定待待删删除除结点指针结点指针z不为不为NULL，有三种情形：，有三种情形
21、：（1）结点结点z没有子结点，可直接删除；没有子结点，可直接删除；（2）结点结点z只有一个子结点，可使只有一个子结点，可使z的父结点的父结点z-p直接指向直接指向z的子结点的子结点z-left或或z-right；（3）结点结点z有两个子结点，则有两个子结点，则z的后继结点的后继结点y必然在必然在z的右子树中，且的右子树中，且y无左无左子结点，按步骤（子结点，按步骤（1）或（）或（2）删除结点）删除结点y，用，用y的数据取代的数据取代z的数据。的数据。过程如图所示：过程如图所示： 蛊秆对泻郎枫甚娱缆殷骄韵忌防禄掸匙哈舱澜烈束媳痊拟渤雷仰缅蜂疚协chaptr4 数据集合上的搜(Searching)
22、算法chaptr4 数据集合上的搜(Searching)算法14猾丧鼠甜照令数摊啸需根氏慰睦库怔桃舌胖螺壮厚怠盒堡涌圣粤镰焕灸路chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法15删除操作算法删除操作算法 Tree_Delete这这个个算算法法除除了了调调用用函函数数Tree_Successor(root,z)的的时时间间代代价价为为O(h)外，其余各处的时间代价均为外，其余各处的时间代价均为O(1)阶。阶。Tree_Insert(root,z)的的运运行行是是在在从从根根到到某某一一个个叶叶结结点点的的一一条条路路径上进行的，因
23、此有下面的结论。径上进行的，因此有下面的结论。 定定理理4.2 动动态态数数据据集集的的Insert(S,x)、Delete(S,x)操操作作可可通通过过二二叉叉搜搜索索树树实实现现，其其算算法法可可在在O(h)时时间间内内完完成成，其其中中h为为二二叉叉搜搜索树的高。索树的高。认串剑雀潜巍隧剧场祭馅贿燃蛊涵黑停馆荧二凛拖货受险好抄立杆钮洗兹chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法164.3 随机二叉搜索树随机二叉搜索树随机二叉搜索树（随机二叉搜索树（Randomly Built Binary Search Tree）：）
24、：一个由一个由n个结点（具有个结点（具有n个不同的关键字）按随机顺序，经过个不同的关键字）按随机顺序，经过n次次Tree_Insert操作插入到一个原始空树而得到的二叉搜索树，操作插入到一个原始空树而得到的二叉搜索树，称为随机二叉搜索树（称为随机二叉搜索树（RBST）。这里的按随机顺序是指，）。这里的按随机顺序是指，n个不同关键字的个不同关键字的n!种不同排列的出现是等可能的。种不同排列的出现是等可能的。定理定理4.3 由由n个不同的关键字组成的随机二叉搜索树的平均树个不同的关键字组成的随机二叉搜索树的平均树高为高为h=O(logn)。 该定理的证明基本思路与步骤：该定理的证明基本思路与步骤：
25、1. 有关概率分布的假设：有关概率分布的假设：假定关键字输入序列假定关键字输入序列k1,k2,.,kn为为n个不同值的一种排列，设各个不同值的一种排列，设各种不同排序为等可能的，因此这一特定排序出现的可能性为种不同排序为等可能的，因此这一特定排序出现的可能性为1/n!。锋聊酮镇付哈寝荒雇奶贬歧届荤熔妓久靴摸也潞匠猪野工判坚孟粪缠胁鹤chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法17假假定定：对对任任一一j值值（1jn），kj取取n个个关关键键字字其其中中任任意意一一个个的的概率为概率为1/n，也是等可能的。，也是等可能的。 2.
26、 在在RBST中结点中结点x为结点为结点y的祖先的充要条件：的祖先的充要条件：首先分析从根到树上任一结点首先分析从根到树上任一结点y（y-key=kj,1key= ki）都具有下列特征：）都具有下列特征： 其对应的关键字其对应的关键字ki在输入关键字序列中位于在输入关键字序列中位于kj之前，即之前，即1ikey=ki）在）在T中是结点中是结点y（y-key=kj）的祖先的充要条件是：）的祖先的充要条件是：辕恨倾饮呀辕议裤少蠕吁炮堑潦乾傅始乾伞报碳砰讣凳岔莱呛啤绒趁磺裤chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法18在在Fig.
27、4.5中中，kj=17。从从图图(a)中中可可以以看看到到，从从根根到到结结点点17的的路路径径上上的的4个个结结点点的的关关键键字字都都符符合合上上述述条条件件，而而且且，从从(b)表表中中的的关关键键字字序序列列中中可可以以看看出出，关关键键字字17前前面面的的10个个关关键键字字中中满满足足命题命题4.1条件的关键字条件的关键字21、19、9、12全是结点全是结点17的祖先。的祖先。粹米饭糙朴柏捐考昌鹃獭赡妥谬锗霞灶恃险红挽丧蝴蜀宏患壁癌铂奄唯梭chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法193. 求求RBST中任一结点
28、的深度中任一结点的深度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）的的路路径径上上，结结点
29、点的的关关键键字字集集合合恰恰为为GjLj，且，且d(kj,T)=|Gj|+|Lj|。 弯艘丑难椭磅咀磋蛰摊肯航阎锣剔边磋加滑闻魂铺仟臀皑尸疽酶屡桃里惜chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法20从从Fig4.5的实例中可以看到，对于的实例中可以看到，对于kj =17，Gj=21，9，Lj =9。12，所以，所以kj的深度为的深度为4。 怕馅恢庙永屹贞体邀受昨钾害蝉婪炙淄斩棘干锐梗属坚数仕栋弛膊蕉呢枯chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法214.4
30、红黑树（红黑树（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
31、），空结点与实际的数据元素或关键），空结点与实际的数据元素或关键字都无关。字都无关。一个在结构上做了上述改变的二叉搜索树称为一个一个在结构上做了上述改变的二叉搜索树称为一个RB树树 。 躁傻卸痈瓤卒韭涎窄淖踌颠衣翼争考拌徊份劲导狱随碉佑纵枢毛牲舅鲸监chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法22救壬严厘胃杯撕漳团股蒲豁揽冬淆闸沦史呼驯迄迢碟贞蝴毛钧绸奠耙交珠chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法23RB树满足下面的性质：树满足下面的性质：1. 每个结点
32、的每个结点的color域必须为域必须为red或或black；2. 每个叶结点（每个叶结点（NULL）的）的color为为black；3. 如果一个结点的如果一个结点的color为为red，则其子结点全为，则其子结点全为black结点。结点。4. 从某一结点到其子树上任意一个叶结点的所有简单路径，包含相同个数从某一结点到其子树上任意一个叶结点的所有简单路径，包含相同个数的的black结点。结点。从一个结点从一个结点x到（其子树中的）任一叶结点的简单路径上的黑到（其子树中的）任一叶结点的简单路径上的黑结点的个数称为结点结点的个数称为结点x的的black高（高（black-height），表示为），
33、表示为bh(x) 。定理定理4.4 具有具有n个内部结点的个内部结点的RB树的树高树的树高 h 2ln(n+1)。证明：证明：1. 首先用归纳法证明以首先用归纳法证明以RB树上任一结点树上任一结点x为根的子树至少为根的子树至少包含包含 个内部结点。个内部结点。饥狮肉答匹役心送磕翼庙氏撵赐泳一左乾获墩逸凭此辩从碟喇恍静祈擒址chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法241递递归归基基础础：对对于于高高度度为为0的的结结点点x，即即x为为叶叶结结点点（NULL），以其为根的子树有以其为根的子树有0个内部结点，即至少有个内部结点，
34、即至少有 个内部结点。命题成立。个内部结点。命题成立。2设对于高度为设对于高度为h-1的结点命题成立。的结点命题成立。 3考考察察高高为为h(0)的的结结点点x，由由于于h0，x是是RB树树的的内内部部结结点点，必有两个子结点必有两个子结点x1、x2，其高为，其高为h-1，且有，且有根据归纳假设，以根据归纳假设，以x1、x2为根的两子树分别至少有为根的两子树分别至少有 个内部结点，个内部结点，以以x为根的子树至少有为根的子树至少有 个内部结点。个内部结点。归纳完成。归纳完成。纷审险酚妇逐毫咖温玖孵茵施惟悸值司匆邪种截酮飞埂衔狈悔布屉光溪桂chaptr4 数据集合上的搜(Searching)算法
35、chaptr4 数据集合上的搜(Searching)算法252. 证明对于证明对于RB树的根树的根r，设其高为，设其高为h，bh(r)h/2。这这一一点点由由性性质质3，即即从从根根到到叶叶的的任任一一条条路路上上，red结结点点数数不不超超过一半即可证明。过一半即可证明。3. 由上面两个命题可知：高为由上面两个命题可知：高为h的的RB树，其内部结点数树，其内部结点数n至少为至少为 ，即即 。故有故有 ，定理得证。，定理得证。 定定理理4.4说说明明，动动态态数数据据集集上上的的基基本本操操作作在在RB树树上上的的执执行行代代价价为为O(h)=O(logn) 阶阶。换换句句话话说说，用用RB树
36、树的的形形式式实实现现动动态态数数据据集，在任何时刻，树高集，在任何时刻，树高h总能保持在总能保持在O(logn) 阶。阶。炬耳柜嘿侩渍惰实验活间炸鬼校展细觉褪患硒杆蚁韧碟础尧锨泡楔倘倍虱chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法26v4.4.2 Red-Black树的插入与删除算法树的插入与删除算法 在插入或删除结点时，为了使树重新具有在插入或删除结点时，为了使树重新具有Red-Black性质，除性质，除了要改变结点间的指针链接关系外，还要对某些结点的着色了要改变结点间的指针链接关系外，还要对某些结点的着色进行调整。进行调
37、整。对于结点间指针链接关系的修改归结为对于结点间指针链接关系的修改归结为旋转旋转（Rotation）操作，）操作，旋转是调整树的平衡状态的基本手段。旋转是调整树的平衡状态的基本手段。Rotation操作对二叉搜索树上的某一局部进行调整，通过交换操作对二叉搜索树上的某一局部进行调整，通过交换一对父子结点的父子关系，在保持树结点间的有序关系的条一对父子结点的父子关系，在保持树结点间的有序关系的条件下（即保持其中序遍历的结果为单调序列），改变该子树件下（即保持其中序遍历的结果为单调序列），改变该子树的平衡状态。的平衡状态。版构岸照奥邱沂玛蓑曾篱蛮精沙橇誉箱皿贵蒸步笆朽下洒筒藉潭患增擎诌chaptr4
38、 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法27Rotation操作分为左旋（操作分为左旋（Left-Rotation）和）和右旋右旋(Right-Rotation)，如，如Fig.4.7所示。所示。 纶伯肿彭闸耀微滇交沁茹师追蛆郑焕搅执溶坤盔航亿潞兜蔷督查铡碘字仰chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法28左旋算法左旋算法Left_Rotation(root,x)Fig.4.8给给 出出 一一 次次 左左 旋旋 转转 的的 实实 例例 的的 图图 示示 。 Right
39、_Rotation(root,x)的算法与的算法与Left_Rotation(root,x)类似。类似。 桃先谗测釉秽侣纺暇乡笼罚怀嘿勉标忱橇靴阜刁邻芭甲需脏些骆捐雕侍副chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法29这个算法主要完成两件事：这个算法主要完成两件事： 1把结点把结点x与其左子结点与其左子结点y的父子关系进行调整，的父子关系进行调整，即把即把x-pxy的父子关系改变为的父子关系改变为x-pyx的顺序；的顺序；2把把y的左子树变为的左子树变为x的右子树。的右子树。算法不存在与结点数算法不存在与结点数n相关的操作，因
40、此时间代价为相关的操作，因此时间代价为O(1)阶。阶。RB树的插入操作，首先调用树的插入操作，首先调用Tree_Insert(root,x)函数完成二叉函数完成二叉搜索树的插入操作，然后调用搜索树的插入操作，然后调用Tree_Rotation(root.x)函数，并函数，并对结点的着色进行调整，使之恢复为一个对结点的着色进行调整，使之恢复为一个RB树。树。 插入操作算法插入操作算法RB_Insert(root,x) 男谦勿沛吃日浦磅裔襄厦帧羽专月青烁囱写悬赴枪悯峨味作送凯抛棍姨墟chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法30
41、Fig.4.9给给出出了了一一个个简简 单单 的的 实实 例例 ， 作作 为为 RB_Insert()算算法法运运行行的的示示意意图。图。主泳挛尺禹能香狞顺结沮撞尹椎拄磋斤徽榜己悼瞅昼斤补罐诞韭蔗孪鸟塔chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法31从算法从算法RB_Insert()的执行过程可以看出：的执行过程可以看出：1对于空树或插入后对于空树或插入后x-p为为black结点的情形，无需进一步处结点的情形，无需进一步处理；理；2x-p为为red结点时，首先按结点时，首先按case1处理，对以处理，对以x-p-p为根的为根的
42、子树进行调整，然后向上扩展，分别按子树进行调整，然后向上扩展，分别按case2、case3处理。处理。RB树的树的Delete算法与算法与RB_Insert()算法的思路是一致的，首先算法的思路是一致的，首先按二叉搜索树的删除方法删去需要删除的结点。在删除过程按二叉搜索树的删除方法删去需要删除的结点。在删除过程中会出现三种情形，在第二、三种情形中，若被摘除中会出现三种情形，在第二、三种情形中，若被摘除（spliced-out）结点是）结点是black结点，这时结点，这时Red-Black性质性质4可能可能被破坏，就需要对被破坏，就需要对RB树进行恢复，恢复方法与插入操作后的树进行恢复，恢复方法
43、与插入操作后的修复类似。修复类似。 髓机利猪姚钮默公僧枫伤瘸馒衫里位瑟反屡廓忌熄强鸯吕颐她痉旦梦桔坤chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法32v4.4.3 关于关于Red-Black树的几点讨论树的几点讨论 1. RB树树是是一一种种二二叉叉搜搜索索树树，在在其其上上进进行行的的查查询询操操作作Search、Minimum、Maximum、Successor、Predecessor等等与与一一般般二二叉叉搜搜索索树树的的查查询询操操作作完完全全相相同同，而而且且算算法法简简明明，也也即即RB树树具具有一般二叉搜索树的优点
44、。有一般二叉搜索树的优点。2. 如如定定理理4.4所所指指出出的的，RB树树是是平平衡衡树树，在在其其上上进进行行的的所所有有操操作作的的时时间间代代价价都都是是O(logn)阶阶的的，RB树树的的树树高高h总总是是保保持持在在一一个很小的范围，即个很小的范围，即h2ln(n-1) 。3. RB树树与与一一般般平平衡衡树树的的平平衡衡机机制制不不同同，虽虽然然它它不不需需要要计计算算平平衡衡因因子子，但但Red-Black性性质质（特特别别是是性性质质4）保保证证了了整整棵棵树树的的平衡性，即绝大多数内部结点有两个子结点。平衡性，即绝大多数内部结点有两个子结点。事事实实上上，red结结点点不不
45、可可能能仅仅有有一一个个black子子结结点点，而而只只可可能能为为以以下下两两种种情情形形之之一一：有有两两个个black（数数据据）子子结结点点；或或左左、右右子子结点均为结点均为NULL。 还廊眨煞通来试券愁缨制禽往衬赠梧版侠匀疑塑少钳曝每肯屠出书刷蘸缄chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法33black结结点点的的子子结结点点有有三三种种情情形形：有有两两个个（数数据据）子子结结点点；左左右右子子结结点点为为NULL；第第三三种种情情形形只只可可能能出出现现在在树树的的下下层层，只只有有一一个个数数据据子子结结点
46、点，这这时时该该子子结结点点必必为为red，且且子子结结点点左左右右儿儿子子为空。如为空。如Fig.4.10所示。所示。RB树树几几乎乎是是一一个个2-树树，不不可可能能出出现现单单链链的的情情形形，从从而而保保证证了了整棵树的平衡性。整棵树的平衡性。 4. 另另一一种种非非二二叉叉的的平平衡衡搜搜索索树树2-3-4树树，很很容容易易转转变变为为Red-Black树。树。煎辐魏灌炙坷牺藏疚幼坪蔗黍虱宛萌捡获周写炽募宙颠台商挎工舷乎乾窄chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法344.5 2-3-4树树 v4.5.1 2-3-
47、4树及其实例树及其实例 1. 2-3-4树有三种不同的结点：树有三种不同的结点：2-结点、结点、3-结点和结点和4-结点。结点。 2-结点与二叉树的结点相同，除了关键字域结点与二叉树的结点相同，除了关键字域key外，有三个指外，有三个指针域针域p、p1、p2，p指针指向父结点、指针指向父结点、p1指针为左指针、指针为左指针、p2指指针为右指针。另外增加一个结点类型域针为右指针。另外增加一个结点类型域type，用来区分结点类，用来区分结点类型。数据域保持数据元素的内容或指向数据元素的指针型。数据域保持数据元素的内容或指向数据元素的指针 。3-结点有两个关键字域结点有两个关键字域key1和和key
48、2，其中，其中key1key与与key1、key2进行进行比较，如相等即找到，不相等则根据比较结果的三种情形转比较，如相等即找到，不相等则根据比较结果的三种情形转入该结点的子树：入该结点的子树： x-key key1 转向转向p1； key1 key key key2 转向转向p3。慌罢癸管写荷笆外每夜斋饯更汽桐烩撂镭冲严移祝希对倒游穷冶颤焦还凿chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法354-结点与结点与3-结点类似，增加了结点类似，增加了key3域和域和p4指针。在指针。在2-3-4树种，树种，4-结点是一种临时结点，在
49、插入和删除过程中可能产生结点是一种临时结点，在插入和删除过程中可能产生4-结点，结点，但该结点可随时由三个但该结点可随时由三个2-结点取代。结点取代。2. 2-3-4树的最主要的特征是其所有的叶结点都在同一深度。树的最主要的特征是其所有的叶结点都在同一深度。如如Fig.4.11所示：所示：假定动态数据集的关键字值域为英语字母集合，即从小到大假定动态数据集的关键字值域为英语字母集合，即从小到大为为A,B,C,D,E,.,X,Y,Z。图中的结点图中的结点I是根，是一个是根，是一个2-结点，其左子树中的关键结点，其左子树中的关键字值均小于字值均小于I，右子树中的，右子树中的关键字值均大于关键字值均大
50、于I，该树，该树T中中只有只有2-结点和结点和3-结点。结点。做滨舜孺梳鸟诬跳獭擂涪敝裙餐诀塞闻肌谈中迈镶鼓化侠顿袒整蕴簧弹炬chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法36v4.5.2 2-3-4树上的查询操作算法树上的查询操作算法 2-3-4树树上上的的搜搜索索算算法法与与二二叉叉搜搜索索树树上上的的搜搜索索算算法法差差别别不不大大，只需要区别只需要区别2-结点和结点和3-结点。结点。 2-3-4树的搜索算法树的搜索算法v4.5.3 2-3-4树的构造过程树的构造过程 2-3-4树树的的插插入入算算法法是是保保证证树树的的
51、基基本本特特征征（即即所所有有叶叶结结点点在在同同一一深深度度）的的关关键键。在在插插入入时时，2-结结点点可可以以变变为为3-结结点点，3-结结点点可可以以变变为为4-结结点点，当当出出现现4-结结点点时时，自自动动分分裂裂为为三三个个2-结结点点，并且把中间的并且把中间的2-结点插入到上一层的父结点中。结点插入到上一层的父结点中。在在一一般般二二叉叉搜搜索索树树中中，每每插插入入一一个个结结点点是是在在最最下下层层添添加加一一个个叶结点，而叶结点，而2-3-4树是在整体扩大的情况下进行向上扩展。树是在整体扩大的情况下进行向上扩展。每当树增加一层时，即是把根结点上升一层，于是树中所有每当树增
52、加一层时，即是把根结点上升一层，于是树中所有结点的深度同时加结点的深度同时加1。 灿陈间竿宾方噶几遵耍微合侣撤钟窘纽赦击薛粹齐驰驼担路吕抓回欲牲奈chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法37捧习疼枝曹豫撂鲤纫殆超巡仓棱彬廉法共炎蜒撑额六软伐惊抑咳沧朝父贝chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法38在在插插入入算算法法中中，一一旦旦产产生生了了4-结结点点就就要要进进行行分分裂裂，这这时时就就会会利利用到父结点指针用到父结点指针p。在。在4-结点分裂时，
53、存在三种情形：结点分裂时，存在三种情形：(1) 4-结点是结点是2-3-4树的根，这时，中间的树的根，这时，中间的2-结点作为新的根，结点作为新的根，树增加一层；树增加一层；(2) 4-结点的父结点是一个结点的父结点是一个2-结点，只需把结点，只需把4-结点中的中间关结点中的中间关键字插入到键字插入到2-结点，该结点，该2-结点变为结点变为3-结点；结点；(3) 4-结点的父结点是一个结点的父结点是一个3-结点，把结点，把4-结点的中间关键字插结点的中间关键字插入到这个入到这个3-结点中，该结点中，该3-结点又变成一个新的结点又变成一个新的4-结点，于是继结点，于是继续向上分裂。续向上分裂。假
54、设插入时树高为假设插入时树高为h，插入过程在最坏情形下是从根到叶、再，插入过程在最坏情形下是从根到叶、再从叶到根，至多进行从叶到根，至多进行2h次处理，因此插入算法的时间代价仍次处理，因此插入算法的时间代价仍是是O(h)阶的。阶的。 氦浸阔插爸詹正札京烈腻尘哄娥撇揖掀斑咎射运票葱盅尖薄虎脑症瓦沾讹chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法39v4.5.4 2-3-4树的性能分析树的性能分析 定定理理4.5 由由n个个关关键键字字生生成成的的2-3-4树树实实际际上上是是一一个个完完全全的的2-3树树，设设其其高高为为h，结结
55、点点数数为为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-结结点点是是
56、临临时时结结点点，不不会会占占用用较多空间，可以分配临时性的工作单元存放较多空间，可以分配临时性的工作单元存放4-结点。结点。搁颐付祝素意症苇众凝睦痕祟倒冕碱钧绒撤曲部阑蹄陇宣坟庭梭梅似虫拧chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法402. 可以采用同一种数据类型来表示可以采用同一种数据类型来表示2-结点和结点和3-结点（按结点（按3-结点结点来设计），只在来设计），只在type域用不同的标记来区分结点类型即可。域用不同的标记来区分结点类型即可。3. 为了减少插入算法的代价，还有一种把分裂为了减少插入算法的代价，还有一种把分
57、裂4-结点的工作分结点的工作分摊到不同的操作中去的方案，即每次生成摊到不同的操作中去的方案，即每次生成4-结点时进行一次分结点时进行一次分裂，如果其父结点又变为裂，如果其父结点又变为4-结点，则不在这一次插入操作中继结点，则不在这一次插入操作中继续分裂。当进行下次插入或搜索操作时，每遇到一个续分裂。当进行下次插入或搜索操作时，每遇到一个4-结点就结点就进行一次分裂，这样可以减少一次插入操作的代价。进行一次分裂，这样可以减少一次插入操作的代价。4. 与插入算法相比，删除操作与插入算法相比，删除操作Delete算法是一个逆过程。插入算法是一个逆过程。插入操作中，关键字要按规则逐层向上插入，而删除操
58、作应在删操作中，关键字要按规则逐层向上插入，而删除操作应在删除其关键字后按一定规则逐层向下压，除其关键字后按一定规则逐层向下压， 腾烙指弱洛去饿疯陷鸟叼拌犹搪望毋诲滦慈脓钞浦浪郡宣咏私蓑禽尚鸥段chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法415. 2-3-4树树获获得得平平衡衡性性的的方方法法很很巧巧妙妙，但但缺缺点点是是结结点点类类型型较较为为复复杂杂，可可以以通通过过一一种种简简单单的的变变换换把把2-3-4树树转转化化为为二二叉叉搜搜索索树树。方方法法是是把把2-3-4树树中中的的3-结结点点（或或4-结结点点）用用一一
59、个个2-结结点点结结构构来来取代，取代的方法如取代，取代的方法如Fig.4.13所示。所示。瞩稳骡事乘巍皇绞侧砰程褒必运悉硼支妊它乾挥阜培钳淮榴唐老娱框洗痞chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法42用用上上述述变变换换将将Fig.4.11中中的的2-3-4树树转转化化为为一一个个二二叉叉搜搜索索树树，不不难难发发现现，这这是是一一棵棵RB树树。从从中中也也可可以以看看出出RB树树与与2-3-4树树的的内在联系。内在联系。曾贝扬酮橙掠洪旅扮蹲柔抵诗渗卿僵之节擅教驴渭镇公肌窑炳碌咸陪疙哪chaptr4 数据集合上的搜(Sea
60、rching)算法chaptr4 数据集合上的搜(Searching)算法434.6 Hashing技术技术 v4.6.1 Hash算法的基本思想与一般模型算法的基本思想与一般模型 Hash方法的基本思想是，首先产生从可能的关键字集合（又方法的基本思想是，首先产生从可能的关键字集合（又称全域）称全域）U=0.N-1到存储空间（到存储空间（Hash表）地址集合表）地址集合T=0.m-1的一个映射函数：的一个映射函数：h:U0.m-1。于是，要存储或检索关键。于是，要存储或检索关键字为字为xU的数据项只需计算函数的数据项只需计算函数h(x)，直接得到该数据项应，直接得到该数据项应在的地址。在的地址
61、。Fig.4.15中给出了一个简单中给出了一个简单的实例，其中的实例，其中N=100，m=7，h(x)=xmod7。店憋甫洞庙薛误痘蛾慷爹锭晰蛙隋刊苇侈欢胚椎宪人矩馆阮抄统塞补加溺chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法44然然而而对对不不同同的的关关键键字字x,yU，h(x)=h(y)的的情情况况可可能能出出现现，这这种种情情形形称称为为冲冲突突（collision）。由由于于一一般般的的|U|远远远远大大于于m，冲冲突难以避免，因此突难以避免，因此Hash技术研究的基本问题是：技术研究的基本问题是： (1)设计一个好的
62、设计一个好的Hash函数，计算简单，而又使数据项分布均函数，计算简单，而又使数据项分布均匀以减少冲突；匀以减少冲突；(2)设计解决冲突的策略和算法。设计解决冲突的策略和算法。集合集合 为实际存于为实际存于Hash表中的关键字集合，表中的关键字集合，|S|=nN。 = n/m 称为负载因子（称为负载因子（load factor）, 值是决定哈希算法值是决定哈希算法性能的主要因素。性能的主要因素。Hash算法的算法的“散列散列”存储方式，使得它不能支持存储方式，使得它不能支持Minimum、Maximum、Successor、Predecessor、Mindelete这类的操作，这类的操作，而对于
63、而对于Search、Insert、Delete操作不但可以支持而且有较高操作不但可以支持而且有较高的性能。的性能。 衬偏琉蛙楞椿燥呻已茸医秉双斜汹罐信冈画释欢攘影畸戌砚辐年劫揽痹许chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法45从从抽抽象象数数据据类类型型（ADT）的的观观点点来来说说，Hash算算法法用用于于实实现现字字典典（Dictionary）类类型型，实实际际关关键键字字集集合合S为为固固定定不不变变时时，称称为为静静态态字字典典，只只支支持持Search操操作作，S为为可可变变时时，即即动动态态数数据据集集，称为称为
64、动态字典动态字典，动态字典支持搜索、插入和删除操作。，动态字典支持搜索、插入和删除操作。v4.6.2 Hash函数的设计函数的设计 Hash函函数数的的设设计计一一般般应应能能兼兼顾顾计计算算简简单单和和分分布布均均匀匀，在在大大多多数数应应用用问问题题中中，可可能能的的关关键键字字集集合合U往往往往远远远远大大于于地地址址空空间间的的规规模模。例例如如以以姓姓名名字字符符串串作作为为关关键键字字，|U|=N是是一一个个极极大大的的值值，而而Hash表表的的长长度度m和和实实际际关关键键字字集集合合S（|S|=n）与与N相相比比小小得得多。因此，分布均匀的要求就是要对于多。因此，分布均匀的要求
65、就是要对于使使 尽量小，尽量小，其中其中h-1(i)为被为被h映射至地址映射至地址i的关键字全体。的关键字全体。滤掠嫂面循卉算骋叙晶显卖疑糕塘铃漓尤惕藉邯咬甚耻聂牟锋滨自顺屿毕chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法46当且仅当当且仅当 时达到最小值，意味着时达到最小值，意味着将将无无任任何何冲冲突突产产生生。无无冲冲突突的的Hash函函数数称称为为完完备备HashHash函函数数（Perfect Hash Function），简称），简称PHF。事事实实上上，无无冲冲突突的的要要求求是是极极难难达达到到的的。“生生日日悖
66、悖论论”指指出出，在在23个个人人中中，有有两两个个人人的的生生日日在在同同一一天天的的概概率率为为0.51，即即当当|S|=n=23，m=365时时，发发生生冲冲突突的的概概率率已已经经在在50%以以上上。而而当当n=50时时，发发生生冲冲突突的的概概率率已已达达0.97。在在D.Knuth所所举举的的实实例例中中指指出出，当当n=31，m=41时时，无无冲冲突突的的映映射射函函数数只只占占全全部部可可能能映映射射函函数数的的1/107。因因此此，在在大大多多数数情情形形下下只只能能追追求求将将冲冲突突尽尽可可能减少。能减少。常用的常用的Hash函数设计方法：函数设计方法：1. 除式法（除式
67、法（Division method）令令h(x)取用取用m除除x的余数，即的余数，即h(x)=xmodm。菇贯间茂嗅戎壁混诽辙墨盈醛芦泥滇蹋秘遍凳篓善酶帮什欧帖原扩扯耗森chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法47这这种种Hash函函数数计计算算速速度度最最快快。在在设设计计时时，m取取值值不不要要习习惯惯性性地地取取为为2的的n次次幂幂。因因为为这这会会使使得得h(x)的的取取值值只只依依赖赖于于关关键键字字的的2进进制制值值的的最最后后几几位位，这这不不利利于于数数据据在在Hash表表中中的的均均匀匀分分布布。一般情况
68、下一般情况下m值最好取为不与某个值最好取为不与某个2n值相近的素数。值相近的素数。2. 乘式法（乘式法（Multiplication method）可方便地取可方便地取m=2p，映射函数可表示为：，映射函数可表示为：其中其中a为常数为常数0a0.95 时，扩大时，扩大Hash区，区，即即所所谓谓空空间间倍倍增增（array doubling）技技术术，需需要要把把数数据据集集中中的的所所有有数数据据按按照照新新的的Hash函函数数重重新新转转存存入入新新的的Hash区区，这这一一工工作代价很大。作代价很大。为为解解决决空空间间倍倍增增所所需需的的高高代代价价问问题题，可可采采用用线线性性扩扩张
69、张Hash算算法。基本思想是指定一对负载因子法。基本思想是指定一对负载因子 的上限的上限 和下限和下限 ，在可能关键字集合在可能关键字集合S的大小的大小n改变的过程中，一旦改变的过程中，一旦 超过超过 ， 存储区扩充一个桶（可存放存储区扩充一个桶（可存放b条数据项），当条数据项），当 小于小于 时，时，存存储储区区缩缩减减一一个个桶桶。这这样样就就保保证证动动态态数数据据集集上上的的操操作作总总是是在在良好的性能下工作。良好的性能下工作。v*4.6.5 Hash技术的几种新发展技术的几种新发展 1. 完备完备Hash函数（函数（Perfect Hash Function） 静龚傀犹吞串潭柄实持
70、土梭骆愤返愈暖络零叭懂扭十篇暴能甥竣妹容械挥chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法63完完备备哈哈希希函函数数（PHF）又又称称无无冲冲突突哈哈希希函函数数。即即PHF的的地地址址映映射射不不产产生生冲冲突突，一一次次计计算算即即可可找找到到目目标标数数据据项项。因因此此，用用PHF实实现现的的检检索索算算法法的的最最好好平平均均和和最最坏坏情情形形时时间间复复杂杂度度都都为为O(1)阶。其定义可叙述为：阶。其定义可叙述为：对任一时间关键字集合对任一时间关键字集合 ，函数函数h： 称为称为S的完备哈希函数（的完备哈希函数
71、（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的首末字符。的首末字符。豆伪新换逾爸
72、椒拷炔扼氯牲崖帜侗司睁强德库鹤挝号猜循汞迁兼褥教栗淬chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法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提出的一种改
73、进方法，是求形如：提出的一种改进方法，是求形如：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表。表。
74、 潜钦魏您皋镭修缚定瑟朔甲翁酣趁鳃摇滦泞借侵窿齐革痘面潜蚜尧辖吧绎chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法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的算法为：的算法
75、为：void writeHIT (key K) int j=1;while (HIThj(k) != j) &(j = t)j+;if (j = t)Thj(k) = k;elsecout failure!;彼天糕袭万默芯秉荷皂芋踞东捎弗彤特摘财商睦板输耪组必磨毡长瑟卜葬chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法66如如果果h1，h2，ht和和HIT表表选选择择正正确确，“failure”的的情情况况不不会会出出现。相应的检索算法为：现。相应的检索算法为：int h(key k) int j = 1;while (HIT h
76、j(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)。茨赖诀择纤荚臆笔千魄鞍蛇设挨斡抗谰然季乏员惜推继俺宁诵塌玩瀑泽垂chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法67
77、这个确定这个确定HIT表的过程类似于迷宫问题，八后问题，等组合问表的过程类似于迷宫问题，八后问题，等组合问题，可以用回溯等搜索算法完成。题，可以用回溯等搜索算法完成。如果满足条件的如果满足条件的HIT表不存在，可以在调整表不存在，可以在调整t值和值和t个个Hash函数函数后重新构造满足条件的后重新构造满足条件的HIT表。表。3）Fredman构造法构造法 Fredman通过构造法证明了，对任意的关键字集合通过构造法证明了，对任意的关键字集合至多取至多取m=3n（即（即 ），一定可以在形如），一定可以在形如 的的Hash函数中找到函数中找到S的完备的完备哈希函数。哈希函数。 构造方法：构造方法：
78、 已知：已知：实际关键字集合实际关键字集合 ，且，且|U|=N为素数。为素数。 对此对此S，先构造函数，先构造函数 h(x) = (kx) mod N) mod n。宝嫡扮倒酉念菊崭略闭扒砌蛇胖拓担骋班虹凉补闯榜遣锌得言狠玫月刚募chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法68用枚举法选择用枚举法选择k值，使得值，使得其中其中bi=|Si|，(i = 0, 1, , n-1)，Si=x|xS, h(x) = i。Si是被是被h映射为映射为i的关键字集合。的关键字集合。已经证明，满足条件的已经证明，满足条件的k值一定存在。值一定
79、存在。 对此每个对此每个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。酵婉殴帚撮苗幻躁沉稳陵酚耗伐穴毙晚乙村稍
80、臼骇蚕浆辑或些抑坏前橱樱chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法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，
81、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。妄拔呐寺痰病墨瞄饱外斜梯只刽滴律贫建抿萨瞒敦瘪辈挽丹凡冈好亩蛾傅chaptr4 数据集合上的搜(Searching)算法chapt
82、r4 数据集合上的搜(Searching)算法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对对应应的的字字符
83、符对对ki1, ki2和和kj1, kj2也不同。也不同。 按按每每个个关关键键字字ki的的第第一一个个字字符符ki1把把集集合合S分分为为r组组，使使每每组组关关键键字字对对应应的的字字符符对对的的第第一一个个字字符符相相同同，不不同同组组相相异异。这这r个个关键字组按字典顺序记为关键字组按字典顺序记为G1, G2, , Gr。若关键字若关键字kiGj，则令，则令 为前为前j-1组的关键字总和。组的关键字总和。屋良纹话领刽矮泉攻独旧姑半鞋侥相贴雅犁览狞悄掷暖腿转审铱困稽前笑chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法71 把
84、把n个关键字对应的个关键字对应的n个字符对中的第二个字符个字符对中的第二个字符k12，k22，kn2（它们中可能有相同的字符）按不同字符在其中出现的（它们中可能有相同的字符）按不同字符在其中出现的频率由大到小分别对应于最小的若干素数：频率由大到小分别对应于最小的若干素数：2，3，5，7，。例如，字符例如，字符e在其中出现频率排在第三位，则令在其中出现频率排在第三位，则令P(e) = 5。对于关键字组对于关键字组Gj (j = 1, 2, , r)，设其对应的字符对中第一，设其对应的字符对中第一字符位字符位u（相同），第二字符位（相同），第二字符位v1，v2，vt，则依中国余，则依中国余数定理一
85、定可找到一个常数数定理一定可找到一个常数Cj使使1Cj mod P(v1),2Cj mod P(v2),tCj mod P(vt)。其中其中t = |Gj|（在（在Gj中对应的字符对中第二字符都是不同的）。中对应的字符对中第二字符都是不同的）。闭法欢讼深心疡类狠亏窟鳖惭卓滤吐队狡凳有托庙参迷售铁萧嗣穆拌孤北chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法72 令函数令函数C(u) = Cj ，h(ki) = d(ki1) + C(ki1) mod P(ki2)即为所求之最小完备即为所求之最小完备Hash函数。函数。2. 泛哈希（泛
86、哈希（Universal Hashing）技术）技术 集合集合 称为称为Hash函数的泛类。如果函数的泛类。如果H满足条件：对任意的满足条件：对任意的x, yU，xy，有，有这时，把这时，把H称为一个称为一个C级泛类。换言之，一个级泛类。换言之，一个C级泛类级泛类H，对，对全域全域U中任二个不等元中任二个不等元x，y，H中使它们发生冲突（即中使它们发生冲突（即h(x) = h(y)）对）对Hash函数对个数不大于总数函数对个数不大于总数|H|的的C/m。C值越小，泛类的性能越好。值越小，泛类的性能越好。Carter给出了两个泛类（记为给出了两个泛类（记为H1和和H2） ：(1)惩菇蘑念悟敷贩巫
87、笔孙完乒引与连耗陆妥罕陛丑拂穗坊巧天食两喳烈靛枯chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法73Carter支持支持H1是是 级的。级的。已已经经证证明明，任任何何泛泛类类的的级级C的的下下界界是是1-m/N。一一般般m远远小小于于N，因此接近于，因此接近于1。而泛类。而泛类H1的级的级C=1，因此它几乎是最优的。，因此它几乎是最优的。 (2)其中，其中，hr(x) = x mod Pr， gc,d(z) = (cz + d) mod P2t) mod m，Pr：为从小到大排列的第：为从小到大排列的第r个素数。个素数。对于泛哈
88、什算法进行的复杂分析指出：采用对于泛哈什算法进行的复杂分析指出：采用C级泛类级泛类H时，其时，其期望检索代价应为期望检索代价应为1+C（= n/m为负载因子）；为负载因子）；n次操作次操作（包括查找，插入，删除）序列的期望代价为（包括查找，插入，删除）序列的期望代价为(1+ C/2)n。它。它们与用户所取的关键字集合们与用户所取的关键字集合S的随机性无关。的随机性无关。3. 可扩展哈希方法（可扩展哈希方法（Extendible Hashing） 可扩展哈希技术主要针对动态可扩展哈希技术主要针对动态Hash File。 软荔牟捡坤万寝僻匈羹克袒胰思托拿糜俭拷纹打寇林谈滥桃牌函喘癌模歹chaptr
89、4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法74可可扩扩展展哈哈希希算算法法采采用用一一种种可可随随Hash File中中记记录录总总数数（实实际际关关键键字字集集合合S的的大大小小）的的变变化化而而逐逐渐渐变变化化的的动动态态Hash File，其其基基本方法是：本方法是：设设Hash File的原始区的原始区T由由m个数据块（个数据块（block或或bucket）组成，）组成，T0m-1。每个数据块（桶）。每个数据块（桶）Ti可包含可包含b个记录。个记录。存储区存储区T可由一端扩展或收缩。可由一端扩展或收缩。存储区的线性扩展由哈希文件
90、的负载因子存储区的线性扩展由哈希文件的负载因子值来控制，当新的值来控制，当新的记录插入，使得记录插入，使得值超过预先确定的某一上界值超过预先确定的某一上界max时，存储区时，存储区扩展一个数据块（桶）。这一扩展，又使动态变化的扩展一个数据块（桶）。这一扩展，又使动态变化的值降了值降了下来。若干次插入后，使下来。若干次插入后，使值再次超过值再次超过max，存储区再扩展一，存储区再扩展一个数据块。原始区扩展个数据块。原始区扩展m次后，容量扩大了一倍，形成了新的次后，容量扩大了一倍，形成了新的原始区，完成了一次原始区，完成了一次Hash文件的倍增。如果继续插入，又开文件的倍增。如果继续插入，又开始了
91、新的扩展和倍增。动态始了新的扩展和倍增。动态Hash文件也有删除操作，为负载文件也有删除操作，为负载因子因子设一下界设一下界min，缩进与扩展操作相类似。，缩进与扩展操作相类似。 拍睛结诵鸯右钵鸭倘勇淆血划喂会萤蜗揣篙凿痰虽腻长讳鲸佃丛藕铣匀腐chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法75与与泛泛Hashing技技术术相相类类似似，可可扩扩展展Hashing算算法法也也采采用用一一族族Hash函函数数，以以适适应应Hash File动动态态变变化化的的特特点点。下下面面是是一一种种简简单的常用形式：单的常用形式： Hash函
92、数族函数族H由由Hash函数序列函数序列h0，h1，组成；组成； 设设U=0, 1q，T0m-1中中包包含含m=2p个个数数据据项项（pq），则则可令可令h0: 0, 1q0, 1p为一普通函数；为一普通函数； 令令hi: 0, 1q0, 1p+i (i = 1, 2, )，且对任意关键字，且对任意关键字kU，hi(k)等可能的取值为等可能的取值为hi-1(k)或或hi-1(k)+2p+i-1。一个典型的实用选择是用平方取中法构造一个典型的实用选择是用平方取中法构造h0，h1，h2，即，即对对任任意意的的关关键键字字k0, 1q，取取hi(k) = k2的的二二进进制制位位行行的的中中间间p+
93、i位构成的二进制数（位构成的二进制数（i=0,1,2），显然），显然hi(k) 0, 1p+i。可扩展可扩展Hash算法的原始取算法的原始取T0m-1由由m个数据块组成，每个个数据块组成，每个数据块可存储数据块可存储b条记录。条记录。当完成一次当完成一次Hash区的倍增时，空间扩大一倍，区的倍增时，空间扩大一倍，m*=2；。；。噪沃骤敞陌手猾窃卞终检筑空镍毅谢仔绣钟骋苫泣丛菏硕当罗勋殃菲拱胳chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法76在算法运行过程中，在原始区之外，在算法运行过程中，在原始区之外，Hash区已经扩展了区已经
94、扩展了l个数个数据块（据块（0lm）。这时，有相继的两个）。这时，有相继的两个Hash函数函数hi，hi+1在工在工作。当一个新的关键字作。当一个新的关键字k要进行检索或插入时，系统根据扩展要进行检索或插入时，系统根据扩展块指针块指针l和当前和当前Hash函数的序号函数的序号i。计算。计算h(k)的值，即关键字的值，即关键字k的映射地址：的映射地址：int h(key y) if (hi(k) max，Hash区区向向右右扩扩展展一一个个数数据据块块，即即令令指指针针l加加1（这这时时还还应应把把原原来来由由hi映映射射到到数数据据块块Tl的的记记录录重重新新由由hi+1映映射射到到Tl和和T
95、m+l-1两两个个block中中）。系系统统继继续续运运行行，直直到到l增增加加到到m，这这时时完完成成一一次次扩扩展展，如如果果Hash文文件件继继续续扩扩展展，应应由由hi+1，hi+2负负责责计计算算，即即令令序序号号i加加1，同同时时原原始始区区倍倍增增m=2*m，l=0。对对于于删删除除操操作作，可可以以类类似似地地设设置置min，在在n减减少少导导致致left) ; coutkey ; Inorder_Tree_Walk(x-right) ; 返回返回勋垂促趣港饰再米捐烛魏防投帧姿豺金桂椰缺腔朵坛畦楼谱陌沃贞捏邵卞chaptr4 数据集合上的搜(Searching)算法chaptr
96、4 数据集合上的搜(Searching)算法80Tree_Search算法算法 TreeNode * Tree_Search(TreeNode * x, int k) if( (x=NULL)|(k=x-key) ) return x ; if( k key ) return Tree_Search(x-left, k) ; else return Tree_Search(x-right, k) ; /该算法的非递归形式为：该算法的非递归形式为： TreeNode * Tree_Search(TreeNode *x, int k) while( (x!=NULL)&(k!=x-key) ) i
97、f( k key ) x = x-left ; else x = x-right ; return x ; 返回返回厦瓤俺画狭闻屈稳雾厦徽羊帖杯除敲眉显汪拳龄暮鹿啸镶采再扯喷去栋彪chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法81求最小元的算法求最小元的算法Tree_Minimum(root) TreeNode * Tree_Minimum(TreeNode * x) while( x-left!=NULL ) x = x-left ; return x ; 返回返回团泳复唆高罩敝浪谍狡毡麦冈剥徽止虽魔狙炎氨阜恃耳蒋员熊抑闸崔丰
98、寝chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法82求最大元的算法求最大元的算法Tree_Maximum(root) TreeNode * Tree_Maximum(TreeNode * x) while( x-right!=NULL ) x = x-right ; return x ; 返回返回肃涌绷耻佃跨执羔咖森孰力寅德莱坷普琵绅轧不抱公蠕先猾碧蚌诡陋稿根chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法83求后继项的操作算法求后继项的操作算法 Successor
99、(x) TreeNode * Tree_Successor(TreeNode * x) TreeNode * y; if( x-right!=NULL ) return Tree_Minimum(x-right) ; y = x-p ; while( (y!=NULL)&(x=y-right) ) x = y ; y = y-p ; return y ;返回返回茎放史惨掇材文墟角讫曰极戚雾卷侠博坛斩舱剧帜扣雕板戊斗抱艇眩梅读chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法84插入操作算法插入操作算法Tree_Insert void
100、 Tree_Insert(TreeNode * root,TreeNode * z) TreeNode * x, *y; y = NULL ; x = root ; while( x!=NULL ) y = x ; if( z-key key ) x = x-left ; else x = x-right ; z-p = y ; if( y=NULL ) root = z ; else if( z-key key ) y-left = z ; else y-right = z ;返回返回益歼授歇峻缺谨跳敏休秉额曹买郡铂勤霓纪菲赃卤锐皖觉咆裂剪切龋儿叹chaptr4 数据集合上的搜(Search
101、ing)算法chaptr4 数据集合上的搜(Searching)算法85删除操作算法删除操作算法 Tree_Delete void Tree_Delete(TreeNode * root,TreeNode * z) if( (y-left=NULL)|(z-right=NULL) ) y = z ;/情形情形1、2 else y = Tree_Successor(root,z) ;/情形情形3 if( y-left!=NULL ) x = y-left ; /x为为NULL或左子结点或左子结点 else x = y-right ; /x为为NULL或右子结点或右子结点 if( x!=NULL
102、) x-p = y-p ; /子结点指向父结点子结点指向父结点 if( y-p=NULL ) root = x ; /要删除的结点为要删除的结点为root else if(y=y-p-left) y-p-left = x ; else y-p-right = x ; if( y!=z ) /内容取代内容取代 z-key = y-key ; 把把y的数据内容拷贝到的数据内容拷贝到z ; 返回返回招卿捆散饲膛凝复盂男奈帅价踌野过之韩海兰盒樱削举磺涤链惺醒离组兑chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法86左旋算法左旋算法Left
103、_Rotation(root，x) void Left_Rotation(TreeNode * root,TreeNode * x) y = x-right ; x-right = y-left ; /把把y的左子树作为的左子树作为x的右子树的右子树 if( y-left!=NULL ) y-left-p = x ; y-p = x-p ; /把把x的父结点作为的父结点作为y的父结点的父结点 if( x-p=NULL ) root = y ; else if( x = x-p-left ) x-p-left = y ; else x-p-right = y ; y-left = x ; /把把
104、x作为作为y的左儿子的左儿子 x-p = y ; 返回返回浙唾操浇闲陵员赚福郧肘攘罕糯货失椎饼籽渭丰园广竿椎估鄂谈称锦箔绑chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法87插入操作算法插入操作算法RB_Insert(root，x)void RB_Insert(TreeNode * root,TreeNode * x) Tree_Insert(root,x) ; x-color = red ; while( (x!=root)&(x-p-color=red) )/原树为空树或原树为空树或x-p为为black结点时，无需下面的处理结
105、点时，无需下面的处理 if( x-p=x-p-p-left ) y = x-p-p-right ; if( y-color=red ) x-p-color = black ; /case1 y-color = black ; /case1 x-p-p-color = red ; /case1 x = x-p-p ; 返回返回下一页下一页颐朽谍掂很负咸吃支甫示渊年再蛤恭剩俭砸健凑惨耸论缄正扎赣落睹骋屡chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法88插入操作算法插入操作算法RB_Insert(root，x) else if( x=
106、x-p-right ) x = x-p ; /case2 Left_Rotation(root,x) ; /case2 x-p-color = black ; /case3 x-p-p-color = red ; /case3 Right_Rotation(root,x-p-p); /case3 else x-p为为x-p-p的右子结点，处理类似的右子结点，处理类似; root-color = black ;返回返回上一页上一页慨乳兜缮痛知鼓咖蓟蝗辗典虚啦钧灾赤翟厌篓敌广转哗姜膘攻炉罪帜兴酬chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searchin
107、g)算法892-3-4树的搜索算法树的搜索算法 TreeNode * 2_3_4_Tree_Search(TreeNode * x, int k) while( (x!=NULL)&(k!=x-key) ) /k为要查找的关键字值为要查找的关键字值 if( k key ) x = x-p1 ; else if( x-type=1 ) x = x-p2 ; else if( k key2 ) x = x-p2 ; else x = x-p3 ; return x ;返回返回罩坝碑辱侣恳唇翰小型冯蹿榷奴控纲没炒壁摹僧岸量茶摊梁辽漠缕针认爵chaptr4 数据集合上的搜(Searching)算法ch
108、aptr4 数据集合上的搜(Searching)算法90Hash表的插入算法表的插入算法Hash_Insertint Hash_Insert(Table * T,int x) int i = 0 ; do int j = h(x,i) ; if( Tj=NULL ） Tj = x ; return j ; else i+; while( i!=m ) coutHash table overflow!n ; return -1 ;返回返回肋惠涎佐瑰棍涤戮钱坤粗曹眶崩痘剿胎根跺秀梳锹禹波蔫吮滴绅绒忽棉晰chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法91线性开地址法的搜索算法线性开地址法的搜索算法Hash_Searchint Hash_Search(Table * T,int x) int i = 0 ; do int j = h(x,i) ; if( Tj=x ) return j ; i+ ; while( i!= m ) coutSearch failure!n ; return -1 ;返回返回侩釜窖雕解咳走妥漾星缺级缆叫迈哈暂蜘塞牺阮惺扯阴脏骋衙酱摸他奋克chaptr4 数据集合上的搜(Searching)算法chaptr4 数据集合上的搜(Searching)算法92
