红黑树 自觉找出一个反例 求解惑
红黑树规则：
性质1. 节点是红色或黑色。
性质2. 根是黑色。
性质3. 所有叶子都是黑色（包括NIL）。
性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
如上图：满足了红黑树的基本规则，但是两边的高度差为2，即非平衡。怎么解释呢？
红黑树
[解决办法]
AVL Tree 才保证绝对平衡。
任何结点的左右子树高度相差最多为1。
红黑树并不保证这点。
实际上这两种树的性能都不错
[解决办法]
红黑树本来就不保证平衡。。保证平衡的那是AVL树。。
[解决办法]
只要保证高度是O(logn)的都能叫平衡二叉树。
[解决办法]
红黑树本就不平衡，它只保证最小高度不会小于最大高度的一半。它牺牲了平衡性换来的是增删操作的简单性，每次增删最多只需要旋转三次，而不象AVL那样一直旋转到根。
如果一开始就准备好数据，此后不增不删只查询，任何各类的BST都一样，从有序随机访问序列构建一个绝对平衡的二叉树很容易。
如果数据是逐渐准备好的，但增删频率远远小于查询频率，AVL应该效果更好
如果数据的增删操作也比较多，RBT更加合适。
[解决办法]
推荐楼主实现一下跳表。
