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

看板Grad-ProbAsk作者 (烏綠微微)時間4年前 (2020/01/18 04:36), 4年前編輯推噓5(5推 0噓 8→)
留言13則, 2人參與, 4年前最新討論串1/1
<課本內容> 假設紅黑樹有 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
推
01/18 06:37, 4年前 , 1F
滿有道理的
01/18 06:37, 1F
推
01/18 08:09, 4年前 , 2F
2r和 2log(n+1)沒有直接的關係 所以2r<=2log(n+1)這個
01/18 08:09, 2F
→
01/18 08:09, 4年前 , 3F
假設不成立
01/18 08:09, 3F
→
01/18 09:23, 4年前 , 4F
沒有直接關係是什麼意思
01/18 09:23, 4F
→
01/18 10:43, 4年前 , 5F
比方說a<=b , a<=c
01/18 10:43, 5F
→
01/18 10:45, 4年前 , 6F
不只到b和c誰比較大 不能直接a<= b<= c
01/18 10:45, 6F
→
01/18 10:46, 4年前 , 7F
*知道
01/18 10:46, 7F
→
01/18 10:48, 4年前 , 8F
2r <= 2log(n+1)是根據b得來的
01/18 10:48, 8F
推
01/18 10:51, 4年前 , 9F
當然寫<=不會出錯啦 但原po提的這個是更嚴格的upper bou
01/18 10:51, 9F
→
01/18 10:51, 4年前 , 10F
nd 我覺得滿有道理的 也就是我們其實畫不出 h = 2 ceili
01/18 10:51, 10F
→
01/18 10:51, 4年前 , 11F
ng (log(n+1)) 的紅黑樹
01/18 10:51, 11F
推
01/18 11:00, 4年前 , 12F
沒看到那行 抱歉
01/18 11:00, 12F
推
01/18 11:02, 4年前 , 13F
這樣蠻有道理的
01/18 11:02, 13F
因為一直看到worst case是2log(n+1)的敘述 但是畫不出來，想說是不是我對紅黑樹的理解有問題 這樣看來課本想表達的重點應該是 ->紅黑樹高度worst case的複雜度=O(log n) 感謝大家一起參與討論～ ※ 編輯: RUOK5566 (220.142.74.15 臺灣), 01/18/2020 17:45:42
‣ 更多 RUOK5566 的文章
文章代碼(AID): #1U8XgsIB (Grad-ProbAsk)