[理工] 資工 關於紅黑樹的平衡 跟 AVL高度平衡

[zaq851017 (交大小V)]

如題。 今天讀一讀想到的。

我們知道AVL 的定義是 abs(Hl - Hr) <=1

就是左子樹高度和右子樹高度是差+-1以內的。

因為紅黑樹本身也是種平衡樹<課本所說> 這裡的平衡有詳細定義嗎?

因為我畫紅黑樹的過程中，Hl-Hr有=2的 我想問不知道紅黑樹的Hl-Hr有一個range範圍嗎?

感謝各位的觀看。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.136.218
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1543816942.A.FA6.html
推 wei12f8158: 從root算最長跟最短距離不超過2倍（證明的話洪逸說太
真的太感謝大大了！！！
→ wei12f8158: 複雜了）
推 wei12f8158:  https://i.imgur.com/zHCTIv8.jpg
推 AliennC: 如果你想深入了解紅黑樹的話，我會建議你去網路上找找設
→ AliennC: 計紅黑樹的 Robert Sedgewick 教授的影片，他在普林斯頓
→ AliennC: 演算法課中有簡略說明他當初設計的想法，看完之後你應該
→ AliennC: 可以更了解紅黑樹 "為什麼" 是那樣操作，懂原理之後對於
→ AliennC: 原本的問題應該自己想一下就通了
哈哈 沒很想在考前仔細理解 不過還是感謝大大
※ 編輯: zaq851017 (140.113.136.218), 12/03/2018 16:38:25
※ 編輯: zaq851017 (140.113.136.218), 12/03/2018 16:38:53
推 b0920075: 最短一定是全黑，最長一定是紅黑交錯，而從任節點開始
→ b0920075: 到子節點黑色數目相同，故最長最短黑色都一樣數目，而
→ b0920075: 黑紅交錯，紅色數量會跟黑色一樣多，所以不超過兩倍
推 whatabiggun: 樓上大哥的解釋很有道理欸