红黑树的几个特征和性质：
1. 每个结点或者为黑色或者为红色。
2. 根结点为黑色。
3. 每个叶结点(实际上就是NULL指针)都是黑色的。
4. 如果一个结点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色结点）
。
5. 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。
然后我们可以得出几点推论：
1）加入两个兄弟同为黑色，那么他们可以将这个黑色上浮给先祖，知道根节点，而不违背红黑树的第5点
要求；
2）在对红黑树进行操作的时候，我们很有可能会遇见两个红节点相互相邻（即为父子的）冲突，解决办
法就是希望能把两父子转化成为兄弟；
我们可以保证开头的节点是黑色的，不然第二个节点就会和其开始冲突，这个问题是一个递归问题，前提
是第一个节点和第二个节点的冲突问题已经解决
情况1：节点2是节点1的左节点，节点3是节点2的左节点；
情况2：节点2是节点1的左节点，节点3是节点2的右节点；
情况3：节点2是节点1的右节点，节点3是节点2的右节点；
情况4：节点2是节点1的右节点，节点3是节点2的左节点；
上述四种情况是所有能出现的场景；
从上图我们也可看出，这个枝条已经失去平衡，我们可以采用旋转的方式把相邻的两个红节点转换为兄弟，并且我们不会该改变枝条的黑节点个数；
首先，我们来分析一些如何增加一个节点，
这里我们分为两部分：
1）如果新增加的节点之间没有冲突，那么，可以顺利的增加上去，也就是说，其父节点是黑色的；
2）如何新增加的节点之间存在冲突，也就是新节点和父节点都是红色的，那么我们应该解决这个矛盾；
我们分为两种情况来解决这个问题；
2.1）如果新节点的父亲和其父亲的兄弟都是红色的，也就是说三者都是红色的，我们可以这么解决；
因为这是在用递归的思想解决问题，所以如上图所示，z必定是已经和yu解决了冲突问题的节点，肯定是黑的；
2.2）如果只有新节点和其父亲是红色的，新节点的叔叔是黑色的，那么我们要分一下几种情况来讨论问题；
在这里，我们要涉及到旋转的问题，树节点的旋转有如下规律：
。能够通过旋转解决树的平衡问题；必选树的枝条过长；
。在红黑树中间，旋转的顶点的颜色我们一般不发生变化；
。旋转解决的问题是，旋转的三个节点每一个节点的位置都会向左或者右边旋转一位，使得父亲和儿子的角色发生改变，父亲，颜色发生交换，解决的问题是能够改变一个节点的颜色而且使得整个树的枝条的黑色节点的数目不发生变化；
我们见如下图片；
以上2和1的角色发生了转换，节点的颜色也发生了改变；
下面的四张图片分别解决了我们开始所描述的四种冲突情况；
这个时候我们又回到了1）的两个红节点问题，接下来，我们只要递归操作，我们会一直的将这个红色的矛盾一直推到树根，因为树根是所有枝条的起点，那么最后树根为红色，我们把这个红色变成黑色，那么所有的树枝的黑色节点都会加1，这也是为什么要把红色的冲突往根推的原因，因为这个红色的节点要把转化成为黑色的节点，并且保持所有树枝的黑色节点数目一样，那么这次由红色的转换就必须发生在一个影响所有树枝的地方，那么他就是树根；
然后，我们来说一下如何删除节点吧：
1）. 要删除的结点没有子结点。在这种情况下，我们直接将它删除就可以了。如果这个结点是根结点，那么这颗树将成为空树；否则，将它的父结点中相应的子结点指针赋值为NULL。
2）. 要删除的结点有一个子结点。与上面一样，直接将它删除。如果它是根结点，那么它的子结点变为根结点；否则，将它的父结点中相应的子结点指针赋值为被删除结点的子结点的指针。
3）. 要删除的结点有两个子结点。在这种情况下，我们先找到这个结点的后继结点（successor），也就是它的右子树中最小的那个结点。然后我们将这两个结点中的数据元素互换，之后删除这个后继结点。由于这个后继结点不可能有左子结点，因此删除该后继结点的操作必然会落入上面两种情况之一。
所以，我们只需几种精神解决第二种情况，第二种情况存在这几个矛盾的地方，如下：
注意，在树中被删除的结点并不一定是那个最初包含要删除的数据项的那个结点。但出于重建红黑树性质的目的，我们只关心最终被删除的那个结点。我们称这个结点为v，并称它的父结点为p(v)。 v的子结点中至少有一个为叶结点。如果v有一个非叶子结点，那么v在这颗树中的位置将被这个子结点取代；否则，它的位置将被一个叶结点取代。我们用u来表示二叉搜索树删除操作后在树中取代了v的位置的
那个结点。如果u是叶结点，那么我们可以确定它是黑色的。 如果v是红色的，那么删除操作就完成了－－－因为这种删除不会破坏红黑树的任何性质。所以，我们下面假定v是黑色的。删除了v之后，从根结点到v的所有子孙叶结点的路径将会比树中其它的从根结点到叶结点的路径拥有更少的黑色结点，这会破坏红黑树的性质5。另外，如果p(v)与u都是红色的，那么性质4也会遭到破坏。但实际上我们解决性质5遭到破坏的方案在不用作任何额外工作的情况下就可以同时解决性质4遭到破坏的问题，所以从现在开始我们将集中精力考虑性质5的问题。（引自http://sage.mc.yu.edu/kbeen/teaching/algorithms/resources/red-black-tree.html）
采用附加节点的方法，我们来看看
1）如果v是红色，直接结束删除操作；
2）v是黑色，如上图：
其中u有两个圈，说明，在root-p(v)-u然后早u的各个叶子节点，这些链是缺少一个黑节点的；
现在我们在2)中分成如下几种情况；
2.1)如果U是红色的，那么这个u只要转变成为黑色就可以完成了；
2.2)如果U是黑色的，那么我们要继续分几种情况；
|
|
|
|
|----2.2.1)u的兄弟和侄子都是黑色的；
| 
|
|
|
|这样，把y-z----到z的叶子节点的这些链条的黑色的节点数目也减少了一个，那么，我们就可以看做从树根---y--叶子节
|点的链条的黑节点数目都少一，这样，我们就可以把y上附加一个黑节点，然后，我们递归实现，如果y也是这样的话，最后
|出现的情况是我们回溯到树根节点，然后树根本来是黑色的，我们选择丢弃掉这个附加的黑节点，也就是我们把除了开始删
|除的那个黑节点到叶子节点的树枝以外，其他的树枝，我们都删除了他的一个黑节点，一致大家的黑节点数目一致；
|
|
|
|
|
|-------u的兄弟是红的，但是两个侄子是黑的；
|
|
|又回到了第一个讨论的了，递归；把y变成黑色即可，因为B肯定是黑色，不然会和x冲突；
|
|
|-----兄弟是黑的，侄子之中有一个红的；如下两种情况；
|
|
|
|
|
|
|
|
|从这里我们可以看出，其实是附加节点的兄弟哪边的树枝将一个黑的节点利用旋转的进位传给了附加节点，使得附加树枝，
|的黑节点被不起，然后其兄弟树枝哪边的一个红节点的侄子因为进位，变成了这个树枝的中与以前的附加节点平级的顶点
|，只要我们把这个红的节点，变成黑色，那么这边的黑色节点也没有缺少，但是，在旋转的时候，进位的三个节点必须是
|一条直线的，所以，如果是近侄子的话，那么，首先要旋转一次使得红节点在位置进行调整，而在第二次旋转的时候，红
|节点能成为第一个节点而使得y-----z----叶子节点的都能够收益；
|
|
|
|