作者zaq851017 (交大小V)
看板Grad-ProbAsk
標題[理工] 資工 關於紅黑樹的平衡 跟 AVL高度平衡
時間Mon Dec 3 14:02:20 2018
如題。 今天讀一讀想到的。
我們知道AVL 的定義是 abs(Hl - Hr) <=1
就是左子樹高度和右子樹高度是差+-1以內的。
因為紅黑樹本身也是種平衡樹<課本所說> 這裡的平衡有詳細定義嗎?
因為我畫紅黑樹的過程中，Hl-Hr有=2的 我想問不知道紅黑樹的Hl-Hr有一個range範圍嗎?
感謝各位的觀看。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.136.218
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1543816942.A.FA6.html
1F：推 wei12f8158: 從root算最長跟最短距離不超過2倍（證明的話洪逸說太 12/03 15:11
真的太感謝大大了！！！
2F：→ wei12f8158: 複雜了） 12/03 15:11
4F：推 AliennC: 如果你想深入了解紅黑樹的話，我會建議你去網路上找找設 12/03 16:19
5F：→ AliennC: 計紅黑樹的 Robert Sedgewick 教授的影片，他在普林斯頓 12/03 16:19
6F：→ AliennC: 演算法課中有簡略說明他當初設計的想法，看完之後你應該 12/03 16:19
7F：→ AliennC: 可以更了解紅黑樹 "為什麼" 是那樣操作，懂原理之後對於 12/03 16:19
8F：→ AliennC: 原本的問題應該自己想一下就通了 12/03 16:19
哈哈 沒很想在考前仔細理解 不過還是感謝大大
※ 編輯: zaq851017 (140.113.136.218), 12/03/2018 16:38:25
※ 編輯: zaq851017 (140.113.136.218), 12/03/2018 16:38:53
9F：推 b0920075: 最短一定是全黑，最長一定是紅黑交錯，而從任節點開始 12/03 16:52
10F：→ b0920075: 到子節點黑色數目相同，故最長最短黑色都一樣數目，而 12/03 16:52
11F：→ b0920075: 黑紅交錯，紅色數量會跟黑色一樣多，所以不超過兩倍 12/03 16:52
12F：推 whatabiggun: 樓上大哥的解釋很有道理欸 08/03 19:54