<課本內容>
假設紅黑樹有 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)) 的紅黑樹

沒看到那行 抱歉這樣蠻有道理的