概念
红黑树不仅是二叉搜索树，且必须满足以下5条平衡规则：
1）每个结点或是红色，或是是黑色。 2）根结点是黑的。 3）所有的叶结点(NULL)是黑色的。（NULL被视为一个哨兵结点，所有应该指向NULL的指针，都看成指向了NULL结点。） 4）如果一个结点是红色的，则它的两个儿子节点都是黑色的。 5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
简单的记法就是：红黑 黑 黑 红黑黑 黑
黑高度的定义： 从某个结点出发(不包括该结点)到达一个叶结点的任意一条路径上，黑色结点的个数成为该结点x的黑高度。红黑树的黑高度定义为其根结点的黑高度
红黑树是真正的在实际中得到大量应用的复杂数据结构：C++STL中的关联容器map,set都是红黑树的应用（所以标准库容器的效率太好了，能用标准库容器尽量使用标准库容器）；Linux内核中的用户态地址空间管理也使用了红黑树
插入和删除
插入的节点为红
操作是一定会破坏五条规则中的某些的，之后会进行修复．比起破坏（５），可以破坏（２）（４）
循环的每次迭代两种结果：要么指针z沿着树上移，要么执行某些旋转然后循环结束
为了维持插入、或删除结点后的树，仍然是一颗红黑树，所以有必要对树的结构做部分调整，从而恢复红黑树的原本性质。
而为了恢复红黑性质而作的动作包括：
结点颜色的改变(重新着色)，和结点的调整。
这部分结点调整工作，改变指针结构，即是通过左旋或右旋而达到目的。
从而使插入、或删除结点的树重新成为一颗新的红黑树。
插入的三种情况
删除的四种情况
在二叉搜索树的删除中，分三种情况
- 删除节点为叶子节点．直接删除
- 删除节点有一个孩子．直接删除并替换
- 删除节点有两个孩子．找到中序后继节点，和删除节点交换值，然后转为情况1/2
在中序后继节点为黑色时，进行修复．因为
- 树中各节点的黑高度会变化
判断类型的时候，先看待删除的节点的颜色，再看兄弟节点的颜色，再看侄子节点的颜色（侄子节点先看远侄子再看近侄子），最后看父亲节点的颜色
具体：被删除节点为黑色，兄弟节点为红色，侄子节点为红色（远侄或近侄） 被删除节点为黑色，兄弟节点为黑色，父节点（黑或红），若为黑，则要上溯
尽量要把对黑高度的影响，控制在子树内，实在不行，再进行兄弟树和父节点的查看
规则5的限制，会要求黑色节点之后要么为nil, 要么为红色节点（然后nil）
在左子树的黑高度-1之后，最好的情况是右子树有红色节点，父节点为黑，直接旋转就好了．否则，不仅旋转，还要考虑变色
左旋代码
分三步．全面考虑两个对象各自的三个指针parent/left/right，考虑空指针的情况
- 关注x和y.left
- 关注y和x.parent
- 关注x和y