老师，红黑树为什么最坏情况下查找时2lgN呢？
来源：13-10 对于红黑树，任何不平衡都会在三次旋转内解决？
qq_湿腻焦糊_0
2018-09-15
写回答
1回答
-
因为一个有n个节点的红黑树，其高度最高为2log(n+1)的。
这个结论具体证明起来有些麻烦，可以用这个课程中介绍的红黑树和2-3树的等价性来近似理解：）
在2-3树中，一个有n个节点的2-3树，其高度是logn级别的。转化为红黑树，由于所有的3-节点都转换为了一个红节点接一个黑节点，所以最坏的情况，红黑树上最长的那条路径，是红黑相间的。黑色节点的个数即为原来2-3树的高度，为logn级别的，现在黑色节点中间都穿插了红色节点，所以，这条最长的路径，其长度，即红黑树的高度，是2logn级别的：）
加油！：）
012018-09-16
相似问题