性质

红黑树是一种含有红黑结点并能保持平衡的二叉查找树。它必须满足下面性质：

性质1：每个结点要么是黑色，要么是红色。

性质2：根结点是黑色。

性质3：每个空结点是黑色。

性质4：每个红色结点的两个子结点一定都是黑色。（黑结点的子结点则不一定）

性质5：从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

对结点的操作

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。

右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。

变色：结点的颜色由红变黑或由黑变红。

查找过程和二叉树一致

查找插入位置后，将插入的结点着色为红色，（不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。）

平衡：

使插入点后依旧满足性质，插入只可能改变性质性质2或4或5。

思路：将红色的节点移到根节点；然后，将根节点设为黑色，基于性质5.

所有的情况见图：

祖宗根节点必黑，允许黑连黑，不允许红连红；新增红色，爸叔通红就变色，爸红叔黑就旋转，那黑往那旋

删除其实是由简到繁，用替代结点代替删除结点，然后删除替代结点，后面的情况都会在过程中转换成前面的情况。也可以说是从树叶到树根的一步步替换。

0度点直接删除；

1度点删除后用子结点代替；

2度点删除后，用左子树最大结点（即最右）或右子树最小（即最左）结点代替；

替换后，因为删除结点之后，可能会违背红黑树的特性。所以需要通过旋转和变色来修正该树，使之重新成为一棵红黑树。

记删除结点的替换之前和替换之后的颜色为X，易得X只有“黑红”，“黑黑”两种情况，看看性质，只有删除黑色结点才能影响性质进入平衡模式，删除红色结点会不会影响性质，（只有删除红色的叶子节点这种情况）。一切从简，删除黑色结点后首先自我解决（看替代结点能否维持平衡），接着找兄弟借红变黑

具体情况如下（p为替代结点，可为空，此时为直接删除叶子结点）没说的都是不可能出现的情况。

一切从简，删除黑色结点后首先自我解决（看替代结点能否维持平衡），接着找兄弟借红变黑，再不行向上反应，直至根结点。判断的时候，先看待删除的节点的颜色，再看兄弟节点的颜色，再看侄子节点的颜色（侄子节点先看远侄子再看近侄子）远侄子红，近侄子无所谓，远侄子黑近侄子红，最后看父亲节点的颜色（重要性排序）。