红黑树的实现

      话不多说，先上代码，红黑树的c++实现见我的github：https://github.com/zk3326312/RB_Tree，下面开始介绍红黑树和它的插入删除节点的过程。

      红黑树相信学习过数据结构的朋友都不太陌生，c++中的stl里的map底层实现就是红黑树，红黑树说到底就是一颗特殊的二叉树，那么它相比普通的二叉树有什么特别之处呢？

      红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。具体来说，红黑树是满足如下条件的二叉查找树（binary search tree）：

       1.每个节点要么是红色，要么是黑色

       2.根节点必须是黑色

       3.红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）

       4.对于每个节点，从该点到叶节点（树尾端）的任何路径，都含有相同个数的黑色节点。

      满足这些条件有什么好处呢，先举个例子，如果你插入的数据为1,2,3,4,5，而1是最先插入的数据，那么你的二叉树就会成为下面的样子

                                         

你要查询5这个节点，你就需要进行5次比较操作，但如果你是红黑树，你的树形状就会如下图

       你就算最多也只用查询3次，这里是两次，那么为什么树会是这个样子呢，下面来讲一下红黑树的插入过程：根节点就不用说了，直接插入，并且颜色标记为黑，为了满足性质2，叶节点的插入比较麻烦，一个叶子节点插入的步骤如下：

       1.将该结点标记为红色的（标注为红色首先不管如何插入数据，都不会违反性质4，而如果标记为黑色，则会导致根结点到叶子结点的路径会多出一个黑结点，不容易进行调整）

       2.如果插入的新结点的父结点为黑色，满足所有条件。

       3.新结点的父结点为红色，因为性质3，所以树必然有祖父结点，则又包括以下的情况（这里红用R表示，黑用B表示）：

       a.父节点为R,叔叔节点为R

       b.父节点为R,叔叔节点为B，当前节点是右子

       c.父节点是R,叔叔节点是B，当前节点是左子

       处理方法：

        a.将父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，从新的当前节点开始算法。

        b.以当前节点的父节点作为新的当前节点，以新的当前节点左旋。

        c.父节点变为黑色，祖父节点变为红色，以祖父节点为支点右旋。

        红黑树的插入难点是插入之后的维稳，即成为一颗平衡的二叉树。

        红色节点需要有两个黑色子节点。

再来说说红黑树删除一个节点的过程：

        情况1：x的兄弟w是红色的。

        情况2：x的兄弟w是黑色的，且w的俩个孩子都是黑色的。

        情况3：x的兄弟w是黑色的，w的左孩子是红色，w的右孩子是黑色。

        情况4：x的兄弟w是黑色的，且w的右孩子时红色的。


针对情况1：改变w、p[z]颜色，再对p[x]做一次左旋，红黑性质得以继续保持。x的新兄弟new w是旋转之前w的某个孩子，为黑色。


针对情况2：因为w也是黑色的，所以x和w中得去掉一黑色，最后，w变为红。
p[x]为新结点x，赋给x，x<-p[x]。


针对情况3：交换w和和其左孩子left[w]的颜色。 即上图的D、C颜色互换。:D
并对w进行右旋，而红黑性质仍然得以保持。
现在x的新兄弟w是一个有红色右孩子的黑结点，于是将情况3转化为情况4.


针对情况4：做颜色修改，并对p[x]做一次旋转，可以去掉x的额外黑色，来把x变成单独的黑色，此举不破坏红黑性质。将x置为根后，循环结束。