作者RUOK5566 (烏綠微微)
看板Grad-ProbAsk
標題[理工] 紅黑樹高度的worst case ？
時間Sat Jan 18 04:36:04 2020
<課本內容>
假設紅黑樹有 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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1579293366.A.48B.html
1F：推 mi981027: 滿有道理的01/18 06:37
2F：推 hero97212: 2r和 2log(n+1)沒有直接的關係 所以2r<=2log(n+1)這個01/18 08:09
3F：→ hero97212: 假設不成立01/18 08:09
4F：→ mi981027: 沒有直接關係是什麼意思01/18 09:23
5F：→ hero97212: 比方說a<=b , a<=c01/18 10:43
6F：→ hero97212: 不只到b和c誰比較大 不能直接a<= b<= c01/18 10:45
7F：→ hero97212: *知道01/18 10:46
8F：→ mi981027: 2r <= 2log(n+1)是根據b得來的01/18 10:48
9F：推 mi981027: 當然寫<=不會出錯啦 但原po提的這個是更嚴格的upper bou01/18 10:51
10F：→ mi981027: nd 我覺得滿有道理的 也就是我們其實畫不出 h = 2 ceili01/18 10:51
11F：→ mi981027: ng (log(n+1)) 的紅黑樹01/18 10:51
12F：推 hero97212: 沒看到那行 抱歉01/18 11:00
13F：推 hero97212: 這樣蠻有道理的01/18 11:02
因為一直看到worst case是2log(n+1)的敘述
但是畫不出來，想說是不是我對紅黑樹的理解有問題
這樣看來課本想表達的重點應該是
->紅黑樹高度worst case的複雜度=O(log n)
感謝大家一起參與討論～
※ 編輯: RUOK5566 (220.142.74.15 臺灣), 01/18/2020 17:45:42