存档

作者存档

Virtual Memory

2014年1月17日 评论已被关闭

虚拟内存一种抽象的形式,它使得每一个进程都以为自己独占整个主存。每一个进程的内存分布都有统一的视图,被称为它的虚拟地址空间。
Linux的虚拟地址空间如图1.13所示。(其它的Unix系统也使用类似的布局。)
在Linux中,操作系统把虚拟地址空间最顶端的区域(译者注:内核空间)保留用于所有进程的公共代码和数据。地址空间的低端区域(译者注:用户空间)被用户进程用来存储代码和数据。注意表格中的地址空间增长方向是从下到上的。
(译者注:在Linux系统中(32位),0x00000000~0xbfffffff为用户空间,0xc0000000~0xffffffff为内核空间。)
Process virtual address space.

每一个进程看到的虚拟地址空间是由一些被划分好的用于特定目的的区域组成。在本书的随后部分你会获取到更多关于这些区域的细节,但是简略地从低端开始向上看一下每个区域也是很有帮助的。

  • Program code and data.所有的进程的代码都从相同固定的地址开始,接下来是数据区域,相当于C语言中的全局变量。代码和数据是直接用可执行文件的内容进行初始化,在我们例子里是hello文件。在第7章我们学习链接和加载时会学习更多的关于地址空间的这部分内容。
  • Heap.在代码和数据区域之后紧跟着运行时的堆。代码和数据区域在程序开始运行一次性分配固定大小的区域,与它不同的是,堆的扩张和缩小是动态的,它是调用C标准库如malloc和free之后的运行结果。我们在第9章学习虚拟内存管理时将学习更多的关于堆的细节。
  • Shared libraries.大概在地址空间的中间部分的区域用于装载了共享库如C标准库和数学库的代码和数据。共享库的概念非常强大但比较难以理解。你将会在第7章学习动态链接时了解它们是如何工作的。
  • Stack.在用户虚拟内存地址空间的最顶端是用户栈,编译器利用它来实现函数调用。跟堆一样,在程序运行用户栈的扩张和缩小也是动态的。特别是我每们调用一次函数时,栈就是增长。每次函数返回时,栈就是缩小。你会在第3章学习到编译器如何使用栈。
  • Kernel virtual memory.内核是操作系统的一部分,它总是长驻于内存。地址空间的最顶端区保留给内核使用。应用程序不允许读写这部分区域和直接调用内核代码段里定义的函数。

正常运作虚拟内存需要硬件和操作系统软件一系列的复杂交互,包括对处理器使用的每一个地址进行硬件转换。基本的思想是将进程的虚拟内存的内容存储在磁盘上,把主存当作磁盘的缓存使用。第9章将会介绍它的工作原理并解释为什么它对于现代操作是如此的重要。

分类: Linux, 翻译 标签:

使用librtmp进行H264与AAC直播

2014年1月3日 评论已被关闭

libx264版本是128
libfaac版本是1.28

1、帧的划分

1.1 H.264帧

对于H.264而言每帧的界定符为00 00 00 01或者00 00 01。

比如下面的h264文件片断这就包函三帧数据

00 00 00 01 67 42 C0 28 DA 01 E0 08 9F 96 10 00
00 03 00 10 00 00 03 01 48 F1 83 2A 00 00 00 01
68 CE 3C 80 00 00 01 06 05 FF FF 5D DC 45 E9 BD
E6 D9 48 B7 96 2C D8 20 D9 23 EE EF …

第一帧是00 00 00 01 67 42 C0 28 DA 01 E0 08 9F 96 10 00 00 03 00 10 00 00 03 01 48 F1 83 2A
第二帧是00 00 00 01 68 CE 3C 80
第三帧是00 00 01 06 05 FF FF 5D DC 45 E9 BD E6 D9 48 B7 96 2C D8 20 D9 23 EE EF ..

帧类型有:
NAL_SLICE = 1
NAL_SLICE_DPA = 2
NAL_SLICE_DPB = 3
NAL_SLICE_DPC = 4
NAL_SLICE_IDR = 5
NAL_SEI = 6
NAL_SPS = 7
NAL_PPS = 8
NAL_AUD = 9
NAL_FILLER = 12,

我们发送RTMP数据时只需要知道四种帧类型,其它类型我都把它规类成非关键帧。
分别是
NAL_SPS(7), sps帧
NAL_PPS(8), pps帧
NAL_SLICE_IDR(5), 关键帧
NAL_SLICE(1) 非关键帧

帧类型的方式判断为界面符后首字节的低四位。
第一帧的帧类型为: 0x67 & 0x1F = 7,这是一个SPS帧
第二帧的帧类型为: 0x68 & 0x1F = 8,这是一个PPS帧
第三帧的帧类型为: 0x06 & 0x1F = 6,这是一个SEI帧

以上是我们利用帧界定符划分帧,并可以判断每一个帧的类型。

注意:如果是压缩图像成H264帧,我们就可不必进行帧界定,因为每一次压缩的输出都明确了该帧的大小(包括界定符),每一次的压缩的结果可能包函多帧。一会具体讨论。

1.2 AAC帧

对于AAC帧它的界定符是FF F1

这里我就不举例了,可通过查看AAC的二进制文件可以看到如下的帧结构。
FF F1 50 80 24 9F FD DE 04 00 00 6C 69 62 66 61 61 63 20 31 2E 32 38 00 00 42 15 95 ..

注意:那么对于AAC而言加上界定符每一帧的前7字节是帧的描述信息,也就是说AAC的祼数据是除去前面的7个字节的,在发送RTMP时,我们要去掉这7个字节。同样,如果我们是一边压缩一边发送RTMP,我们同样不需要界定帧,因为libfaac每次压缩完成的输出就是一个完整的帧数据,我们只需要将该帧打包发送即可。

综合上面的所述,如果我们只是一边压缩一边将压缩结果发送到RTMP服务器,那我们就可以不用对帧进行界定,如果我们是发送H264与AAC文件,那我们就要对帧进行界定。

2.视频与音频的编码信息

如果我们只是简答的将压缩数据打包发送给RTMP服务器,那么RTMP服务器是不可以对数据进行解码和播放的,在这之前我们要将音视频的视频的编码信息发送给RTMP服务器。很多人可能苦于寻找下面的三个编码参数而不得要领。其实要想得到也是很简单的。 阅读全文…

分类: C/C++, Win32 标签:

GBK与UTF-8之间的转化

2013年11月11日 没有评论

GBK编码与UTF-8之间的转化。
第一种是先将 GBK->Unicode->UTF-8;
第二种是通过iconv库,直接GBK->UTF-8;
Unicode编码包含所有字符集,而GBK(GB2312是GBK的一个子集),UTF-8等等都称为多字节集(Multibyte),两个多字节字符集之间的转换首先将源字符集映射到Unicode上,再将Unicode映射到目标多字节字符集上。有一个问题就是源字符集与目标字符集不可能是一一对应的,所以在转换的时候往往会有一个参数表示如果未找到对应的字符的处理情况。另外Unicode中的表示字符用wchar_t,而多字节的字符用char表示(也有多个char表示一个字符)。

windows下

C语言中有与WideCharToMultByte对应的接口是wctomb,MultiByteToWideChar对应的接口是mbtowc,但是对应的转化不能将正确的转换UTF-8。具体实现是先将当前语言为源字节集,将源字节集转化成Unicode,然后将语言设置成目标字节集将Unicode转化成目标字节集,具体参见:
setlocale: http://msdn.microsoft.com/en-us/library/aa272906(v=vs.60).aspx

利用第三方库实现,它就是大名鼎鼎的libiconv,有一个值得小心的地方,就是当目标字符集中没有源串中对的字符是可以选择继续还是忽略,所以及在open时会带上参数”//IGNORE”,要不然就遇到这种情况会停止转化。

分类: C/C++, Linux, Win32 标签:

【翻译】创建并重定向子进程的标准输入输出

2013年10月14日 没有评论

原文地址:http://msdn.microsoft.com/en-us/library/windows/desktop/ms682499(v=vs.85).aspx
本节的实例描述了控制台进程如果通过CreateProcess函数创建子进程。同时展示了使用匿名管道重定向子进程的标准输入和标准输出句柄。当然,有名的管道也可以用来重定义进程的I/O。

CreatePipe函数使用SECURITY_ATTRIBUTES来创建可继承的读写端的管道。管道的读端作为子进程的标准输入,管道的写端作为子进程的标准输出。将这两个管道句柄设置到STARTUPINOF的结构体的标准句柄中(标准输入,标准输出,标准错误输出),这样子进程就可以继承这几个管道的句柄。

父进程使用管道的另外两端向子进程的标准输入中写入数据或者从子进程的标准输出读出数据。在STARTUPINFO结构体中,这些句柄(即父进程使用的另外两个句柄)也是可以承继的。然而这些句柄是不能被子进程继承(子进程中继承从标准输入中读取数据和向标准输出中写入数据)。因此,在创建子进程前,父进程调用SetHandleInfomation函数来保证向子进程标准输入中写入数据和从子进程标准输出中读出数据是不可以被继承的。更多信息,参阅Pipes。

下面的代码是的父进程的代码。它使用一个简单命令行参数:文本文件的名字。

下面是子进程的代码。它使用STDIN和STDOUT的继承句柄去访问父进程创建的管道。父进程从它的输入文件中读出并将读出的数据写到管道中。子进程通过过STDIN的管道读取数据和通过STDOUT的管道写入数据。父进程能过管道的读端读出数据并能过标准输出STDOUT显示出来。

本文还可以解决一个问题就是利用c库的system,_popen创建的进进程出现黑窗口的问题。另外原文件的父进程在创建子进程后增加了两行代码:

有点类似于pipe后,父进程关闭fd[1]子进程关闭fd[0]类似,这是子进程没有继承向子进程标准输入中写数据和向子进程标准输出读数据,因为父进程设置这两个句柄不可以继承。同时父进程也应该关闭自己的向子进程标准输入中读数据和向子进程中标准输出中写数据的句柄。

分类: 翻译 标签:

使用原子操作实现自旋锁

2013年10月14日 没有评论

原子操作
在windows平台有InterlockedCompareExchange原子操作接口。实现对内存的互斥修改

如果对函数的解释有点疑惑,可以看一下该函数的大致实现。

自旋锁
如果我们所1代表“加锁”,0代表“未加锁”。加锁的过程是将内存值0改成1,所以我们可以利用这特性实现加锁操作和解锁操作。

知道trylock只是尝试去将0改成1,如果之前已经是1说明,锁被占用了。所以我们实现了自旋等待锁被释放。

更好的实现,用Sleep切换CPU。

对于基于linux的gcc也是有相应的“比较修改”接口__sync_bool_compare_and_swap(lock, old, set),它的参数与windows的接口有两点不一样,参数不一致,返回类型也不一样。它的trylock的实现:

example

分类: C/C++, Linux, Win32 标签:

Inheritance Mode in C++

2013年7月31日 没有评论

Inheritance Mode in C++

There are 3 kinds of inheritance mode: public private protected

we can change to each other between protected and public,but we can’t change private in base class to public or protected

 

分类: C/C++ 标签:

红黑树详解

2013年7月8日 没有评论

在本文,我将比较透彻地讲解红黑树。本文适合那些有对二叉树有一定的基础,并且熟悉C语言的读者。本文最主要的参考资料是《Introduction to Algorithms 3rd Edition》。

1.1 二叉查找树

1.1.1 基本概念

二叉查找树是在数据结构中比较重要的数据结构之一,从外部看它满足集合性质,具有查找,插入和删除的基本功能,同时还可以求最大值和最小值。由于二叉查找树独特的性质,它特别适合用来存储动态集合。
定义:对于二叉树上的所有结点x,如果y是x的左子树,那么y.key ≤ x.key。如果y是x的右子树,那么y.key ≥ x.key,这样的二叉树就称为二叉查找树(Binary Search Tree)。
我们关心的二叉查找树的逻辑结构,下面的两棵二叉树:

图1 二叉查找树。(a)这一棵高度为3的二叉树,因为10比15小,所以10在15的左子树上;同理在以10为根的左子树里,7比10小所以7在左子树上,12在10为根的子树的右子树上;20在以15为根的右子树上。(b)这是一棵高度是4的二叉查找树,它的所有key与图(a)是一样的。在图(a)中,查找最坏的情况是7和12,它们需要经过3次比较才能找到,而图(b)最坏情况是20,需要经过4次比较才能找到。
要想二叉树的查找的花费时间小,我们尽可能让二叉树不出现类以于单链形态的二叉树,让树的高度尽量的低。对于高度为h的二叉查找树,从树根对叶子最坏的情况是比较h次。也就是说,对于高度为h的二叉查找树的最坏查找情况的运行时间是O(h)。二叉树的查找效率取决于树的高度。

1.1.2 操作

二叉树做为动态集,它有查找、插入、删除、最大值、最小值、前驱和后继这些基本操作。为了后序的方便,我们定义了结点和树,另外我们还用NIL表示空子树。

查找
在二叉查找树中根据给定的key找到该结点。由于二叉树的性质,我们就知道,如果目标key比当前结点的key要小,那么目标结点必定在当前结点的左子树上。

最小值与最大值
我们来分析一下最小值的位置。我们认为最小值的位置是从根出发一直沿结点的左子树直到某个结点x的左子树为空,那么这个结点x就是整个二叉树中key最小的结点。注意,我们并没有做任何key的比较。
证明:假设这个结点x不是最小值,另外有最小值结点y,那么y.k > x.k。如果y是x的祖先,因为x位于y的左子树上,那么x肯于定比y要小,所以y不是x的祖先。如果y不是x的祖先,假设y与x的最小的共同祖先的z,又因为y不是x的祖先,所以y在z的右子树上,所以z.k < y.k,并且有z.k > x.k,与假设的y.k > x.k矛盾,所以假设不成立,x是二叉查找树中key最小结点。最大值的分析方法也是一样的。

前驱和后继
前驱与后继定义来源于二叉树中序遍历的key序列。我们知道二叉的中序遍历的key序列是一个升序序列。在二叉查找树中,对于结点x,如果有结点y,满足y.key>x.key并且y是这些结点中key最小的,那么y就称之为x的后继。同理,在二叉查找树中,对于结点x,如果有结点y,满足y.key

图2结点的后继和前驱。(a)y是x的后继,因为y没有左子树,所以y是x右子树上key最小的结点。(b)y是x的后继,因为x的左子不为空,所以y是x左子树中最左那个小那个,所以y是x的后继。(c)x是y的前驱,因为y没有左子树,所以y是x左子树上key最大的那个结点。(d)y是x的前驱,因为x有左子树,所以x左子树上key最大的在x左子树上最右的那个结点。也有可能是z右孩子的最左的那个子孙结点(图b所示)。如果y是的后继,那么y就是x的前驱。
对于某个结点y它的后继的位置是:如果y的右子树存在,那么后继是y的右子树中的key最小的结点;如果y的右子树不存在,那么我们只要找到哪个结点的前驱是y,那么那个结点就是y的后继(图2中的d)。

根据前驱和后继的定义,我们知道通过对树中最小值一直沿着后继直到结束,这样的序列就是中序遍历的序列。下面给出中序遍历的代码:

插入
对二叉查找树的插入,不能破坏二叉查找树的性质,那么我们要结点插入到什么地方呢?答案是叶子,新插入的结点,都是将成为某个叶子结点的左孩子或者右孩子。

图3 二叉查找树的插入。图中key为11的结点插入到树中,其中浅色结点表示插入时候比较的路径。虚线表示插入的位置。

我们发现insert与search方法是一样的,只不过search是查找特定的key,而insert是查找合适的叶子结点的位置,它的运行时间为O(n)。

删除
在介绍删除二叉查找算法之前,我们先来介绍一个辅助函数transplant,这个函数有3个参数,在树T中,将v替换u的位置,即u的双亲变成v的双亲,v替换u成为u双亲的孩子。另外一个辅助函数replace,这个函数有3个参数,在树T中,将v完全代替u,即u的双亲变成v的双亲,v替换u成为u双亲的孩子,另外左右孩子均为u的孩子。

图4演示了transplant中v在树中替换u的过程。如果u是根,即v.p==0时,T的树根就改变了。

我们来考查一下待删除的结点是z。那么z可能有几种情况:

  • z没有右孩子;
  • z有右孩子:z的右孩子有左孩子,z的右孩子没有左孩子。


图5 二叉树删除的三种情形。图中z(浅色的)为待删除的结点。(a)没有右孩子的删除,将z的左孩子替换z即可,z的左孩子有可能是NIL指针。(b)z的右孩子不为空,y是z的后继,但右孩子的左孩子为空,我们知道z的右孩子就是z的继,所以用z的右孩子替换z即可。(c)z的后继y不是z的右孩子,y的右孩子替换y,从树中移出y,将y作为z右孩子的双亲连接上,此时情形成了情形b了。
下面我具体针对这3种情形进行分解。情形1,z没有右孩子,我们只要将左孩子替换z在树中位置就能完成删除操作,其实我们拿z的前驱替换也是可以的;情形2,z有右孩子,所以我们找到z的后继替换z。因为z的key小于右子树所有的key(假设没有重复的key),那么z的后继就是右子树上的最小key。如图5的中b和c,z的后继可能是z的右孩子(当右孩子没有左孩子就会出现该情况),那么调用transplant(T,z,y)。另外,要连接上原来z的左子树;z的后继也有可能不是z的右孩子(图c所示的情况),首先我们调用transplant(T,y,y->r),这时候y已经从树中脱离了,然后我们将y嫁接到z的右孩子的双亲上,这样y就成了z右孩子的双亲了,这和情形b是同一种情况了。下面是删除的代码:

1.1.3 实现

参考附件:bstree.c。

1.1.4 思考题

1.Bunyan教授认为他发现了二叉查找树的一个重要的性质。假设在二叉查找树上查找key为k的结点,并且key为k的结点是一个叶子结点。那么有三个集合:A,搜索路径的左边结点的集合;B,搜索路径上的结点的集合;C是搜索路径右边的结点集合。Buyan教授认为对于三个集合的任意值a∈A,b∈B,c∈C一定满足a≤b≤c。对于上面的观点,请给出最小可能一个的反例。
2.证明:在高度为h的二叉查找树上,我们实现的动态集基本操作:min,max,successor,predecessor,search,insert和remove的运行时间都是O(h)。
3.在二叉查找树的删除操作中,假设我们不取z的后继而取z的前驱替换z,请相应对称的代码。

1.2 红黑树

在上节的思考题中,我们证明了在高度为h的二叉查找树上,我们实现的动态集基本操作运行时间都是O(h)。总而言之,树度h决定查找效率。如果我们通过某种方法能够将二叉树尽可能的低,那么二叉树的查找效率将会大大地提高。
对于一个含有n结点的最坏的情况是这n个结点形成一条单链,那么二叉查找树的树高为n,运行时间为O(n);那么最好情况是n个结点形了一棵完全二叉树。所谓完全二叉树是指对于一棵高度为h的二叉树,除第h层外,其它各层的结点数都达到最大个数,并且第h层所有的结点都连续集中在最左边,这样的二叉树称为完全二叉树。那么h介于lg n与lg n+1之间,也就是说运行时间为O(lg n)。可以说它的效率是极高的。

1.2.1 基本概念

如果我把二叉查找树的每个结点都涂上红色或者黑色。如果它满足下面的5个性质,那么我们就称它为红黑树(Red Black Tree):

  • 每个结点不是红色就是黑色。
  • 根结点是黑色的。
  • 每个叶子结点(NIL)都是黑色的。
  • 如果一个结点是红色的,那么它所有的孩子都是黑色的。
  • 对于每一个结点,从当前结点到后代的叶子的路径上包含黑色结点的数量是相同的。

根据红黑树的性质,我们可得出下面的结论:具有n内部结点的红黑树的高度最高为2lg(n+1)。
在证明这个结论之前,我们来看看红黑树的表示。每个结点到叶子结点(NIL)经过的黑色结点的个数(包括自已)称之为黑高度(black-height)。我们把NIL称之为外部结点,那些带有key的“合法”的结点称之为内部结点。

图6 红黑树的表示。key为64的结点的黑高度为3,key为26,81,14,44的结点黑高度为2,key为5,19,30,76,92的结点黑高度为1。
证明:我们将红色结点吸附到黑色的双亲结点上,那么一个黑色结点最多可以吸附2个结点,并且可以有4个孩子,那么就形成了一个大结点,如图7所示。这样树我称之为234树。红黑树的数学本质就是234树,并且所有的“叶子”结点的高度都是相等的。不难看出,黑高度就是这棵234树的高度。

图7 将图6中的红色结点吸附到双亲结点上,这样对应数学结构为234树。
对于高度为h并且所有的“叶子”结点的高度都是相等的234树最少有多少个结点呢?要想结点最少,那么它就退化出了满二叉树了。所以,树的结点个数n满足:
(公式1)
由公式1得出:两边取对数即。这里的h是234树的高度,由前面所述,红黑数的黑高度就是对应234树的高度。对于黑高度了h,由性质2、3、4得出红色结点不可能多于黑色结点。所以结点个数不大于黑高度的2倍。所以具有n内部结点的红黑树的高度最高为2lg(n+1),证毕。
我们证明的结论说明红黑树的搜索运行时间为O(2lg(n+1))也就是O(lg n)。
为了方便操作,我们引入一个NIL结点,这个NIL结点是跟普通的结点一样,不过我们只使用color这个域,因为NIL结点是黑色的。

我们定义了结点的颜色,同时每个结点都增加了一个c域来表示结点的颜色。除此之外我们还为树定义了一个nil结点,之前实现的二叉查找树中指向NIL都改为指向T->nil。

1.2.2 查找

因为红黑树本身就是一棵二叉查找树,所以对红黑树的查找操作跟普通的二叉查找树的操作没有什么不一样,但注意的时,在这里我们已经用T.nil取代了0。下面仅仅给出查找操作的代码,读者可以比较一下与普通的二叉查找树有什么不一样的地方。

有两处不一样,第一处是x!=0替换成了x!=&T->nil,另外一处是在结尾出增加了对x是否是nil的判断,操作上的代码没有二致。对于前驱和后继,我就不举例了,有兴趣的读者可以自行思考或者参考一下附件的实现。

1.2.3 旋转

在介绍红黑色的插入与删除前,我们介绍一下二叉树的旋转操作:旋转分为左旋(Left-Rotate)和右旋(Right-Rotate)。
左旋

图8 树的左旋和右旋。(a)将x结点右孩子y替换x成树中的位置,同时x成为y的左孩子,y原来的左孩子成为x的右孩子。观察在调整前α  下面是左旋代码,先用y替换x的位置,再将y的原左子树变成x的右子树,x成y的左子树。

右旋
下面给出右旋的代码,先用y替换x的位置,再将y的原右子树变成x的左子树,x成y的右子树。

小技巧:区分左旋还是右旋,我们只要看x最终是y的左孩子还是右孩子,如果左孩子那就是左旋,如果右孩子那就是右旋。
综述,二叉查找树的左旋和右旋并不会破坏其二叉查找树的数学性质。

1.2.4 插入

红黑树的插入前半部分与普通的二叉查找树的插入大致相同的,我们来看一下插入的代码。

从代码中可以看出,它与我们前面的二叉查找树的插入操作有两个地方不同,首先是用T.nil取代了0,其次是在代码的结尾,多出了两行,一行是z->c=RBT_RED,另一行是调用了_rbt_insert_fixup函数。
我们知道,将结点插入到红色黑树的叶子结点上,可能会导致这棵树不再满足红黑树的性质。我们将新插入的结点着成红色,插入到红黑中,然后通过_rbt_insert_fixup修正红黑树的性质。
当插入结点z时,我如果把z着成红色,看看我们会破坏原有的那些性质呢?
我们已经将z着成红色了,所以性质1不会被破坏。当往空的红黑树插入结点的时候,这个性质2会被破坏。每个叶子结点(NIL)都是黑色的,所以性质3不会被破坏。因为我们插入的结点是红色的,所以性质4可能被破坏,同样是因为我们插入的是红色结点,所以性质5不会被破坏。综述,我们往将z着成红色插入到红黑树的时候,可能会破坏性质2和性质4,其它性质不会被破坏。

图9 红黑树的插入情形。(a)z的叔叔是红色的,z是左孩子;(b)z的叔叔是红色的,z是右孩子;(c)z的叔叔是黑色的,z是左孩子;(d)z的叔叔是黑色的,z是右孩子。这里我们略了z的叔叔是左孩子的情况,因为它们是对称的。
当结点z插入时,如果z的双亲结点不是红色的,那么它不会破坏红黑树的性质。所以只有z的双亲是红色的时候,z和z的双亲都是红色会破坏红黑树的性质4,所以我们目的是在不破坏现有的性质1,3,5来恢复性质2和4。
我们考查z和z的叔叔,当z的双亲是左孩子,性质4被破坏的情况只有图9所示的4种情况;当z的双亲是右孩子的时候,跟这个是对称的。我们知道,是因为性质4被破坏了,所以z和z的双亲都红色的,所以z双亲肯定不是根结点,因为根结点是黑色的。下面针对这四种情况进行恢复红黑色树的性质。
情形1:z的叔叔是红色的。
这种情况,不管z是右孩子还是左孩子,我们将z的双亲的双亲上的黑色的分别涂给z的双亲和z的叔叔,这样不会可能破坏性质2或者性质4,其它性质依然保持,因为z的双亲是红色且z的叔叔也是红色的(假设的条件)。我们不知道z的祖亲的双亲颜色,所以我把z的祖亲当作新的结点z,继续调整。

图10 我们将z.p和叔叔都着成黑色,z.p.p当作新的z继续修复。直到z.p的颜色是黑色的,那么z.p.p是根时,由于z.p是T.nil,它也是黑色的,也会退出循环,不会将叶子着成红色的。我们在最后恢复性质2,暂且不考虑性质2被破坏。
情形2:z的叔叔是黑色的,z是双亲的左孩子。

图11 情形2。我们发现可以将B右旋到右子树,通过一次右旋和着色就可以恢复红黑树的性质4了,因为没有哪个红结点是红色的孩子双亲。
进入每一个情形都是因为z和z.p都红色的,由于插入之前是合法的红黑树,所以z.p的另一个孩子是黑的,z.p.p也黑色的,图示的y是是z.p.p,所以y是黑色的。对y进行右旋,我们发现通过z的路径少了一个黑色,如图示交换一下颜色就恢复了红黑树的性质4了。
情形3:z的叔叔是黑色的,z是双亲的右孩子。

图12 情形3。z的叔叔是黑色的,并且z是右孩子。
我们发现对z的双亲y进行左旋,因为只有z和z的双亲不满足红色树的性质4,所以z的左右孩子都是黑色的,这样旋转并不会破坏z的孩子和z兄弟的黑高度的。然后把z指向z的左孩子,这时候就将情形3转换到了情形2了。
下面是修复红黑树四种情形的代码。最后,我们修复了根是黑色的性质2。

从上面的修复性质4的可以看,只有情形一在不做旋转的情况下,z的指针向上在树中移动两层。情形2经过一次旋转就可以恢复,情形3要先通过旋转变成情形2。所以我们得出结论,向红黑树中新插入一个结点着成红色,我们可以通过不超过两次的旋转就可以恢复红黑树的性质。

1.2.5 删除

红黑树的删除,其实也是先进行二叉查找树的删除,再调整颜色。
二叉树删除的三种情况中,对比观察图13,情况c中,使用y替换了z,只要我们将y着成z的颜色,那么我们很容易发现一个共同之处,那就是如果我们将虚线圈起来当成一个特殊的结点,那么所有从根结点出发经过双亲结点到达NIL树叶结点的路径肯定也经过孩子结点。那么二叉树删除的结果就是,圈中少了一个结点,如果我们将结点删除,但颜色保留,将刚移走的结点的颜色“塞”给x,也就是圈中的剩下的结点x,加上自身的颜色,此时x可能是“黑黑”也有可能是“红黑”。那么我们发现剩下的部分,除了性质1外,其它性质都没有变化。

图13 红黑树结点删除的初始情形。内圏的颜色是表示孩子的颜色,圈外表示双亲的颜色。x表示原删除或移走后剩下的结点的位置。(a)x的位置是z的左孩子,留下了z的颜色;(b)x的位置是z的右孩子,z的右孩子替换了z,留下了z右孩子的颜色;(c)x的位置是z后继的位置,z的后继已经替换了z,留下了原z后继的颜色。
我们发现一个规律,如果圈内有一红一黑,那么我们并不需要调整红黑树,直接将x着成黑色就行了。所以我们删除代码比之前普通二叉查找树的删除多了一些记录位置的代码 。还有一个值得注意的地方就是如果圈中的孩子是叶子结点,那么通过叶子结点是无法找到双亲的,所以我们不管是不是叶子结点都将p指向圈中双亲的双亲。

好了,现在我们可以开始调整“塞”给x上的黑色了,根据判断条件,只要x和y有一个是红色,均不用调整,而且调整前是合法的红黑树,x和y不可能同为红色,所以唯一的情况是x是黑色,被移走结点留下的也是黑色。下图所示的x的兄弟w都是右子树的例子,同样如果w是左子树是对称的。

图14 上面是分别是调整颜色是遇到的所有情况。(a)情形1,w颜色为黑色的,并且w的右孩子为红色,这时候,我们对x的双亲左旋转将x的新双亲和新叔叔都着成黑色,x的祖亲着成原x的双亲的颜色。(b)情形2,w颜色是黑色的,并且w的左孩子是红色的w的右孩子是黑色的,将w进行一次右转,重新着色,我们发现这个状态正好是情形1。(c)情形3,w的是黑色的并且左右孩子都是黑色的,我们将x和w都提取一个黑色给x的双亲,这时候我们把双亲看成新的x,继续调整。(d)情形4,w颜色是红色的,由于w是颜色是红色的,所以w的左右孩子都是黑色的。我们对x的双亲做一次左旋,重新着色,我们发现状态转换到了(a)(b)(c)中的任意一种了。
假设有函数C(m)表示如果m结点是黑色的,C(m) = 1;如果m结点是红色的C(m) = 0。并且我们知道x是双黑的,所以w不可能是nil结点,所以w是有左右孩子的。
情形1:x的兄弟w是黑色的,并且w的右孩子是红色的。
我们假设C(x.p)=p,C(x.r)=q。在调整前:
α子树的根到图示的根黑结点个数是2+p;
β、γ子树的根到图示的根黑结点的个数是2+p+q;
δ、ε、ζ子树的根到图示的根黑结点的个数是1+q’’。
我们交换w和x双亲的颜色,并将w的右孩子着成黑色,再对x.p执行一次左旋。我们发现在调整后:
α子树的根到图示的根黑结点个数是3+p;
β、γ子树的根到图示的根黑结点的个数是3+p+q;
δ、ε、ζ子树的根到图示的根黑结点的个数是1+q’’。
α、β和γ均比之前多了一个黑色,如果我们将x身上的额外的黑色去掉,那么α、β和γ到图示的黑结点个数与调整之前一样,分别是2+p和2+p+q,调整结束。

情形2:x的兄弟w是黑色的,并且w的左孩子是红色的。右孩子是黑色的。
这个情形比较简单,我们交换一下w和右孩子的颜色执行一次右旋,α、β、γ、δ、ε和ζ到图示的根的黑结点个数仍然不变,观察这个情形就转化了情形1了。

情形3:x的兄弟w是黑色的,并且w的左孩子是黑色的,右孩子也是黑色的。
因为w和左右孩子都是黑色的,并且x是“双黑的”,将w和x的黑色都向上提,这时候将w着成红色。x的双亲成了新的x了,继续向上调整。

情形4:x的兄弟w是红色的。
因为x是红色的,所以x的孩子和x的双亲都是黑色的,调换w的双亲与w的颜色进行一次左旋。我们发现x的新兄弟成了黑色,那么这就成情形1、2和3中的任意一种来调整了。
下面是fixup代码:

1.2.6 实现

参考附件:rbtree.c。

1.2.7 思考题

1. 先依次画出从初始空树中成功插入key为41,38,31,12,19,8的结点的红黑树。再画出依次删除8,12,19,31,38,41之成功后红黑树。

附件

bstree.c : 二叉查找树实现代码
rbtree.h : 红黑树的接口
rbtree.c : 红黑树的实现
如果你是windows用户
main.c :红黑树的操作实例
rbtree.exe:一个红黑树的操作实例编译方法: gcc -o rbree.exe rbtree.c main.c -mwindows
本文的其它参考文档:
第12章 二叉查找树
第13章 红黑树
全文下载:红黑树详解

分类: C/C++, 算法导论 标签:

第13章 红黑树(4)

2013年6月29日 没有评论

13.4 删除

跟其它n结点红黑色树的基本操作一样,删除一个结点的运行时间是O(lg n)。从红黑树中删除一个结点比插入一个结点要复杂一点。
从红黑树中删除一个结点的方法在基于TREE-DELETE方法的(第12.3节)。首先我们需要定制一下TRANSPLANT子方法,这样TREE-DELETE可以将它运用在红黑树上。

RB-TRANSPLANT与TRANSPANT有两个地方不一样。首先,第1行用T.nil代替了NIL。其次,在第6行的v.p赋值是无条件的:即使v指向哨兵结点,我们可以将v.p赋值。事实上,当v=T.nil,我们将能够利用v.p来赋值。
RB-DELETE方法有点像TREE-DELETE方法,但是增加了数行伪代码。一些增加的代码是为了跟踪y,它有可能导致破坏红黑的性质。当我们要删除结点z并且z有小于两个孩子,那么z将从树中删除,我们将y当作z。当z有两个孩子,y将是z的后继,y将会移动到z在树中的位置。当它从树中删除或者移动,我们将记下y的颜色,我们跟踪了结点x,将x移动到y在树中原来的位置,因为x可能会破坏红黑树的性质。删除结点z后,RB-DELETE将调用辅助方法RB-DELETE-FIXUP,这个方法会修改颜色和做一些旋转来恢复红黑树性质。

尽管RB-DELETE包含的伪代码是TREE-DELETE的两倍那么多,但是这两个方法有着相同的基本结构。你可以在RB-DELETE找到TREE-DELETE的每一行(有一点点变化,用T.nil替换了NIL,调用TRANSPLANT替换成了调用RB-TRANSLPLANT),在相同的条件下执行。
下面是这两个方法的其它的不同之处:

  • 我们维护了结点y,y做为从树中删除的结点或才在树中移动的结点。第1行设置了y指向z,当z有少于两个孩子时直接删除了。当z有两个孩子,第9行设置y指向z的后继,如同TREE-DELETE一样,并且y将会移动到z在树中的位置。
  • 因为y的颜色可能会改变,变量y-original-color存储了y在改变之前的颜色。第2和10行在对y进行了赋值后立即设置了这个变量。当z有两个孩子的时候,那么y≠z,并且结点y将移动到结点z在红黑树中的原始位置;第20行让y着成z相同的颜色。我们需要保存y的原始颜色在RB-DELETE的结尾测试它;如果它是黑色的,那么移除或者移动的y可能会破坏红黑树的性质。
  • 正如我们刚才讨论过的,我们记录y的原始位置的结点x。第4,7,11设置x指向y唯一的孩子或者,如果y没有孩子,指向哨兵T.nil。(回顾12.3节y没有左孩子。)
  • 因为结点x移动到了y的原始位置,x.p一直指向y的双亲结点在树中原始位置,甚至是,事实上也有可能是哨兵T.nil。就算z是y的原始双亲(如果z有两个孩子并且它的后继就是z的右孩子),x.p在RB-TRANSPLANT的也在第6行进行了赋值。(观察第5,8或者14的RB-TRANSPLANT的调用,传递的第二参数跟x是一样的。)
    当y的原始双亲是z的时候,然而,我们不希望让x.p指向y的原始双亲,因为我们将会删除这个结点。(译者注:z结点将用从树中删除,x.p指向这个结点就没有意义了)由于结点y将会提升取代z的位置,在第13行设置了x.p指向y,这会导致x.p指向y双亲的原始位置(译者注:原双亲的位置就是z在树中的位置),不管x=T.nil与否。
  • 最后,如果y是黑色结点,我们可能破坏一个或更的红黑树性质,所以我们在第22行调用RB-DELETE-FIXUP去恢复红黑树的性质。如果y是红色的,当y删除或者移动的时候,红黑树的性质没有被破坏,理由如下:
    1. 树中没有结点的black-height被改变。
    2. 没有红结点是相邻的。因为y取代了z在树中的位置,跟z的颜色是一致的,我们不可能在y的新位置找到两个相邻的红色结点。更进一步,如果y不是z的右孩子,那么y的原始右孩子x替换了y在树中的位置。如果y是红色的,那么x一定是黑色的,所以用x替换y不会导致两个红色结点变成相邻的。
    3. 因为如果y是红色的,它就不可能是根,根继续是黑色的。

如果结点y是黑色的,可能会出现三个问题,可以调用RB-DELETE-FIXUP将会修正它们。首先,如果y一开始是根并且y的一个红色的孩子变成了新的根,这样我们破坏了性质2。第二,如是x和x.p都是红色的,那么我们破坏了性质4。第三,在树内移动y将会导致任意一条之前包含y的简单路径少一个黑色结点。因此在树中任何以y为祖先的结点不都满足性质5。我们说之前的y的位置上的结点x有一个“额外”的黑色结点,这样就修正了性质5。换句话说,我们在任意包含x的简单路径上增加一个黑色结点,这样情形下,性质5就保持了。当我们移除或者移动黑色结点y,我们将y的黑属性“推”给结点x。问题就是现在结点x既不是红色也不是黑色,性质1将不满足。(译者著:x本身是有颜色的,y的颜色色留在了原地也就是现在x位置,那么x结点就有两种颜色,一种是本身的颜色,一种是黑色)换句话说,结点x可能是“双黑”或者“红和黑”,在包含x的简单路径上,它贡献了2个或者1个黑结点数量。结点x的颜色属性现在仍然是红色(如果x是红和黑)或者黑色(如果x是双黑)。换句话说,在x指向的结点上有一个额外的额外的黑附加上这个结点上而不是在color属性上。(译者著:color属性不能表示该结点的颜色了)。
我们现在可以看看RB-DELETE-FIXUP并考察它是如何修复查找树上的红黑属性的。

方法RB-DELETE-FIXUP恢复了性质1,2和4。练习13.4-1和13.4-2让你去说明方法是如何恢复性质2和4的,所以本节的余下部分,我们专注于性质1。第1-22行的while循环的目的是在树中向上移动额外的黑,直到:

  1. x指向了一个红和黑结点,这种情形我们在第23行将x的着成(单色)黑色。
  2. x指向了根,这种情况我们简单的“移除”额外的黑;或者
  3. 做一些适当的旋转和重新着色,然后我们退出循环。

在while循环里,x一直指向一个非根的双黑结点。我们在第2行里判断x是它双亲x.p的左孩子还是右孩子。(我们给出了x是左孩子情形的代码;x是右孩子的情况在第22行,这们是对称的)我们维护了指针w指向x的兄弟。因为结点x是双黑的,节点w肯定不是T.nil,否则从x.p到叶子w(单黑)(译者著:叶子是黑色的)的路径上的黑结点将会比x.p到x路径上的黑结点的数量要少。
代码中的这四种情形将会在表13.7中出现。在考查每一种情形前,让我们大致地看一下如何验证每一种情形的转换保持了性质5。关键思想在于每种情形的变化,所示的每一个树根(包括)到它的子树α,β,…… ζ都保持了黑结点的数量(包括x的额外的黑色)。因些如果变化之前满足性质5,那么之后它也满足。举个例子,如图13.7(a),它描述了情形1,变化前和变化后从根到任意子树α,β的黑结点的数量都是3。(再次提醒,记住x结点添加了一个额外的黑色)相同地,在变换前后,从根到任意的子树γ,δ,ε的黑结点的数量是2。在图13.7(b),图示的树根统计必须包含根根的颜色属性值c,它可能是红色或者黑色。如果我定义count(RED)=0和count(BLACK)=1,那么大变换前后,从根到α的黑结点的数量都是2+count(c)。这种情形下,通过变换后,新结点x的color属性c,但是这个结点的是红黑(当c=RED)或者双黑(当c=BLACK)。同样地,你还可以验证其它情形(参看练习13.4-5)。

情形1:x的兄弟w是红色的。

当结点x的兄弟w是红色的就是情形1(RB-DELETE-FIXUP的第5-8行和图13.7(a))。由于w肯定有黑色的孩子,我们可以交换w和x.p的颜色,并在x.p上做一次右旋,这不会违反红黑树的性质。旋转前w的孩子是x的新兄弟,它现在颜色是黑色的,因些我们把情形1变成了情形2,3或者4。

情形2:x的兄弟x是黑色的,并且w的孩子都是黑色的。

在情形2中(RB-DELETE-FIXUP的第10到11行和图13.7(b)),w的孩子都是黑色的。因为w也是黑色的,我们可以将x和w的黑都关掉,让x只有一个黑和w变成红色。为了补偿从x和w中移除的黑色,我们添加一个额外的黑色到x.p上,x.p原始可能是红色或者黑色。观察如果是通过情形1进入情形2的,新结点x是红黑色的,由于原始的x.p是红色的,新的结点是红黑的。意味着,新结点x的color属性值是红色的,然后当我们测试循环条件的时,循环结束。然后我们在第23行将新结点x(单黑)着成黑色。

情形3:x的兄弟w是黑色的,w的左孩子是红色的,并且w的右孩子是黑色的。

当w是黑色的,它的左孩子是红色的并且它的右孩子是黑色的就是情形3(第13到16行和图13.7(c))。我们可以先交换w和它左孩子的颜色并用w做一次右旋,这并不会破坏红黑树的属性。X的新兄弟w现在一棵带有红色右孩子的黑色的结点,这样我们就将情形3转换成了情形4了。

情形4:x的兄弟w是黑色的,并且w的右孩子是红色的。

当结点x的兄弟w是黑色的并且w的右孩子是红色的就是情形4(第17到21行和图13.7(d))。通过改变一些颜色和在x.p上的一次左旋,使它变成单黑,这样我们可以移除x上的额外的黑色并且不会破坏任何红黑树的性质。设置x成根将会在测试循环条件时使while循环终止。

分析

RB-DELETE的运行时间是多少呢?因为高度为n的红黑树是O(lg n),除去调用RB-DELETE-FIXUP的时间方法总时间花费O(lg n)。在RB-DELETE-FIXUP里,情形1,3和4的每一个都会在常数次颜色修改和最多三次旋转结束循环。情形2是唯一一个重复while循环的,并且只是x指针在树中向上移动,并不会旋转。因些RB-DELETE-FIXUP会花费O(lg n)的时间和最多三次旋转,因此RB-DELETE的总时间也是O(lg n)。

图13.7 RB-DELETE-FIXUP的while循环里的情形。黑色结点的color属性为BLACK,深色的阴影结点color属性为RED,浅色阴影结点color属性用c和c’表示,它可能是红色或者黑色的。字母α,β,…,ζ代表任意子树。每一种情形通过改变颜色和/或做一次旋转从左边的状态变成右边的状态。任何x的指向的结点都有一个额外的黑,这个结点可能是双黑或者红黑。只情形2会重复循环。(a)通过交换B和D的颜色和做一次左旋,将情形1转换在2,3或者4。(b)情形2中,通过将D结点着成黑色并将x指向B结点,x指向的额外的黑在树中向上移动。如果我们是通过情形1进入情形1,while循环将会终止,因为新结点x是红黑的,因此它color属性值c是红色。(c)通过交换C结点和D结点的颜色和一次右旋将情形3转换成情形4。(d)情形4通过改变一些颜色和一次左旋(不会破坏红黑树的性质)移除额外的黑,然后循环终止。

练习

13.4-1 证明执行完RB-DELETE-FIXUP,树根一定黑色的。
13.4-2 证明如在RB-DELETE中x和x.p都是红色的,通过调用RB-DELETE-FIXUP性质4被恢复了。
13.4-3 在练习13.3-2中,你发现一查从初始空树通过成功插入key41,38,31,12,19,8的红黑树。现在画出依次删除8,12,19,31,38,41之成功后红黑树。
13.4-4 RB-DELETE-FIUXP的哪一行代码我们将检查了修改哨兵T.nil?
13.4-5 在图13.7的的各种情形中,给出从图示的根到各个子树α,β,…,ζ的黑结点个数,并验证每个个数与变化后的相同。当结点的color属性值是c或者c’,就使用表达式count(c)或者count(c’)表示在你的统计中。
13.4-6 Skelton和Baron教授认为在RB-DELETE-FIXUP情形1开始的时候,x.p结点可能是黑色的。如果这个教授的说法是正确的,那么第5-6行就是错了。证明x.p在情形1开始的时候一定是黑色的,教授们的担心是多余的。
13.4-7 假设结点x通过RB-INSERT插入到红黑树,然后通过RB-DELETE立即删除。结果的红黑树与初始的红黑树一亲吗?验证一下你的答案。
全文下载:第13章 红黑树

第13章 红黑树(3)

2013年6月25日 没有评论

13.3 插入

我们可以在O(lg n)时间将一个结点插入到含有n结点的红黑树。为了插入结点,我们将TREE-INSERT方法(第12.3节)做稍稍的修改把树T当做普通的二叉查找树插入结点z,然后将z着成红色。(练习13.3-1让你解释一下为什么我们选择红色而不是黑色。)为了保持红黑树的性质,我们调用辅助方法RB-INSERT-FIXUP去着色和旋转。调用RB-INSERT(T,z)将结点z插入树T中,其中z结点已经包含填充了key。

TREE-INSERT和RB-INSERT方法有四个地方不一样。第一,所有TREE-INSERT使用NIL的地方都被替换成了T.nil。第二,在RB-INSERT的第14到15行,我们将z.left和z.right设置成了T.nil,是为了维护合适的树结构。第三,在第16行,我们将z着成红色。第四,由于将z着成红色将会导致红黑树的某个性质发生了违例,所有我们在第17行调用RB-INSERT-FIXUP(T,z)去恢复红黑树的性质。

为了理解RB-INSERT-FIXUP是如何工作的,我们将代码分成三个主要步骤去解释。首先,我们要判断在RB-INSERT中将z着成红色会出现哪些违反红黑树的性质的情况。其次,我们将考查第1到15行的while循环的目的。最后,我们将分析while循环体的的三种情况看它们是如何达到目的的。图13.4展示了RB-INSERT-FIXUP在红黑树上的执行过程的一个例子。
在调用RB-INSERT-FIXUP之前红黑树的哪些性质将不能保持?性质1将会继续保持,同理性质3,因为新插入的红色结点的两个孩子是T.nil。性质5,内容是从指定结点出发到叶子结点的每条简单路径上的黑色结点的数量是相同,这个性质也跟之前一样的,是因为结点z替换了(黑色)哨兵结点,并且z结点带有哨兵结点的红色结点。因此,只有性质2,要求根结点是黑色的,和性质4,红色结点不能有红色结点的孩子。这两个可能的不能保持的情况都是由z着成红色造成的。性质2是当z是根结点的时候不能保持,性质4是当z的双亲是红色的不能保持。图13.4(a)展示了z插入后违反性质4的一个例子。

图13.4 RB-INSERT-FIXUP操作。(a)插入后的结点z。因为z和它的双亲都是红色的,所以发一次性质4违例。因为z的叔叔是红色的,所以适应于情形1。我们重新将结点着色并且将指针z从树上向上提升,结果如(b)所示。跟上面的情形一样,z的它的双亲双都是红色的,但是z的叔叔是黑色的。因为z是z.p的右孩子,所以适用于情形2。我们做一次左旋,结果如图(c)所示。现在z是双亲的左孩子,那它适用于情形3。重新着色并右转直到成为图(d)中的树,它一棵合法的红黑树。
第1到15行的while循环在每次迭代的开始都维护了下面三个不变式:

  1. 结点z是红色的
  2. 如果z.p是根,那么z.p是黑色的。
  3. 如果红黑树的性质招到破坏,那么最多只有一个性质被破坏,性质2或者性质4被破坏。如果是性质2,那是因为z是根并且是红色。如果性质4被破坏那是因为z和z.p都是红色的。

c部分,处理这些违反红黑树性质的部分,在RB-INSERT-FIXUP恢复红黑树性质上比(a),(b)部分更为重要,我们用它来了解程序代码中的情况。因为我们注意力聚集在z结点及它在树中的周围结点上,从(a)部分我们知道z是红色的。我们可以利用(b)部分知道z.p.p是存在的,我们在第2,3,7,8,13中引用到它。(译者注,因为b部分说根是黑色的,而且z.p也是红色的,所以z.p.p肯定存在。)
我们证明在第一次迭代时循环不变式是真的,每次迭代都维护这个不变式,在循环结束时,这个不变式将给我们提供一个很好性质。
我们从初始化和终止开始讨论。然后我们详细考查循环体是如何工作的,我们将讨论每次迭代的循环维护这个不变式。随后,我们将表明每次循环迭代后都有两种可能的结果:z指针向上移动或者做一些旋转后循环终止。
初始化:在第一次迭代前,我们用一棵合法的红黑树开始,然后我们插入了红色结点z。我们各种情况下调用RB-INSERT-FIXUP时不变式都是成立的:
当调用RB-INSERT-FIXUP时,z是被添加的红色结点。
如果z.p是根,那么z.p开始时就是黑色调用RB-INSERT-FIXUP不用修改。
当我们调用RB-INSERT-FIXUP时,我们已经看到性质1,3,5保持不变。
如果树的性质2不能保持,那么说明添加了红色的根结点z,z是树中的唯一一个内部结点。因为双亲和两个孩子都是哨兵结点,它们都是黑色的,树就不会违反性质4。因些违反性质2的情况,是整棵树中唯一一处破坏红黑树性质的地方。
如果树的性质4不能保持,由于结点z的孩子是黑色的哨兵并且在添加z前整个棵树没有其它的违反红黑性质的地方,那么这种违反一定是z和z.p都是红色的。而且,没有 对红黑树的其它性质的违反。
终止:当循环结束时,它是因为z.p是黑色才结束的。(如果z是根结点,那z.p是哨
兵T.nil,它也是黑色的)因此,在循环结束时,树不会违反性质4。通过循环不变式,仅仅只有性质2可能不满足。第16行也恢复了这个性质。所以在RB-INSERT-FIXUP结束时,所有的红黑树性质都满足了。
维护:在while循环里我们实际上需要考虑到6种情形,但有三种情形与另外三种情形是对称的,取决于第二行的z的双亲z.p是z的祖亲z.p.p的左孩子还是右孩子。我们仅仅给出了z.p是左孩子的解决方案的代码。结点z.p.p是存在的,是由于b部分的循环不等式,如是z.p是根,那么z.p是黑色的。因为我们仅当z.p是红色才会进入循环迭代,我们知道z.p肯定不是根。意味着z.p.p是存在的。
我们根据z双亲的兄弟或称作“叔叔”的颜色来区分情形1与情形3。第3行让y指向z的叔叔z.p.p.right,第4行测试y的颜色。如是y是红色的,我们执行情形1。否则,执行跳到情形2和情形3。所有的三种情况,z的祖亲是黑色的,是因为z.p是红色的,只有z和z.p是违反性质4。

情形1:z的叔叔是红色的

图13.5展示了情形1(第5到8行),z.p和y都是红色的时候属于这种情形。因为z.p.p和y是黑色的,我们将z.p和y都着成黑色,用来修复z和z.p都是红色的问题,并且我们z.p.p着成红色来保持性质5。我们把z.p.p当成新的结点z来重得while循环。在树上z指针向上移动了两层。
现在,我们证明情形1在下一次迭代前维护了循环不等式。我们用z来表示当前迭代中的结点z,那z’ = z.p.p来表示第1行下次迭代被为结点z的结点。

  1. 因为本次迭代将z.p.p着成了红色,结点z’在下一次迭代开始时是红色的。
  2. 结点z’.p是本次迭代的z.p.p.p,它的颜色没有改变。如是这个结点是根,它在本次迭代前是黑色的,并且在下次迭代开始是也保持黑色。
  3. 我们已经讨论了情形1维护了性质5,它不会破坏性质1或者3。


图13.5 RB-INSERT-FIXUP情形1的处理过程。性质4被破坏了,由于z和它的双亲z.p都是红色的。不管z是右孩子还是左孩子,我们操作方法都是一样的。每一个子树α,β,γ,δ和ε都有一个黑色的根,并且它们有相同的black-height。情形1改变了一些结点的颜色,为了保持性质5:从一结点向下到叶子结点都有相同数量的黑结点。while循环所z.p.p当成新的z继续下去。所以违反性质4都只可能发现在新红色z和它的双亲之间,如它的双亲是红色的,处理方法跟上面的一样。

情形2:z的叔叔是黑色的并且z是右孩子
情形3:z的叔叔是黑色的并且z是左孩子

在情形2和情形3中,z的叔叔的颜色是黑色的。我们通过z是z.p的左孩子还是右孩子来区分这两种情形。第10到11行形成了情形2,在图13.6中与情形上放在一起。在情形2中,结点z是双亲的右孩子。我们立即使用一次左旋变成了情形3(第12到14行),这种情形z变成了左孩子。因为z和z.p都是红色的,旋转影响了结点的black-height和性质5。不管直接的情形3还是通过情形2转化而来的,z的叔叔都是黑色的,否则的话将会执行情形1了。另外,z.p.p是存在的,在执行第2和3行时,我们已经讨论了这个结点是存在的,并且在第10行将z向上提升了一层然后在第11行向下降了一层,z.p.p仍然没有变化。在情形3中,我们将一些结点的颜色改变了并且做了一次右旋,这些是为了保持性质5,然后在一条线上就不存在两个红色的结点,就这样完成了。因为现在z.p是黑色的了,while循环不再进行下一次的迭代了。

图13.6 RB-INSERT-FIXUP情形2和3的处理过程。跟情形1一样,不管是情形2还是情形3由于z和z的双亲都是红色的而破坏了性质4。它的任意一棵子树α,β,γ,δ都有一个黑色的根(α,β,γ是根据性质4,δ如果不是黑色将执行情形1),并且它有相同的black-height。我们通过一次左旋将情形2转化成情形3,保持了性质5:从一结点向下到叶子结点都有相同数量的黑结点。情形3一些点颜色被改变了并且做了一次右转,也是为了保持性质5。然后while循环结束了,因为性质4满足了:在一条线上不再有两个红色结点。
现在我们来证明情形2与情形3保持了循环不等式。(正如我们讨论过的,z.p将会在第1的下次测试z.p将会是黑色,并且循环体将不再执行。)

  1. 情形2使z指向z.p,z.p是红色的。z和它的颜色在情形2和3中不再变化。
  2. 情形3使z.p着成黑色,所以如果z.p是下次迭代开始的根,那么它就是黑色的。
  3. 跟情形1一样,性质1、3和5在情形2,3中也得以保持。由于在情形2和3中,结点z不是根,我们知道这不会破坏性质2,由于唯一结着成红色的结点在情形3变成一个黑色结点的子女。情形2和3修正了性质4的破坏,同时它们也不会引进新的破坏。

在讨论每次循环迭代维护不变式时,我们也证明了RB-INSERT-FIXUP正确地恢复了红黑树的性质。

分析

RB-INSERT的运行时间是多少呢?由于n结点的红黑树的高度是O(lg n),RB-INSERT第1到16行花费了O(lg n)时间。在RB-INSERT-FIXUP中,while循环只有遇到情形1的时候才会重复循环,然后z向树上移动两层。while循环执行的总次数因此是O(lg n)。因此RB-INSERT总共花了O(lg n)的时间。更有意思的是,它旋转次数决不会多于两次,因为如果执行了情形2或者情形3,while循环就结束了。

练习

13.3-1 在RB-INSERT的第16行,我们将新插入的结点z设置成了红色。观察如果我们选择将z的颜色设置成黑色,那么红黑树的性质4会不会破坏。为什么我不选择将z设置成红色?
13.3-2 成功将key为41,38,31,12,19,8都插入空的红黑树后,画出这棵红黑树。
13.3-3 假设在图13.5和图13.6中任意子树α,β,γ,δ和ε的back-height是k。标记每个结点的black-height去验证图示的转换能保持性质5。
13.3-4 Teach教授担心RB-INSERT-FIXUP可能会设置T.nil.color为红色,这样的话当z是根的时候循环将不会结点。通过证明RB-INSERT-FIXUP决不会将T.nil.color设置成红色来说明这位教授的担心是没有必要的。
13.3-4 假设红黑树是通过RB-INSERT插入n结点形成的。证明如果n>1,那么树中至少有一棵红结点。
13.3-6 考虑一下,如果红黑树表示没有存储双亲结点的指针,应该如何有效地实现RB-INSERT。
全文下载:第13章 红黑树

第13章 红黑树(2)

2013年6月17日 2 条评论

13.2 旋转

查找树操作TREE-INSERTTREE-DELETE,运行在nkey的红黑树上,花费时间O(lg n)。由于改动了树,所以结果树可能不符合13.1节列举的红黑树的性质。为了恢复这些性质,我们必须改变树中一些结点的颜色和修改一指针结构。
我们通过旋转来修改指针结构,它是一个局部操作使查找树保持二叉查找树的属性。图13.2展示了两种旋转:左旋和右旋。当我们对结点x进行左旋时,我们假设yx的右孩子并且不是T.nil; x可以是树中任意右孩子不空的结点。左旋的“轴”是沿着xy的。它使y成为子树的根,x成为y的左孩子,y左孩子成为x的右孩子。
LEFT-ROTATE伪代码假设x.rightT.nilroot的双亲为T.nil

      图13.2 二叉查找树的左旋操作。左旋操作LEFT-ROTATE(T,x)通过修改常数个指针来改变两个结点的结构把右边的结点的结构变成左边的结构。相反的右旋操作RIGHT-ROTATE(T,y)将左边的结构变成右边的结构。α、β和γ表示任意形态的子树。旋转操作要保持二叉树的性质:α子树上的所有keys要小x.key,x.key要小于β子树上的所有keysβ子树的keys要小于y.keyy.key要小于γ子树上的所有的keys

图13.3 展示了LEFT-ROTATE如何修改二叉查找树的实例。代码跟RIGHT-ROTATE是对称的。LEFT-ROTATERIGHT-ROTATE的运行时间者是O(1)。一次旋转只修改了指针;结点其它属性都保持不变。

13.3 方法LEFT-ROTATE(T,x)如何修改一棵二叉查找树的实例。中序遍历输入树和中序遍历修改过后的树产生相同的key序列。

练习

13.2-1 写出RIGHT-ROTATE方法。
13.2-2 证明在任意n结点的二叉查找树上,刚好有n-1种可能的旋转。
13.2-3 a,b,c分别是α、β和γ的任意结点,在图13.2的左侧。如图在结点x上做一次左旋转a,b,c的深度是如何变化的?
13.2-4 证明任意n结点的二叉查找树经过O(n)次旋转得其它任意形态的n结点二叉查找树。(提示:首先证明最多通过n-1次右旋可以将树的结构变成右链的形态。)
13.2-5 我们说如果通过一系列的调用RIGHT-ROTATE可以从二叉查找树T1转换成T2,那么二叉查找树T1右转(right-convert)T2 。举出一个例子T1T2,使得T1不能右转成T2。然后证明如果树T1右转成T2,那么它可以通过调用O(n^2)RIGHT-ROTATE得到。
全文下载:第13章 红黑树