灵魂守卫

RTMP握手协议

根据RTMP的文档，RTMP的握手过程为：

下面是握手的数据格式：

其中：
时间1：C发送C1时，C上的时间
时间2：S发送S1时，S上的时间
时间3：S接到C1时，S上的时间
时间4：C接到S1时，S上的时间
(时间2和时间3可能相等)

所以上面的过程写成代码应该是： 阅读全文…

本文是对RTMP协议的中文翻译
TXT：rtmp_utf8
HTML：rtmp.html
DOC：rtmp.doc
PDF:rtmp.pdf
原版地址：rtmp_specification_1.0

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

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

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

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

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服务器。很多人可能苦于寻找下面的三个编码参数而不得要领。其实要想得到也是很简单的。 阅读全文…

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”,要不然就遇到这种情况会停止转化。

原文地址：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]类似，这是子进程没有继承向子进程标准输入中写数据和向子进程标准输出读数据，因为父进程设置这两个句柄不可以继承。同时父进程也应该关闭自己的向子进程标准输入中读数据和向子进程中标准输出中写数据的句柄。

原子操作
在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

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语言的读者。本文最主要的参考资料是《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章 红黑树
全文下载：红黑树详解