分类： LINUX
2009-12-10 15:18:21
在研究SEP4020的Linux内核内存管理时遇到个红黑树，老是琢磨不透为什么要采用这么复杂的红黑树呢，通过网上资料的讲解和自己对linux的分析现在算是懂了一些了。
满足下面几个条件的二叉搜索树，称为红黑树：
1. 任何一个节点都被着色――红色或是黑色。
2. 根节点是黑色的。
3. 所有的NIL节点都看成黑色（NIL节点是就是一个假想的或是无实在意义的节点，所有应该指向NULL的指针，都看成指向了NIL节点。包括叶节点的子节点指针或是根节点的父指针）。
4. 如果一个节点是红色的，那么它的子节点一定是黑色的。（但对于黑节点的子节点可以是红或黑）
5. 对于任何一个节点而言，从该节点到它的子孙节点中的NIL节点路径中，所包含的黑节点个数相同。
一、黑高度的定义：
从任何一个节点，向下到底部的路径中，包含的黑节点的个数，称为这个节点的黑高度。从红黑树的第５条性质可以看出，黑高度是唯一的、确定的。
只要同时满足红黑树的这些条件，就一定会有“红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过２倍”这个平衡的性质。
我们可以假设，如果存在两条路径L和S，L比S长两倍以上（S路径上有n个节点，L上有大于2n个节点）。可知，S的黑高度最大只可能是n，那么根据第５条性质，L的黑高度也大也只可能是n，也就是，L路径上一定有超过n个红色节点（因为节点不是黑的就必定是红的）。所以，肯定会有两个以上的红色节点是相邻的。这就与第４个条件矛盾了。所以，红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过２倍。
红黑树的高度h<2lg(n+1)（这个在《算法导论》13.1节中有证明）。也就是说，红黑树的操作的时间复杂度是O(lgn)的。
二、为什么二叉树要变成红黑树？
二叉搜索树的操作时间复杂度，取决于树高h，因此，我们当然就希望h尽量地小以提高操作的效率。从直观上就可以发现，二叉搜索树各子树的规模越平均，它的高度就会越小。所以在应用中，一般都会将二叉搜索树实现成一种平衡树，以保证最差时间复杂度为O(lgn)。红黑树就是其中的一种，应用得很广泛（SGI STL的set和map就是基于红黑树来实现，Linux内核中也用到这个数据结构）
红黑树是二叉搜索树的一种。它与普通二叉搜索树不同的是，红黑树的每个节点都附加了另一个属性――颜色，可以是红色，也可以是黑色。通过对于每条路径上节点颜色的规则进行限定，红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过２倍。所以，红黑树是一种近似平衡的二叉搜索树。
到此我总算知道为什么Linux的进程内存管理中需要红黑树了，原因就是采用这种树不论从从哪开始搜索一个线性内存结构vm_area_struct所需的时间是最小而且是唯一的，这样其搜索效率也是最高的。
红黑树的查找、最大值、最小值、前趋、后继等操作，与普通的二叉搜索树没有什么区别。但红黑树的插入和删除操作需要重新实现。仅仅用普通的二叉搜索树的插入和删除动作，可能会破坏红黑树本身的一些性质，因此，需要进行额外的处理。这些额外的处理主要是改变树节点的颜色，或是改变树的结构。
三、树的旋转
改变树的结构，主要是用旋转。旋转有两种，左旋和右旋，下面是这两种旋转的：
这种旋转的操作，是在二叉搜索树的局部对树的结构进行调整的一种方式，经过旋转之后，二叉搜索树的性质是不会发生改变的。如下图：
在我们的Linux内核中红黑树代码在/lib/rbtree.c中实现的。
在内核中的红黑树的左旋转和右旋转函数是：
static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)；
static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)；
向红黑树插入节点，先将需要插入的节点着成红色，用普通二叉搜索树的方法将这个节点插入到树中，然后再想办法把被破坏的红黑性质恢复。（将新插入的节点颜色着成红色，可以尽量减少对红黑性质的破坏，恢复起来也容易。因为插入红色节点的话，那么被破坏的部分会在局部，因为这时候红黑树的高度没有改变的，考虑的问题也就比较少，恢复过程也容易形成递归，详细见下文说明）
将节点插入红黑树的函数：
rb_link_node(&vma->vm_rb, rb_parent, rb_link);（但这个函数只是将插入的节点染成红色，node的父节点为rb_parent，rb_link即为node）
分析：我们考虑下，如果一个红色节点（下文称用Z指向它）被插入到树中，那么有哪些红黑性质可能被破坏呢？只有规则第2条（根节点是黑色的）以及第4条（红色节点的子节点一定是黑色节点），其它都不会被破坏。
如果插入的节点的父节点是黑色的，那么不需要做任何调整，这红黑树是正常的。如果父节点是红色，或没有父节点（也就是插在了树根的位置），那么就要进行调整以保证红黑树是正确的。
首先对第4 条进行分析，我们知道，插入一个新的节点，这个节点肯定会被放到树的底部成为一个叶节点（参考普通二叉树的插入过程），那么这个红色节点就没有可能和自己的子节点同色（因为叶节点的子节点是NIL节点，都是黑色的），如果第4条被破坏的话，肯定是Z指向的节点的父节点是红色的。因此，为了使分析和解决更加容易和清晰，我们在对树进行调整以恢复红黑特性时，始终使得Z总是指向相邻红色的节点中的子节点（指针Z可能会向上升到树的中部或根部）。基于这个做法，我们可以知道，如果是第2条被破坏了的话，也就是Z指向根节点了，那么第4条肯定就符合了（因为Z的父节点是NIL，黑色的），因此对第2条性质的恢复变得很简单，只需要被根从红色变为黑色即可。这时，所有性质都会被满足了（因为是根节点，所以根节点被着为黑色时，所有路径都黑高会统一加1，也就是第5条不会被破坏，操作之后的红黑树仍然是正确的）。好了，现在只留下第4条性质的恢复的问题了。
如果第4条被破坏了，也就是说，Z的父节点是红色的，那么，说明，Z一定有祖父节点，而且是黑色的（否则插入前原树就有问题，又或是调整时的方法不正确）。因此可以把问题放到以Z的祖父节点为根节点的子树内进行解决，这样可以把调整的范围最小化，而且这也是有可能的：只要不改变这子树的黑高度，那么就不会对树的其它部分产生影响。我们要做的就是在这个子树范围内把红黑性质调整回来。再看子树的根是否与其父节点同为红色，是的话，就再次用前面所说的去解决它，一直向上递归到红黑性质被恢复为止。
四、红黑树的节点插入及调整
对第4条性质的恢复，根据Z的父节点是Z的祖节点的左子节点还是右子节点，分为两组对称的情况，每组有3种情况。下面我们只对其中一组进行说明，以Z的父节点是Z祖节点的左子节点为例：
第一种：Z的“叔父”节点是红色。
如上图所示，在这种情况下，将父、叔节点都着为黑色，再将子树根节点着为红色，那么子树的黑高度没有发生改变，而且红黑性质得得到了调整。此时，再将Z指向子树的根节点，向上递归恢复红黑特性。
第二种：Z的“叔父”节点是黑色的，Z是父节点的左子节点
如上图，将Z的父节点与祖节点进行一次右旋，并把父节点着黑色，原来的祖节点着红色。这些子树的红黑特性得到了恢复，而且子树的黑高度没有变化。另外，由于子树根节点已经是黑色了（这个节点不会出现父子同为红色的问题了），所以不必再向上递归了，此时整个树的红黑特性都已经是正确的了。
第三种：Z的“叔父”节点是黑色的，Z的父节点的右子节点。
如上图，将Z本身与其父节点进行一次左旋，让Z指向原来的父节点，就可以调整为情况二，而情况二已经得到解决。
这样，红黑树的节点插入问题就得到了解决。
在Linux内核中进行红黑树调整时的做法
// 对插入的红色节点进行局部调整
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
struct rb_node *parent, *gparent;
while ((parent = node->rb_parent) && parent->rb_color == RB_RED)/*如果父节点是红色才需要调整的*/
{
gparent = parent->rb_parent;
if (parent == gparent->rb_left)/*如果parent是gparent的左节点*/
{
{
register struct rb_node *uncle = gparent->rb_right;
if (uncle && uncle->rb_color == RB_RED)/*第一种：Z的“叔父”节点是红色*/
{
uncle->rb_color = RB_BLACK;
parent->rb_color = RB_BLACK;
gparent->rb_color = RB_RED;
node = gparent;
continue;
}
}
if (parent->rb_right == node)/*第三种：Z的“叔父”节点是黑色的，Z的父节点的右子节点。*/
{
register struct rb_node *tmp;
__rb_rotate_left(parent, root);/*先将parent于node进行左旋转*/
tmp = parent;
parent = node;
node = tmp;
}
parent->rb_color = RB_BLACK;/*第二种：Z的“叔父”节点是黑色的，Z是父节点的左子节点*/
gparent->rb_color = RB_RED;
__rb_rotate_right(gparent, root);/*将parent与gparent进行右旋转*/
} else {/*如果parent是gparent的右节点*/
{
register struct rb_node *uncle = gparent->rb_left;
if (uncle && uncle->rb_color == RB_RED)
{
uncle->rb_color = RB_BLACK;
parent->rb_color = RB_BLACK;
gparent->rb_color = RB_RED;
node = gparent;
continue;
}
}
if (parent->rb_left == node)
{
register struct rb_node *tmp;
__rb_rotate_right(parent, root);/*在这里node与parent右旋转*/
tmp = parent;
parent = node;
node = tmp;/*在这里还原下node与parent次序*/
}
parent->rb_color = RB_BLACK;
gparent->rb_color = RB_RED;
__rb_rotate_left(gparent, root);
}
}
root->rb_node->rb_color = RB_BLACK;
}
