一种高效的二叉查找树红黑树

《一种高效的二叉查找树红黑树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一种高效的二叉查找树——红黑树1．红黑树的定义查找是计算机信息管理的最常见操作。普通的二叉查找树的查找效率与树的深度有关。当它的左右子树深度相差较大时，查找效率就与单链表差不多。为提高查找效率，必须设法使二叉查找树的左、右子树的深度保持平衡。红黑查找树就是一种平衡的二叉查找树。定义一棵二叉查找树如果满足下列性质，则称为红黑树：（1）每个结点或是红色的，或是黑色的（增加一位表示颜色的存储位）；（2）每个空结点NIL是黑色的；（3）如果一个结点是红色的，则它的儿子应是黑色的；（4）从任何一给定结点到

2、其子孙叶结点每条简单路径上都具有相同个数的黑结点。图1给出了一棵红黑树的例子，其中黑结点用方框表示，红结点用椭圆表示。2、例：3、推论：若一棵二叉查找树是红黑树，则它的任一子树也必为红黑树。4、红黑树的生成可以从空树开始，通过逐步插入结点来生成一棵红黑树。向一棵红黑树T中插入一个新结点x的过程如下：先按普通二叉查找树那样，在T中插入结点x，并将x着为红色。为保证红黑树的的性质要求得以继续保持，一般需随时进行调整。具体可分为以下几种情况：（1）若x的父结点是黑色的，则插入过程结束。（2）若x的父结

3、点是红色的，而x的叔叔结点y是黑色的，则需按图2或图3方式进行调整，其中子树α,β,γ,δ每一棵都有一个黑根。（3）若x的结点是红色的，而x的叔叔结点y也是红色的，则需按图4或图5方式进行调整。对插入结点x在其祖父结点的右子树中的情况，不难给出调整规则。将x的祖父结点作为新的x，继续按情况（1）、（2）、（3）处理。由于需要判定插入结点的父结点及叔叔结点的红与黑，为便于操作，红黑树的结点就具有如下结构：lchildparentdatatagrchild其中lchild、parent、rchild

4、分别是指向左儿子、父结点和右儿子的指针，tag是红黑标志位，data是数据域2红黑树的查找效率为方便起见，我们把红黑树的叶结点（NIL）称为外部结点，带有关键字的结点称为内部结点。定义从某个结点x出发（不包括结点x本身）到叶结点的路径上的黑结点个数，称为该结点x的黑深度，记为bd（x），根结点的黑深度就是该红黑树的黑深度。定理1以结点x为根的子树，至少有2bd(x)-1个内部结点。证：对以x结点为根的子树深度用归纳法。为方便起见，将以x为根的子树深度记为d（x）。若d（x）=0，则x就是叶结点N

5、IL，这时该子树的内部结点数为0，bd(x)=0，故结论为真。设d（x）≤k-1时结论为真，考察d（x）=k的情形。由红黑树定义中的性质要求3和4可知，当x为红色时，x的子树的黑深度为bd（x）-1；当x为黑色时，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，根据红黑

6、树定义中的性质要求3，从根到叶结点的路径上至少有一半的黑结点，从而该树的黑深度至少为d/2，由定理1有2d/2–1≤n故d/2≤lg（n+1），d≤2lg（n+1）由于查找操作的时间复杂性与红黑树的深度成正比，故对红黑树的查找，在最坏情况下的时间复杂性为O（lgn）。若考虑红黑树的动态查找特性，即在查找失败时插入该结点，这时最坏情况是发生树的形状连续调整，但调整次数不会超过树的深度，故时间复杂性仍保持为O（lgn）。综上所述，不难发现，红黑树是一种高效的查找树，值得推广应用。i:=i+1;ifA

7、.data[i]=xthen〖A.data[i]=A.data[A.last];A.last:=A.last―1〗】end;{DELETE}MEMBER,INSERT,DELETE运算有最坏情况下的复杂性为O(n)二、字典的散列实现1．图示开散列(hashing)的思想,使每一个运算所需要的时间最坏情况下也为常数2．散列函数3．例functionh(x:elementtype):0..B-1;vari,sun:integer;beginsum:=0fori:=1to10dosum:=sum+or

8、d(x[i]);h:=summodBend;{h}其中集合元素x是长度为10的字符串。该散列函数利用Pascal提供的函数ord(ord©字符所对应的整数码)，将字符串x中的每个字符转换为一个整数，然后将每个字符对应的整数相加，用所得和除以B的余数作为h(x)值。显然这个余数是0，1,…,B-1之一。4.用开散列来实现字典时，其数据类型可说明如下：constB=100{桶的个数}typecelltype=recordelement:elementtyoe;next;celltypeendDICT