红黑树

首先红黑树是一种平衡树，通过红黑染色的方式保持平衡

术语解释

• NIL：NIL节点是一个空节点，我们可以认为它是一个空指针指向的节点，代表这里什么也没有，在红黑树中我们认为一个NIL节点的颜色默认为黑色，虽然并没有一个实际的节点储存这个颜色信息

红黑树必须满足以下四条性质：

1. Every node is either red or black.
2. All NIL nodes (figure 1) are considered black.
3. A red node does not have a red child.
4. Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.

由以上四个限制可以得到以下性质：

the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf

这个结果很容易想到，根节点到达每个叶节点上的黑色节点数一样，那么最长路径和最短路径之间的节点数量差别只有红色节点，而红色节点不能连续出现（由限制3)可知），所以最长路径最多是最短路径的两倍（红黑交替和全黑）
这就使得红黑树能够维持一个高平衡性，保证了最长路径和最短路径的差值不会太大

Linux中的红黑树的使用

在具体学习红黑树的代码之前，我们先看一下Linux源码中对红黑树使用的文档和代码：

search

struct mytype *my_search(struct rb_root *root, char *string)
{
      struct rb_node *node = root->rb_node;

      while (node) {
              struct mytype *data = container_of(node, struct mytype, node);
              int result;

              result = strcmp(string, data->keystring);

              if (result < 0)
                      node = node->rb_left;
              else if (result > 0)
                      node = node->rb_right;
              else
                      return data;
      }
      return NULL;
}

其中用到的数据结构定义如下：

struct rb_root {
	struct rb_node *rb_node;
};

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
};

struct mytype {
      struct rb_node node;
      char *keystring;
};

然后我们看一下 container_of 的定义：

#define container_of(ptr, type, member)                   \
    ({                                                    \
        const typeof(((type*)0)->member)* __mptr = (ptr); \
        (type*)((char*)__mptr - offsetof(type, member));  \
    })

宏的作用是：
接收指向一个对象（数据）的指针，这个数据所属于的结构体的类型，以及这个数据在结构体中的成员名，返回指向这个结构体的指针
简而言之就是取容器

所以 container_of(node, struct mytype, node)这个宏的作用就是从 node这个属于红黑树部分的结构体，获得它的容器，从而得到具体的数据
这里 container_of()的原理是通过计算指定成员的偏移量，以及其地址，计算出包含它的结构的地址

这里采用了类似装饰器的想法，mytype把红黑树节点包起来，使得数据可以和红黑树分开单独编写逻辑，这是在没有类和模板之类的东西的C语言下对代码复用的一种实现

知道这一部分的设计思想后，搜索部分就是简单的BST的搜索过程，由于储存的是字符串，所以使用 strcmp()来比较数据的大小

insert

下面是插入操作的代码：

int my_insert(struct rb_root *root, struct mytype *data)
{
      struct rb_node **new = &(root->rb_node), *parent = NULL;

      /* Figure out where to put new node */
      while (*new) {
              struct mytype *this = container_of(*new, struct mytype, node);
              int result = strcmp(data->keystring, this->keystring);

              parent = *new;
              if (result < 0)
                      new = &((*new)->rb_left);
              else if (result > 0)
                      new = &((*new)->rb_right);
              else
                      return FALSE;
      }

      /* Add new node and rebalance tree. */
      rb_link_node(&data->node, parent, new);
      rb_insert_color(&data->node, root);

      return TRUE;
}

在寻找插入节点部分和一般的BST一样，找到插入位置后使用 rb_link_node()将节点插入到红黑树中，然后使用 rb_insert_color()来维护红黑树的性质（之前提到的四条规则）
关于如何维护红黑树的性质及其具体代码，我们在后面的实现中再讨论

removing and replacing

删除操作和替换操作是Linux中自带实现的，只需要调用函数即可：

void rb_erase(struct rb_node *victim, struct rb_root *tree);
void rb_replace_node(struct rb_node *old, struct rb_node *new,
                      struct rb_root *tree);

只要找到了指定的节点，就可以通过这两个函数来删除或者替换节点

次序相关的操作

struct rb_node *rb_first(struct rb_root *tree);
struct rb_node *rb_last(struct rb_root *tree);
struct rb_node *rb_next(struct rb_node *node);
struct rb_node *rb_prev(struct rb_node *node);

这四个函数可以在任意一棵红黑树中找到最小值、最大值、后继、前驱
相关的操作在BST中都会介绍到

红黑树的操作

现在知道了红黑树的限制，我们的工作就是如何让BST的操作能够满足上面的四个性质，下面我们一个个操作来说：

(这里采用的是wikipedia的代码，linux的代码我们最后再看)

首先请记住上图第一张中的N、P、S、C、D节点的位置，本文来自我的学习笔记，所以并没有很多配图，红黑树的核心操作就来源于这五个节点的变化，请对号入座

插入

首先关于红黑树所使用的结构如下：

enum color_t { BLACK, RED };

struct RBnode {     // node of red–black tree
  RBnode* parent;   // == NIL if root of the tree
  RBnode* child[2]; // == NIL if child is empty
    // The index is:
    //   LEFT  := 0, if (key < parent->key)
    //   RIGHT := 1, if (key > parent->key)
  enum color_t color;
  int key;
};

#define NIL   NULL // null pointer  or  pointer to sentinel node
#define LEFT  0
#define RIGHT 1
#define left  child[LEFT]
#define right child[RIGHT]

struct RBtree { // red–black tree
  RBnode* root; // == NIL if tree is empty
};

首先我们要插入一个新的节点，通过一般BST的方式找到该节点对应的位置：

RBnode** find_place(RBtree* tree, int key) {
        RBnode** node = &tree->root;
        while (*node != nullptr) {
                if (key < (*node)->key)
                        node = &(*node)->left;
                else if (key > (*node)->key)
                        node = &(*node)->right;
                else
                        return nullptr;
        }
}

这里和Linux源码一样使用了指针的指针，用来得到结构 RBnode的中指针 left和 right，这样能够方便直接修改一个节点的父节点

找到这个节点的位置后我么可以直接将其插入红黑树，为了维持红黑树的第四性质：

Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
我们默认插入的节点为红色，并且检测当前的节点的case

这里的case指的是一个节点附近和它相连的一系列节点的构成情况，是否构成一个违反红黑树性质的情况

我们把插入后的情况检查分为6种：

case 1

插入的节点的父节点是黑色，此时红黑树性质不被破坏，不做任何改动

case 2

如果P节点和U节点都是红色，那么祖父节点一定是黑色，为了维护红黑树，我们需要把P和U节点染成黑色，然后把G节点染成红色，这样局部满足了红黑树性质
同时，为了让祖父节点不破坏role3，我们把N节点设置为G，然后循环这个过程，直到N节点为空，或者构成不需要修改的情况

case 3

如果插入的节点为根节点，则不需要改动

case 4

如果插入的父节点是红色且为根节点，则改变父节点的颜色为黑色即可

上述四种情况都很简单，代码如下：

void RBinsert1(RBtree* T,         // -> red–black tree
               struct RBnode* N,  // -> node to be inserted
               struct RBnode* P,  // -> parent node of N ( may be NULL )
               byte dir)  // side ( LEFT or RIGHT ) of P where to insert N
{
    struct RBnode* G;  // -> parent node of P
    struct RBnode* U;  // -> uncle of N

    N->color = RED;
    N->left = NIL;
    N->right = NIL;
    N->parent = P;
    if (P == NULL) {  // There is no parent
        T->root = N;  // N is the new root of the tree T.
        return;       // insertion complete
    }
    P->child[dir] = N;  // insert N as dir-child of P
    // start of the (do while)-loop:
    do {
        if (P->color == BLACK) {
            // Case_I1 (P black):
            return;  // insertion complete
        }
        // From now on P is red.
        if ((G = P->parent) == NULL)
            goto Case_I4;  // P red and root
        // else: P red and G!=NULL.
        dir = childDir(P);  // the side of parent G on which node P is located
        U = G->child[1 - dir];              // uncle
        if (U == NIL || U->color == BLACK)  // considered black
            goto Case_I56;                  // P red && U black
                                            // Case_I2 (P+U red):
        P->color = BLACK;
        U->color = BLACK;
        G->color = RED;
        N = G;  // new current node
                // iterate 1 black level higher
                //   (= 2 tree levels)
    } while ((P = N->parent) != NULL);
    // end of the (do while)-loop

wikipedia的代码和Linux源码实现的代码架构不太一样
这里的代码将数据包含在节点类中，我们通过迭代找到需要插入位置的父节点，然后通过 dir来确定插入的方向，然后直接将 N接到 P的后面
同时设置 N的默认颜色为红色等

case 5 and 6

接下来我们进入case 5和6，首先我们已经确定P节点为红色，然后U节点为黑色，这样我们就不能通过染色解决问题，这样不能两边同时改变黑色节点数量（我们接下来称为Black height）

红黑树选择的解决方式如下：

• 首先我们需要保证 N节点和P节点都在同一方向，也就是说，如果N节点是 P节点的左子节点，那么 P节点就是 G节点的左子节点；如果 N节点是 P节点的右子节点，那么 P节点就是 G节点的右子节点

如果不能满足以上要求的话，进入case 5：

• 将 P节点按照自己所在的方向旋转，即，如果 P节点是左子节点， N节点是右子节点，那么将 P节点进行左旋，然后将旋转后的 P节点设置为新的 N节点

这样我们就构建出了一个case 6：

此时我们发现一个问题，旋转操作是会改变RBtree的Black Height的，简单列举几种情况即可发现这个问题
但是这里旋转的两个节点都是红色节点，所以对于Black Height并没有影响，但是对于case 6而言，我们就需要对黑色节点进行旋转了

• 我们将 G节点按照 P节点所在方向的反方向旋转，使得 P节点代替原本 G节点的位置，此时右子树的Black height增加1，左子树的Black Height减少1，为了维护role 4，我们将 G节点染为红色，P节点染为黑色，此时我们发现，role 3和role 4同时满足了

这么一来，插入的6种case就考虑完毕了，下面是case 5、6的代码部分：

if (N == P->child[1 - dir]) {  // Case_I5 (P red && U black && N inner
                               // grandchild of G):
    RotateDir(P, dir);         // P is never the root
    N = P;                     // new current node
    P = G->child[dir];         // new parent of N
                               // fall through to Case_I6
}
// Case_I6 (P red && U black && N outer grandchild of G):
RotateDirRoot(T, G, 1 - dir);  // G may be the root
P->color = BLACK;
G->color = RED;
return;  // insertion complete
         // end of RBinsert1

删除

删除操作的简单情况：

• 删除节点为根节点，直接删除即可
• 一个节点如果只有一个非NIL子节点，那么这个子节点一定是红色，如果是黑色，那么Role 4一定会被破坏，黑色子节点至少多贡献一个Black Height
• 这样的话，如果N是红色节点，那么它就不能只拥有一个节点，而是要么没有子节点，要么有两个黑色子节点
• 如果 N是黑色节点，那么它可以拥有一个红色子节点，或者没有子节点，或者两个黑色子节点

对于一个只有一个子节点的红色节点，由于一定没有子节点，所以我们可以直接删除这个节点

对于只有一个子节点的黑色节点，其子节点一定是红色，我们可以将其直接替换删除节点，然后将其染为黑色，从而满足Role 4

考虑了只有一个子节点和根节点的简单情况后，我们来考虑有两个子节点的情况：

• 如果一个节点同时拥有左右节点的话，我们可以寻找其前驱或者后继进行替换，然后将后继节点作为对象删除即可

前驱或后继节点一定是只有一个子节点，或者本身就是叶子节点，所以至此我们只剩下最后一种情况：
如果一个黑色节点没有子节点，我们将其删除后必然会破坏Role 4，此时需要进行删除后的红黑树维护

删除后的维护

删除后操作我们总共要关注5个节点的情况：
S、 N、P、C和 D节点

case 1

如果删除的黑色节点是一个新的根节点，那么直接删除即可

Case_D1 (P == NULL):
        return; // deletion complete

case 2

C和 D节点我们认为是 S节点的子节点
S节点是 N节点的兄弟节点，当 S节点和 P节点都是黑色，且C和 D节点也是黑色时，采取以下操作：

• 我们将 S节点染为红色，但是这样会使得经过S节点的路径Black Height减少，局部维护的同时破坏了整体的Role 4，所以我们把 P节点当做新的 N节点，继续进行删除后的维护

void RBdelete2(
  RBtree* T,         // -> red–black tree
  struct RBnode* N)  // -> node to be deleted
 {
  struct RBnode* P = N->parent;  // -> parent node of N
  byte dir;          // side of P on which N is located (∈ { LEFT, RIGHT })
  struct RBnode* S;  // -> sibling of N
  struct RBnode* C;  // -> close   nephew
  struct RBnode* D;  // -> distant nephew

  // P != NULL, since N is not the root.
  dir = childDir(N); // side of parent P on which the node N is located
  // Replace N at its parent P by NIL:
  P->child[dir] = NIL;
  goto Start_D;      // jump into the loop

  // start of the (do while)-loop:
  do {
    dir = childDir(N);   // side of parent P on which node N is located
Start_D:
    S = P->child[1-dir]; // sibling of N (has black height >= 1)
    D = S->child[1-dir]; // distant nephew
    C = S->child[  dir]; // close   nephew
    if (S->color == RED)
      goto Case_D3;                  // S red ===> P+C+D black
    // S is black:
    if (D != NIL && D->color == RED) // not considered black
      goto Case_D6;                  // D red && S black
    if (C != NIL && C->color == RED) // not considered black
      goto Case_D5;                  // C red && S+D black
    // Here both nephews are == NIL (first iteration) or black (later).
    if (P->color == RED)
      goto Case_D4;                  // P red && C+S+D black
    // Case_D2 (P+C+S+D black):
    S->color = RED;
    N = P; // new current node (maybe the root)
    // iterate 1 black level
    //   (= 1 tree level) higher
  } while ((P = N->parent) != NULL);
  // end of the (do while)-loop

来自Wikipedia的伪代码，有着详细的注释

case 3

若 S节点是红色节点，C和 D是黑色节点，进行以下操作：

• 将 P节点按 N节点的方向旋转，然后将 P节点染为红色，将 S节点染为黑色，此时的 S节点就变为了原来的 C节点（一定是黑色节点）

Case_D3: // S red && P+C+D black:
  RotateDirRoot(T,P,dir); // P may be the root
  P->color = RED;
  S->color = BLACK;
  S = C; // != NIL
  // now: P red && S black
  D = S->child[1-dir]; // distant nephew
  if (D != NIL && D->color == RED)
    goto Case_D6;      // D red && S black
  C = S->child[  dir]; // close   nephew
  if (C != NIL && C->color == RED)
    goto Case_D5;      // C red && S+D black
  // Otherwise C+D considered black.
  // fall through to Case_D4

这样一来，我们要考虑的case就变成了：N黑，P红，S黑
接下来我们要考虑的case就是 C和 D节点的不同情况：

case 4

如果 D和 C都是黑色，那么将 S染为红色，将 P染为黑色，这样相当于给右子树的Black height加一，直接完成了红黑树的维护

Case_D4: // P red && S+C+D black:
  S->color = RED;
  P->color = BLACK;
  return; // deletion complete

case 5

我们认为 C节点是左子节点，D节点是右子节点
如果 C节点为红色，不管 P节点是黑还是红，我们都可以直接执行下面的操作：

• 将 S节点和 C节点进行旋转，然后交换两者的颜色

Case_D5: // C red && S+D black:
  RotateDir(S,1-dir); // S is never the root
  S->color = RED;
  C->color = BLACK;
  D = S;
  S = C;
  // now: D red && S black
  // fall through to Case_D6

这么一来，红色就从 C节点转移到了 D节点的位置上，于是我们进入了最后的case 6

case 6

此时的 D节点是红色，不管 P节点是黑还是红，我们都可以直接执行下面的操作：

• 将 P和 S节点旋转，然后交换两者的颜色，并把 D节点染为黑色

Case_D6: // D red && S black:
  RotateDirRoot(T,P,dir); // P may be the root
  S->color = P->color;
  P->color = BLACK;
  D->color = BLACK;
  return; // deletion complete
} // end of RBdelete2

到此为止，基本的红黑树过程已经阐述完毕，我们下面总结一下红黑树的这些操作到底在干什么，问什么要这样干

旋转

首先要提及的就是旋转操作，旋转操作我们可以看作一个子节点（N）和一个父节点（P）交换位置

对于图中的三个框起来的子树部分，旋转操作的影响如下：

• N子树上的路径全部会多经过一个S点
• D子树上的路径全部会少经过一个 P点
• C子树上的路径不会有任何改变

结合起 P和 S这两个旋转对象的颜色，旋转操作可以在不改变BST性质的情况下改变 N子树和 D子树Black height，这是旋转操作在红黑树维护中扮演的角色

但是旋转会改变Black height，也有可能将红色的 C节点接到红色的 P节点上，所以一般旋转后还需要重新进行染色

于是我们重新来审视以下删除后的维护过程为什么要这么做：

首先可以直接处理完毕的case有：

• case 1： N节点是根节点，直接删除即可
• case 4： P节点是红色，其他四个节点都是黑色，那么只需要将 P节点染为黑色，S节点染为红色，删除 N节点即可
• case 6：当 N和 S 和 C是黑色，D是红色时，将 P和 S旋转，使得 N子树Black Height加一，而为了防止 P节点是黑色时导致 D子树的Black Height减一，我们将 S节点改为 P节点的颜色，此时相当于从右子树移动了一个黑色到左子树，为了保持平衡，我们将D节点也染为黑色，这样就使左子树的Black Height加一，在移除 N节点后，整棵树的Black Height不变

合理地使用旋转和染色可以用来操控子树的Black Height，另外的三种情况就是想办法把旋转操作的五个关键节点变成可以直接处理的情况

• case 2：这种情况的思路时让 P的右子树也集体Black height减一，然后就可以把 N子树减一的状态扩展到 P子树上，从而向上寻求一个可以直接处理的解
• case 3：这种情况的主要目的是将子节点的红色转移到父节点上，从而进入case4、5、6
• case 5：将红色节点从 C转移到 D上，从而进入case 6

为什么不能直接染色更改？
直接修改成红色可能打破role 3，所以通过旋转后，保证了修改节点的子节点一定是黑色，然后再修改颜色

到这里红黑树的基本思想已经介绍完成了

完全把这些情况和旋转、染色的意义理清楚还是花费了超出想象的篇幅，所以关于Linux源码的部分暂且就不再看了，其实现的原理都是基于红黑树罢