红黑树的理解与编写（c++实现）

红黑树的理解与c++编写

基础性质

红黑树是一种二叉搜索树，并且相对于二叉搜索树做了一定的改进。
红黑树具有下列五种性质：

1. 根节点黑色。
2. 每个节点为红色/黑色。
3. 红色节点下两个节点必为黑色。
4. 每一条从根至叶的路径上的黑节点数量相同。
5. 每个叶节点都是黑的。

从五个性质可以得出的结论是，红黑树树内节点数n≥2h/2−1$n\ge 2^{h/2}-1$
证明省略，可以看CLRS第三版p174。

所以可以看出，红黑树相对于一个普通二叉树而言，对空间利用的更好。

红黑树操作

操作包括：

• Search
• Successor
• Predecessor
• Minimum
• Maximum
• Insert
• Delete
• InorderTreeWalk

红黑树操作不止于此，但是从最外层的“用户”角度来说，这些就足够了。然而这些外层操作需要调用的操作还有：
- LeftRotate
- RightRotate
- TransPlant
- InsertFixup
- DeleteFixup

其中左旋、右旋、两个Fixup算是红黑树的特色应用，用来保持红黑树的4性质。操作中Search、Successor等不涉及红黑树性质，只涉及节点值大小的操作与普通的二叉树并无二致，在此不表。

所以我主要集中在Insert和Delete两个函数上。这两个函数分别需要调用InsertFixup和DeleteFixup。

Insert操作

Insert函数事实上和普通二叉树的Insert也没有太多区别：
在不考虑节点具有相同值的情况下，从树根开始向下遍历，一直到一个NIL节点。（NIL节点代表一个空节点，可以作为根的父节点或者叶的子节点）然后将NIL节点替换为你的插入值。
但是加入对红黑树性质的考虑，因此我们有了InsertFixup。这个新节点的颜色被我们设置成红色，因为红色节点确保了性质4（每条路径上黑节点数目相同）的成立。所以引入一个红色节点，我们面临的问题可能是性质3（每个红色节点的子节点都是两个黑色节点）的挑战。如果性质3受到了挑战，我们就需要进入InsertFixup的步骤。而性质3受到挑战的先决条件是：新插入的节点的父节点是红色节点。在这样的情况下，两个红色节点连接在一起，红黑树受到了挑战。
那么在InsertFixup开始时，我们首先要记住的是只有性质3被违背时（也就是x.p是红色的），我们才需要不停fixup。这时候我们可以开始分类讨论。

将刚才插入的节点记为x。（每个节点具有p,left,right,color,key值）
最开始的时候需要明确的是除去x之外的整棵树具有完整的红黑树性质。基于这一点，以及x.p是红色的，易知x.p.p是黑色的。
首先我们的第一层假设是，x.p==x.p.p.left（记为uncle）。之所以做这个假设，是因为在InsertFixup当中，x的叔叔（在这个假设的前提下叔叔就是x.p.p.right）是非常重要的。
那么我们第二层假设是基于叔叔的颜色。如果uncle.color==red，我们就可以很轻松地解决x颜色与x.p之间红色碰撞的问题。因为uncle.color==x.p.color==red,所以x.p.p.color==black.（性质3）接下来把x.p.p设置为红色（原为黑色），把x.p和uncle设置成黑色（原为红色）。那么性质4显然是不变的；并且性质3对于x而言也得到了满足。然而，因为x.p.p的颜色改变了，他有可能违背了性质3。所以，我们需要把x更新成为x.p.p。
我们第三层假设（uncle此时已经是黑色的了），是x是x.p的左孩子还是右孩子。如果x是x.p的左孩子，我们可以交换x.p与x.p.p的颜色并且对x.p.p进行一次右旋来解决，并且此循环到此结束。然而，如果x为x.p的左孩子，我们没有可以直接解决的方法；但是，我们可以对x.p进行一次左旋，并且将x更新为原来的x.p，这样这种情况就会被归于x为x.p的左孩子的情况，由此迎刃而解。

重新回到第一层假设，如果x.p=x.p.p.right。这是一个镜像问题，只需要把左右操作左右对调即可。
最后，如果说你在操作变更过程中，不小心改变了根（root）的颜色，只需要在最后将root重置为黑色即可。

Delete操作

相比较于Insert，Delete与普通二叉搜索树的区别更大。Delete需要关注三个节点和一个颜色：即将删除的节点（记为toDelete)，即将对toDelete取而代之的节点（记为toReplace），即将对toReplace取而代之的节点（记为tRTR），以及toReplace原本的颜色（记为original_color，是我们需要考虑是否对红黑树的性质造成了影响的颜色）。
首先我们需要考虑toDelete是否同时具有左右孩子。如果它没有左孩子，那么删除时只需要将右孩子移植到toDelete原先的位置上即可。另一种情况同理。那么在这种情况下，original_color应该是toDelete原先的颜色（而不是toReplace的）。因为我们直接移植了其中的一个孩子给toDelete，相当于toDelete的颜色消失了；所以original_color在这里应该是toDelete原先的颜色。而tRTR应该就是toReplace。
如果toDelete同时具有左右孩子，我们取他的后继（Successor）作为toReplace，并将toReplace.right记为tRTR。将toReplace原先的颜色记为original_color,然后将toRelace取代toDelete，将tRTR移植到toReplace的位置，将toReplace的颜色设置成和toDelete一样（这样我们可以保证toReplace及以上红黑性质不变，问题集中于tRTR的位置）。
在DeleteFixup之前，我们先要确定一点：只有original_color==black时，我们才需要fixup。如果original_color==red，红黑性质不会改变。
所以进入到DeleteFixup之中，我们要记住，我们删除了一个黑色的节点。也就是说，从我们删掉黑色的节点的位置向下的所有路径的黑高都少了1，也就违反了性质4。为此，我们需要假设当前取代了toReplace位置的节点（也就是tRTR）具有一层额外的黑色。我们在DeleteFixup里的任务就是，把这层额外的黑色一直向上移，直到出现一个合适的红色节点，使得我们可以把这层黑色给他，让他变成一个黑色节点。
所以如果当前被我们fixup的节点是红色的，我们的任务就结束了。只要把当前处理的节点变成黑色即可。
首先，我们的设置一个x节点（初始值与tRTR相同，这个x具有我们所说额外的黑色并且本身也是黑色——这是一个大前提）。
我们的第一个假设是，x==x.p.left。这样子，我们需要关注x.p.right（记为brother）。
第二个假设是，brother是红色的。这时，通过将brother和x.p颜色互换，x不变，我们重新构造了原树；此时brother变成了黑色的。
那么第二个假设的第二种情况就是brother是黑色的。此时可以继续就brother的孩子继续分类。
那么这里我们开始第三层假设。第一种情况是brother有两个黑孩子。那么此时，brother如果变成红色，brother仍然可以满足性质3。所以我们把brother变成红色，将x变为x.p。这样子对于brother分支而言，尽管缺少了一个黑节点（brother），但是又多了一个黑节点（x具有额外的一层黑色）；对于x分支同样成立。
第二种情况是，brother右边是黑孩子，左边是红孩子。此时，通过交换brother和brother.left的颜色并且对brother进行一次右旋，可以把brother.right更新为原先brother.left的颜色（红色）。

第三种情况就是，brother右边是红孩子，而左边不再重要。这种情况下的操作很巧妙：将brother和x.p交换颜色，然后将brother.right设置为黑色，最后对brother进行左旋。

这种变换之后，在当前由ABCDE构成的小树种，A（x）的黑高增加了1，而其他两个叶子DE的黑高没有变化。所以是，合法的。

c++实现

redBlackTree
写的时候对于NIL的定义比较讲究，不能写在头文件里。原因我不是很清楚…