Red Black Tree 的一点感想

红黑树的基本性质

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

红黑树插入时，如果插入红色节点则：
（由于插入黑色节点一定会导致性质五被破坏，所以考虑插入为红色节点的情况）

1. 性质一不会破坏
2. 性质二可能破坏
3. 性质三不会被破坏
4. 性质四可能被破坏
5. 性质五不会被破坏

当插入导致性质被破坏时需要调整：
由上面所述，只有性质二和四可能被破坏，而性质二只有在插入之前为空树时可能被破坏。所以我们需要关注性质四，即插入导致两个红色节点连在了一起。下面分情况表述：

• **1.插入的节点为根节点：**若插入前无任何节点，则插入后的节点为根节点直接设置为黑色即可。
• **2.插入的节点的父节点为黑色节点：**无需做任何改变因为不会影响红黑树性质
• 3.插入的节点的父节点为红色且 uncle 节点也是红色： 此时将导致两个红色节点连接到了一起，此时我们考虑改变两个红色节点之中的一个，然而改变插入节点的颜色显然是无意义的，（如果改变相当于插入黑色节点），所以我们将插入节点的父节点设置为黑色，然而这样同时会导致性质五的违背，所以我们将其 uncle 节点也设置为黑色，并将 parent 的 parent 节点设置为红色，此时调整完成。插入节点为 M,如下图：
  
  （图片来源于网络）
• **4.插入节点的父节点为红色且 uncle 节点为黑色（T.nil 也为黑色），插入节点为右节点：**以插入节点的的父节点作为支点左旋变成情况 5，再调整
  
  （图片来源于网络）
• **5.插入节点父节点为红色，uncle 节点为黑色（T.nil 为黑色），插入节点为的左子节点：**将 parent 节点设置为黑色，parent 的 parent 节点设置为红色，并以 parent 节点为支点右旋。
  
  （图片来源于网络）
  删除节点：
  当我们删除一个节点时，z 指向删除节点，y 指向替换删除删除节点的节点，x 指向 y 的右子树，首先按照二叉搜索树的的删除方式进行删除，并在其中加入部分代码记录 Y 的踪迹和 y 的初始颜色，还有 x 的踪迹（见《算法导论》第三版 183 页）。
  删除节点的过程：当 z 只有一个子树时，y 指向该子树，并直接将子树 y 替换 z,当 z 有两个子树时选择右子树的最左侧节点作为 y，并用 y 替换 z，并用 x 替换 y,并进行 red-black tree 调整。
  所以实际过程相当于删除 Y

当 y 是红色时，删除后不会影响红黑树的基本性质，可直接删除

当如果 y 是黑色，会出现如下三种情况：
1.如果原先的 y 是根节点，y 的红色 x 替换 y 将导致违反性质 2
2.如果替换后 x 和 x 的父节点都为红色则违反性质 4
3.y 在树中移动将导致包含 y 的任何简单路径和高度减一。

所以我们需要对 y 为黑色节点时被 x 替换后的树进行调整。
由于懒得画图使用网络图片~~~~这时 N 上文所述的 x
1.如果 N 的兄弟节点为红色时
将 B 设置为黑色，N 的父节点 P 设置为红色，然后以 P 为中心左旋转，则转换情况 2

（图片来源于网络）

2.如果 N 的兄弟节点为黑色，并且两个子节点都为黑色（包括 T.nil）：
将 N 的兄弟节点 B 变红，然后用 N 的父节点 P 作为新的 N，进行递归操作。因为 N 是 P 的左子树，P 的左子树路径中，删除 N 后，会缺少一个黑色节点，因此递归的将右树上的路径也减少一个黑色节点，知道 N 的颜色为红色。最后把当前的 N 节点置为黑色。最后产生的结果就是将右侧的黑色节点上移，这样右子树和左子树都没有减少黑色节点。

（图片来源于网络）
3.如果 N 的兄弟节点 B 是黑色的他的左孩子为红色，右孩子为黑色
将 B 变红，b1 变黑，然后以 B 为中心右旋，则转换为情况 4

（图片来源于网络）
4.如果 N 的兄弟节点 B 是黑色他的右孩子为红色，左孩子可红可黑
将 B 的颜色设置为与 P 的颜色一致，然后 P 和 b2 设置为黑色，以 P 为中心左旋。

（图片来源于网络）
至此正文结束
分割线------------------------------------------------------------------------
花了我整整一下午加一晚上时间才看懂了此算法，并立刻跟新博客，也为以后如果忘记也是一个不错的复习资料，不过很开心今晚的迎新晚会很棒棒~~~~~~，不早了再不睡要猝死啦。。。。。