红黑树是一颗二叉树，它在每个节点上增加了一个存储位来表示节点的眼色，可以是 RED或者BLACK。通过对任何一条从根到叶子的简单路径上各个节点颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因而是近似于平衡。
一颗红黑树是满足下面红黑性质的二叉搜索树：

  1. 每个节点不是红色就是黑色。
  2. 根节点是黑色的
  3. 每个叶节点是黑色的
  4. 如果一个节点是红色的，则它的两个子节点都是黑色的
  5. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点、

    注意：以上性质是根据《算法导论（第三版）》中红黑树部分的定义

哨兵(sentinel)是一个哑对象其作用是简化边界条件的处理 在红黑树中表示为Tree->nil 是一个颜色为黑色的空节点

旋转

当对树进行插入或者出操作时，得到的新的树很有可能违反 红黑树的五条性质，因此需要通过改变树中的某些节点的颜色以及指针结构来维护红黑树的性质。

红黑树的旋转一共有两种：左旋和右旋。

左旋

当在某个节点 X上做左旋时，假设它的右孩子是Y 而不是NULL节点，X可以为其右孩子不为NULL 节点的树内任意节点。左旋以X到Y的链为’支轴’进行，它使Y称为X的父节点，X称为Y的左孩子，Y的左孩子称为X的右孩子。
r1.pngr2.png
伪代码表示为：

  1. ROTATE_LEFT (Tree,x);  // Tree整颗树指针 x 表示当前上图旋转节点X 
  2.   // 第一步取出 x的右孩子 Y
  3.   y = x->rightChild
  4.   // 将y的 左孩子赋值给x节点的右孩子
  5.   x->rightChild = y->leftChild
  6.   // 如果y的左孩子不为NULL节点  则将X节点设置为其父节点
  7.   if(y->leftChild!=Tree->nil)
  8.     y->leftChild->parent = x;
  10.    //将 x的父节点赋值给y的父节点
  11.    y->parent = x->parent;
  14.   if(x->parent==Tree->nil) // 说明是根节点
  15.     Tree->root  = y;
  16.   else if(x==x->parent->leftChild) //说明x 节点是其父节点的左孩子  将y替换到x的位置
  17.     x->parent->leftChild= y;
  18.   else//则x 节点是其父节点的右孩子 将y替换到x的位置
  19.     x->parent->rightChild = y;
  22.    // 将x 设置为y的左孩子
  23.    y->leftChild = x;
  24.    //将x的父节点指向 y
  25.    x->parent  = y;

右旋 （和左旋是对称的）

当在某个节点 X上做右旋时，假设它的左孩子为Y。X节点可以为其左孩子不为NULL的树中的任意节点。它使Y称为X的父节点，X称为Y的右孩子，Y的右孩子称为X的左孩子。
r3.png

  1. ROTATE_RIGHT (Tree,x);  // Tree整颗树指针 x 表示当前上图旋转节点X 
  2.   // 获取x节点的左孩子Y节点
  3.   y = x->leftChild;
  4.   // 将 y的右孩子设置为x的左孩子
  5.   x->leftChild = y->rightChild;
  6.   if(y->rightChild!=Tree->nil)
  7.     y->rightChild->parent = x; 
  9.   //将 x的父节点赋值给y的父节点
  10.   y->parent = x->parent;
  12.   if(x->parent==Tree->nil) // 根节点
  13.     Tree->root = y;
  14.   else if (x==x->parent->leftChild) // 说明x是其父节点的左孩子 将y设置为其父节点的左孩子
  15.       x->parent->leftChild = y;
  16.   else // 否则x是其父节点的右孩子 将y设置为其父节点的右孩子
  17.       x->parent->rightChild = y;    
  19.    // 将x 设置为 y的右孩子
  20.    y->rightChild = x;
  22.    // 将x的父节点指向y
  23.    x->parent = y

插入

将一个新节点n插入树T内，就像T是一颗普通的二叉搜索树一样，然后再将n着色为红色。为保持红黑树的性质。再调用一个辅助程序RB-INSERT-FIXUP 来对节点进行重新着色并旋转。

为什么新节点的颜色初始化为红色：因为如果我们将新节点设置为黑色，那我们将违反作为红黑树的第五条性质。 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点、 因为从根节点到其后代叶节点的路径，新节点n都比其他叶节点多一个黑色节点

当一个新节点n被插入并着色为红色后，要确定红黑性质有哪些不能继续保持。使调用RB-INSERT-FIXUP保持红黑性质
RB-INSERT-FIXUP 伪代码 在实际写代码的时候 还需注意父节点和子节点为空指针的问题

  1. RB-INSERT-FIXUP（Tree,node）// Tree 为 红黑树  node 为插入的新节点 
  3. while(node->parent->color==RED)
  5.   if(node->parent==node->parent->parent->leftChild)
  6.     y = node->parent->parent->rightChild
  7.     if(y->color==RED)
  8.       node->parent->color = BLACK;
  9.       y->color = BLACK;
  10.       node->parent->parent->color = RED;
  11.       node = node->parent->parent;
  12.     else if node==node->parent->rightChild
  13.         node = node->parent;
  14.         ROTATE_LEFT(Tree,node) //对其父节点进行左旋
  16.     node->parent->color = BLACK;
  17.     node->parent->parent = RED;
  18.     ROTATE_RIGHT(Tree,node->parent->parent)
  20.   else
  21.         // 和上面代码差不多 只需交换 left 和right
  24. Tree->root->color = BLACK;

循环的过程：
初始化循环: 在循环的第一次迭代之前 都是从一颗正常的符合红黑性质的红黑树开始的。 并新增了一颗红节点 node。
要证明RB-INSERT-FIXUP被调用时，不变式的每个部分都成立。

  1. 当调用RB-INSERT-FIXUP 时 ，node 是新增的红节点
  2. 如果node->parent 是根节点，那么node->parent开始时黑色的，并且在调用RB-INSERT-FIXUP之前保持不变。
  3. 注意到在调用RB-INSERT-FIXUP时：性质1 ，性质3和性质5 成立
    1.      1. 性质1 **每个节点不是红色就是黑色，** 着色是的只有这两种颜色，是满足的
    2.      1. 性质3 **每个叶节点是黑色的 ** 因为所有的叶节点都是黑色的哨兵节点
    3.      1. 性质5 **对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点、**因为初始化新节点为红色，在上文中也有解释。

如果违反了性质2 则红色根节点一定是新增节点node;它是树中惟一的内部节点。因为node 节点和两个子节点都是黑色的哨兵节点，没有违反性质4，这样对性质2的违反就是整棵树中的唯一违反红黑性质的地方
如果违反了性质4 则由于node 子节点都是黑色哨兵，并且该树在node节点加入之前没有其他性质的违反，所以违反必然是因为node节点和node->parent节点都是红色。而且没有违反其他红黑性质被违反。

循环的终止：
循环终止是因为node->parent为黑色的。(如果node是根节点，则node->parent 是黑色的哨兵节点)，这样树在循环终止是就没有违反性质4，根据初始循环不变式的c条件中来说。此时唯一可能违反的只有性质2，但是在 RB-INSERT-FIXUP最后一行，恢复了这个性质，所以在RB-INSERT-FIXUP结束时，所有红黑树的性质都成立。

保持循环：
实际在while的循环中的6中情况，其中三种和另外三种是对称的。这取决于node ->parent 是其node->parent->parent的左孩子还是右孩子。根据不变式的b部分，如果node->parent是根节点那么node->parent是黑色的，可知节点node-parent->parent存在。因为只有在node->parent 是红色节点是才进入循环迭代。所以node->parent 不可能是根节点，因此node-parent->parent存在。
下列三种情况的区别在于node->parent的兄弟节点的颜色不同。
在上述的伪代码的第四行中 y 指向 node->parent->parent->rightChild; 在第5行测试 y节点的颜色，如果y是红色的，那么执行情况1。否则将控制转向情况2和情况3.
在所有三种情况中node的祖父 node->parent->parent节点是黑色的，因为它的父节点node->parent 是红色的。所以性质4只在node 和node->parent 被破坏了。

情况1：node 的叔叔节点y 是红色的。

下图展示了情况1的情形：这种情况在node->parent 和y节点都是红色时发生。因为 node->parent->parent是黑色的（因为 node->parent是红色的，node->parent->parent就不可能是红色的）。所以将node->parent和y 都标记为黑色，将node->parent->parent 标记红色保持性质5，然后把node->parent->parent最为新节点node 重复循环
i1.png

情况2：node 的叔叔节点y是黑色的且node 节点是一个右孩子

情况3：node 的叔叔节点y是黑色的且node 节点是一个左孩子

在情况2和情况3中,node 的叔叔节点y是黑色的，通过node 是node->parent的左孩子还是右孩子来区别这两种情况。在情况2中 节点node是他父节点的右孩子，可以使用左旋将此情况转变为情况3，此时节点node 为左孩子（如下图所示）。因为node和node->parent都是红色，所以旋转对节点的黑高和性质5无影响。无论是进入情况2，还是通过情况3进入情况2,node的叔叔节点y总是黑色的，否则就好执行情况1.
在情况3中改变某些节点的颜色并做一次右旋，以保持性质5，这样由于在一行中不再有两个红色节点。所有处理到此完成。因此此时node->parent是黑色的。所以无需再次执行while循环。

i2.png

删除

红黑树的删除和二叉树的类似，只是到了最后判断删除节点之后是否破坏了树想红黑性质

下列伪代码用于将nodeChild 节点交换到node的位置上 在删除过程中有用

  1. RB-TRANSPLANT(Tree,node,nodeChild); // Tree表示红黑树 node 表示交换的节点，nodeChild表示交换的另一个节点 通常是node的子节点，但也可以不是
  2. if node->parent==Tree->nil
  3.   Tree->root = nodeChild
  4. else if node == node->parent->left
  5.     node->parent->left = nodeChild
  6. else
  7.     node->parent->right = nodeChild
  9. nodeChild->parent = node->parent

删除操作伪代码

  1. RB-DELETE(Tree,node) // Tree表示树，node 当前删除的节点
  2. y = node; // 使用变量y 保存node 
  3. y_original_color = y->color; // 存储发生改变前的节点颜色
  5. if node->left==Tree->nil  // node 的左节点为哨兵节点则取 右节点的值
  6.   x = node->right;
  7.   RB-TRANSPLANT(Tree,node,node->right);
  8. else if node->right==Tree->nil // node 的右节点为哨兵节点则取 左右节点的值
  9.     x = node->left;
  10.     RB-TRANSPLANT(Tree,node,node->left);
  11. else
  12.     y = getMinNode(node->right);
  13.     y_original_color = y->color;
  14.     x = y->right
  15.     if y->parent==node
  16.       x->parent=y;
  17.     else 
  18.       RB-TRANSPLANT(Tree,y,y->right)
  19.       y->right = node->right
  20.       y->right->parent = y;
  22.       RB-TRANSPLANT(Tree,node,y) // 将 y 替换到node 位置
  23.       y->left = node->left;
  24.       y->left->parent = y;
  25.       y->color = node->color;
  26. //当删除的节点为黑色时，才需要 RB-DELETE-FIXUP 恢复红黑树性质，至于原因下面会提到
  27. if y_original_color==BLACK
  28.    RB-DELETE-FIXUP(T,x);

当被删除的节点是红色时，红黑树的性质仍然保持

  1. 树种的黑高并没有变化
  2. 如果删除的节点是红色 则其不可能是根节点 所以根节点仍然是黑色
  3. 不存在两个相邻的红节点，因为在y在树种占据了node的位置，在考虑到node的颜色。树中y的新位置不可能有两个相邻的红节点（因为我们会把node的颜色给y）。另外如果y不是node的右孩子，则y的原右孩子x代替y，如果y是红色的，x一定是黑色的。因此x代替y不可能使两个红节点相邻

如果被删除的节点y是黑色的，则会产生三个问题，可以通过调用 RB-DELETE-FIXUP 进行补救

  1. 如果y是原来的根节点，而y的一个红色的孩子称为新的根节点，这就违反了性质2
  2. 如果x和x->parent是红色的。则违反了性质4

  3. 在树中移动y将导致先前包含y的任何简单路径的黑节点都少1，因此y的任何祖先都不满足性质5

    RB-DELETE-FIXUP 修复函数 ```basic RB-DELETE-FIXUP(Tree,node) //

while node!=Tree->root && node->color==Black if node===node->parent->left // 是其父节点的左子树 brother = node->parent->right // node的兄弟节点 if brother->color ==RED brother->color = BLACK; node->parent = RED; ROTATE_LEFT(Tree,node->parent); brother = node->parent->right; if brother->left->color==BLACK&&brother->right->color==BLACK brother->color = RED node = node->parent else if brother->right=>color==BLACK brother->left->color = BLACK; brother->color = RED; ROTATE_RIGHT(Tree,brother); brother = node->parent->right;

  1. brother->color = node->parent->color;
  2. node->parent-color = BLACK;
  3. brother->right->color = BLACK;
  4. ROTATE_LEFT(Tree,node->parent);      
  7. node = Tree->root;

else // 这里对应代码是 其兄弟节点是其父节点的右子树 代码和上面差不多，只需right 换为left

x->color = BLACK;

``` 在 RB-DELETE-FIXUP函数中对于确认其兄弟节点之后，只需要判断四种情况，不过要根据是左子树孩子右子树来决定左旋还是右旋。

情况1 node 的兄弟节点 brother 是红色的

因为brother必须有黑色子节点，所以改变brother和node->parent的颜色，然后对node->parent 做一次左旋而不违反红黑树的任何性质。现在，node 的新兄弟节点是旋转之前brother的某个子节点。其颜色为黑色，这就将情况1转换为情况2,3,4处理。如下图：
rd1.png

情况2 node的兄弟节点brother是黑色的，而且brother的两个子节点都是黑色的

brother的两个子节点都是黑色的。因为brother也是黑色的，所以从node 和 brother 上去掉一个黑色
变为node 为黑色 brother为红色，为了补偿从 node 和 brother中去掉的黑色，在原来是红色或者黑色的node->parent上新增一个额外的黑色。通过将node->parent作为node来重复循环
rd2.png

情况3 node的兄弟节点brother是黑色的，brother的左孩子是红色的，而brother的右孩子是黑色的

当brother为黑色且其左孩子为红色，右孩子为黑色时。可以交换brother 和其brother->left的颜色，然后对brother进行右旋而不违反任何性质。现在node的新节点brother是一个有红色右孩子的黑色节点。这样将情况3转换成了情况4
rd3.png

情况4 node的兄弟节点brother是黑色的，而brother的右孩子是红色的

当在这种情况时:通过进行某些颜色修改并对node->parent做一次左旋。将node 设置为根后循环终止
rd4.png