老师，红黑树为什么最坏情况下查找时2lgN呢？

Answer 1

liuyubobobo 2018-09-16 01:54:11

因为一个有n个节点的红黑树，其高度最高为2log(n+1)的。

这个结论具体证明起来有些麻烦，可以用这个课程中介绍的红黑树和2-3树的等价性来近似理解：）

在2-3树中，一个有n个节点的2-3树，其高度是logn级别的。转化为红黑树，由于所有的3-节点都转换为了一个红节点接一个黑节点，所以最坏的情况，红黑树上最长的那条路径，是红黑相间的。黑色节点的个数即为原来2-3树的高度，为logn级别的，现在黑色节点中间都穿插了红色节点，所以，这条最长的路径，其长度，即红黑树的高度，是2logn级别的：）

加油！：）

• 提问者 qq_湿腻焦糊_0 #1

  非常感谢bb老师！