<课本内容>
假设红黑树有 n 个内部节点，
每条路径有 r 个black nodes，
则其高度h >= 2log[2] (n+1)
h的worst case为2log[2] (n+1)
《课本证明》
（a) h <= 2r
（b) n >= 2^r-1 即 r <= log[2] (n+1)
故得证 h <= 2log[2] (n+1)
<疑问>
但是h <= 2r <= 2log[2] (n+1)
I. 前面的h=2r成立时
代表最长路径红黑相间
II. 后面的2r = 2log[2] (n+1)成立时
代表n个节点都是黑色的
所以I & II 不会同时成立
是不是应该写成 h < 2log[2] (n+1) ？

满有道理的

2r和 2log(n+1)没有直接的关系 所以2r<=2log(n+1)这个假设不成立

没有直接关系是什么意思

比方说a<=b , a<=c不只到b和c谁比较大 不能直接a<= b<= c*知道

2r <= 2log(n+1)是根据b得来的当然写<=不会出错啦 但原po提的这个是更严格的upper bound 我觉得满有道理的 也就是我们其实画不出 h = 2 ceiling (log(n+1)) 的红黑树

没看到那行 抱歉这样蛮有道理的