红黑树

 问题：

　　能否进一步提高，比如总体O（n+h）、单版本O(1)？ 答案是可以！！

相邻的版本之间的差异不能超过O（1）,显然AVL树的删除操作不能满足这一点，因为当每次删除一个节点后，有可能自底而上，逐层引发多大logN次的旋转。

所以要用到红黑树：

　红黑树所具有的规则：

 对红色节点做一次提升变换：

　　底层节点：

在经过提升之后：

 原来提升之后的红黑树就是4阶B树啊！！！

 红黑树接口定义：　　

红黑树的动态调整算法：

　　插入：

双红修正算法：

　　第一种情况：叔父节点u是黑色的

　第二种情况：叔父节点u是红色的

 需要在出现问题的节点中，找到居中的那个关键码，并且以他为界，将原先的大节点分为左右两个新的节点。居中分界的关键码，将被取出上移插入父节点的位置中。

红黑树

原文：https://www.cnblogs.com/ccpang/p/11617529.html