[理工] 紅黑樹高度的worst case ？

[RUOK5566 (烏綠微微)]

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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.142.74.15 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1579293366.A.48B.html
推 mi981027: 滿有道理的
推 hero97212: 2r和 2log(n+1)沒有直接的關係 所以2r<=2log(n+1)這個
→ hero97212: 假設不成立
→ mi981027: 沒有直接關係是什麼意思
→ hero97212: 比方說a<=b , a<=c
→ hero97212: 不只到b和c誰比較大 不能直接a<= b<= c
→ hero97212: *知道
→ mi981027: 2r <= 2log(n+1)是根據b得來的
推 mi981027: 當然寫<=不會出錯啦 但原po提的這個是更嚴格的upper bou
→ mi981027: nd 我覺得滿有道理的 也就是我們其實畫不出 h = 2 ceili
→ mi981027: ng (log(n+1)) 的紅黑樹
推 hero97212: 沒看到那行 抱歉
推 hero97212: 這樣蠻有道理的
因為一直看到worst case是2log(n+1)的敘述
但是畫不出來，想說是不是我對紅黑樹的理解有問題
這樣看來課本想表達的重點應該是
->紅黑樹高度worst case的複雜度=O(log n)
感謝大家一起參與討論～
※ 編輯: RUOK5566 (220.142.74.15 臺灣), 01/18/2020 17:45:42