红黑树

正常的二叉树，在添加或者删除一个节点的时候，整个二叉树的结构会发生变更，会导致某些查找路径变的很长（深度），比如说下面这样的，

不平衡的树结构

红黑二叉树在普通二叉树的基础上有设定了一些基本的规则

• 节点是红色或者黑色；
• 根节点是黑色；
• 所有的叶子（NIL节点）都是黑色；
• 每个红色节点都必须有两个黑色子节点；（每个叶子到跟的所有路径上不能有两个连续的红色节点）
• 从任意一个节点到其每个叶子的所有简单路径都包含相同数目的黑色节点；

如果在添加删除节点的过程中生成的新的树不满足上述的基本规则，就需要通过一些方法对二叉树进行调整，以使得它能满足红黑树的基本要求，

• 左旋转；
• 右旋转；
• 重新着色；

当二叉树重新满足红黑树的基本规则以后，这个二叉树又恢复了平衡的状态，就如同下面这张图上一样，

平衡的树结构

所以红黑树的高度会一直维持在O(log(n))，n是节点的个数，可以极大降低查找算法的复杂度。

关于定理的证明以及红黑二叉树的插入删除操作网上有很多例子，就不赘述了；后面有个链接是演示红黑树的插入删除操作，以及在这个过程中怎么做到自平衡的过程，有助于理解红黑树存在的原因。

REF
wiki: 红黑树
Red-Black Tree visulization