1、一种高效的二叉查找树红黑树1 红黑树的定义查找是计算机信息管理的最常见操作。普通的二叉查找树的查找效率与树的深度有关。当它的左右子树深度相差较大时，查找效率就与单链表差不多。为提高查找效率，必须设法使二叉查找树的左、右子树的深度保持平衡。红黑查找树就是一种平衡的二叉查找树。定义 一棵二叉查找树如果满足下列性质，则称为红黑树：（1） 每个结点或是红色的，或是黑色的（增加一位表示颜 色的存储位） ；（2） 每个空结点 NIL 是黑色的；（3） 如果一个结点是红色的，则它的儿子应是黑色的；（4） 从任何一给定结点到其子孙叶结点每条简单路径上都具有相同个数的黑结点。图 1 给出了一棵红黑树的例子，其中
2、黑结点用方框表示，红结点用椭圆表示。2、例：3、推论：若一棵二叉查找树是红黑树，则它的任一子树也必为红黑树。4、红黑树的生成可以从空树开始，通过逐步插入结点来生成一棵红黑树。向一棵红黑树 T 中插入一个新结点 x 的过程如下：先按普通二叉查找树那样，在 T 中插入结点 x，并将 x 着为红色。为保证红黑树的的性质要求得以继续保持，一般需随时进行调整。具体可分为以下几种情况：（1） 若 x 的父结点是黑色的，则插入过程结束。（2） 若 x 的父结点是红色的，而 x 的叔叔结点 y 是黑色的，则需按图 2 或图 3 方式进行调整，其中子树 ,每一棵都有一个黑根。（3） 若 x 的结点是红色的，而
3、x 的叔叔结点 y 也是红色的，则需按图 4 或图 5 方式进行调整。对插入结点 x 在其祖父结点的右子树中的情况，不难给出调整规则。将 x 的祖父结点作为新的 x，继续按情况（1） 、 （2） 、（3）处理。由于需要判定插入结点的父结点及叔叔结点的红与黑，为便于操作，红黑树的结点就具有如下结构：lchild parent data tag rchild其中 lchild、 parent、rchild 分别是指向左儿子、父结点和右儿子的指针，tag 是红黑标志位，data 是数据域2 红黑树的查找效率为方便起见，我们把红黑树的叶结点（NIL）称为外部结点，带有关键字的结点称为内部结点。定义 从
4、某个结点 x 出发（不包括结点 x 本身）到叶结点的路径上的黑结点个数，称为该结点 x 的黑深度，记为 bd（x） ，根结点的黑深度就是该红黑树的黑深度。定理 1 以结点 x 为根的子树，至少有 2bd(x)-1 个内部结点。证：对以 x 结点为根的子树深度用归纳法。为方便起见，将以 x 为根的子树深度记为 d（x） 。若 d（x）=0 ，则 x 就是叶结点 NIL，这时该子树的内部结点数为 0，bd(x)=0，故结论为真。设 d（x）k-1 时结论为真，考察 d（x）=k 的情形。由红黑树定义中的性质要求 3 和 4 可知，当 x 为红色时，x 的子树的黑深度为 bd（x）-1；当 x 为黑
5、色时，x 的子树的黑深度或为bd（x） ，或为 bd（x）1，而 x 的子树的深度小于等于 k-1，由归纳假设可知，以 x 为根的子树至少包含有 2bd(x)1-1+2bd(x)1-1+1 个内部结点。故结论成立。定理 2 含有 n 个内部结点的红黑树的深度至多为2lg（n+1） 。证：设红黑树的深度为 d，根据红黑树定义中的性质要求3，从根到叶结点的路径上至少有一半的黑结点，从而该树的黑深度至少为 d/2，由定理 1 有 2d/21n故 d /2lg（n+1） ， d 2lg（n+1）由于查找操作的时间复杂性与红黑树的深度成正比，故对红黑树的查找，在最坏情况下的时间复杂性为 O（lgn） 。
6、若考虑红黑树的动态查找特性，即在查找失败时插入该结点，这时最坏情况是发生树的形状连续调整，但调整次数不会超过树的深度，故时间复杂性仍保持为 O（lgn） 。综上所述，不难发现，红黑树是一种高效的查找树，值得推广应用。i : =i+1;if A.datai=x thenA. datai =A.dataA.last;A.last : =A.last1】end; DELETEMEMBER,INSERT,DELETE 运算有最坏情况下的复杂性为 O(n)二、字典的散列实现1图示开散列(hashing)的思想,使每一个运算所需要的时间最坏情况下也为常数2散列函数3例function h(x :eleme
7、nttype):0.B-1;vari,sun:integer;beginsum : =0for i : =1 to 10 dosum : =sum +ord (xi);h : =sum mod Bend;h 其中集合元素 x 是长度为 10 的字符串。该散列函数利用 Pascal 提供的函数 ord(ord字符所对应的整数码)，将字符串 x 中的每个字符转换为一个整数，然后将每个字符对应的整数相加，用所得和除以B 的余数作为 h(x)值。显然这个余数是 0，1,B-1 之一。4.用开散列来实现字典时，其数据类型可说明如下：constB=100 桶的个数typecelltype=recordel
8、ement:elementtyoe;next;celltypeendDICTIONARY=array0.B-1 of celltype;5.在字典的开散列表示下，它的各个运算可实现如下。（1） 字典初化 MAKENULLprocedure MAKENULL(var A:DICTIONARY);vari :integer;beginfor i : =0 to B-1doA i : =nilend;MAKENULL（2） 字典查询 MEMBERfunction MEMBER(x:elementtype; A:DICTIONARY):boolean;varcurrent :cellentype;be
9、gincurrent : =Ah(x);while currentnil then【if Abucket.element=x thenAbucket:=Abucket.nextelse current : =Abucket;while current.nextnil doif current.next.element=x thencurrent.next : =current.next .next;returnelse current : =current.next】end;DELETE若要删除的元素正好位于不带表头单元的表的第一个位置，则对第一个位置进行特殊处理。三、闭散列1 闭散列是将字典
10、中的元素直接放在桶头数组中，而不是用桶头数组来存放桶链接表的表头，因此闭散列表中的每一桶都只能存放集合中的一个元素。2 采用闭散列来存放元素时，可能会发生冲突。因为桶可能已被具有相同散列值的其它元素所占据。3 如果发生了冲突，则可以采用重新散列技术，即使用散列函数序列 逐步顺序地试探，直到发 ,)(,21xh现一个空桶为止。4 例 ，并举书上习题1,mod)() Biixhi P173 第 7 题5 基本运算 INSERT 如上，MEMBER 及 DELETE 如何来实现呢？6 实现 MEMBER 时，按的顺序逐步检查每一个12,mod)() Biixhi 桶，看是否有一个桶中有 ，如果有，则返回真。否x则，若遇到一个桶，我们是否能确定闭散列
