红黑树总结和两种实现的比较

上半学期，忙里偷闲利用课余时间帮一个朋友编写了一个大型稀疏矩阵运算的程序，由于当时没有时间整理，现在利用暑假整理下。由于其中主要用到了红黑树结构，因此只对红黑树进行下总结。下面先简单的介绍下红黑树，然后对两种实现（linux内核实现方式与STL实现方式）当中的细节做下简单对比。

红黑树的具体定义不再罗列啦，网上一搜一大堆，主要说下其特点和基本操作。红黑树是一种平衡搜索树，其特点自然和“平衡”有关，就是避免了在最糟糕的情况下，其搜索复杂度达到O(n)（其中n是节点个数）。红黑树最大搜索次数为2lg(n+1)，证明可以利用红黑树的性质和归纳法马上得到。红黑树的基本操作和普通的二叉树是一样的，即：查找、插入和删除。查找没什么可说的，主要说下插入和删除，因为插入和删除需要考虑维持红黑树的“平衡”性质。下面分别介绍下插入和删除：

1 、插入：我们假设插入的节点颜色为红色（之所以为红色是因为这样恢复红黑树比较简单），这样当插入节点后主要会破坏红黑树的两个性质，即：1)根节点为黑色，2)插入节点与其父节点的颜色同时为红色。对于情况一，我们只需简单的将插入节点的颜色设为黑色即可，这样的改变不会破坏红黑树的其他四条性质，同时又满足了根节点的颜色为黑色的性质。对第二种情况我们分两种情况进行讨论，见下左图：

                         

        

这就是插入节点非根节点时破坏红黑树的两种情况(在第二种情况是，如果插入的节点是其父节点的右孩子，则可以对其父节点进行一次左旋，转化为上述情况)。
    2、删除：如删除的节点不同时具备两个孩子且其颜色为红色则可以直接删除，令其后继结点取代其父节点即可，不会破坏红黑树的性质。因为删除的节点为红色，所以不可能是根节点和叶节点，即根节点和叶节点仍旧为黑色，又因为删除的节点颜色为红色，所以不会减少每条路径上的黑色节点的个数，最后因为删除的节点为红色，所以删除节点的父节点为黑色，将删除节点的后继结点取代删除节点不会破坏性质4。若删除节点存在两个子节点，直接将删除节点的后继结点替换到删除节点的位置，并将颜色设置为删除节点的颜色，这样就相当于删除其后继结点只需判断其颜色即可，如其为红色分析同上。下面分析删除的节点颜色为黑色的情况，如上右图。上述节点D为要删除的结点。删除操作比插入操作稍微复杂些，但是对于删除操作来说都可以转化为上述情况，比如若C为红色时，此时A为黑色，对A进行一次左旋即为上述情况，再如若E为红色F为黑色时(若F也为红色，可按上述做)则最C进行一次右旋即可，通过上述操作后删除也可以保持红黑树的性质。

下面给出linux和STL两份源码中的主要不同之处，并进行比较，如下：
linux源码：

struct rb_node
{
    unsigned long  rb_parent_color;
#define    RB_RED        0
#define    RB_BLACK    1
    struct rb_node *rb_right;
    struct rb_node *rb_left;
};
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
    rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color)
{
    rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}

STL源码：

struct _Rb_tree_node_base
{
  typedef _Rb_tree_Color_type _Color_type;
  typedef _Rb_tree_node_base* _Base_ptr;

  _Color_type _M_color;
  _Base_ptr _M_parent;
  _Base_ptr _M_left;
  _Base_ptr  _M_right;
};
static _Link_type& _S_parent(_Link_type __x)
    { return (_Link_type&)(__x->_M_parent); }
 static _Color_type& _S_color(_Link_type __x)
    { return (_Color_type&)(__x->_M_color); }

可以看到linux内核的实现充分利用了操作系统中的一些特性，例如利用虚拟地址的分配粒度都是64位对齐（windows核心编程里面说的），这样就可以把颜色值和父节点的指针统一表示来（用父节点指针的底两位表示颜色），见linux源码中的三个函数。而STL中的实现和我们平时一样中规中矩使用普通的指针。
在具体实现泛型上也是不同的，STL中采用的是C++的模板特性，而linux内核采用的是一种更高的抽象来实现泛型，就像实现链表一样，它把这些操作的高度抽象出来（例如：红黑树的抽象为：父节点、左右孩子节点和颜色）写成一个结构，然后哪里需要就把他插入到那里，代码和红黑树是一种聚合关系。
参考文献：
STL源码解析 208~232
算法导论      164~180

本文来自：http://blog.chinaunix.net/uid-28311809-id-3823619.html