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

看板Grad-ProbAsk作者 (交大小V)時間7年前 (2018/12/03 14:02), 7年前編輯推噓4(4推 0噓 7→)
留言11則, 3人參與, 7年前最新討論串1/1
如題。 今天讀一讀想到的。 我們知道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
推
12/03 15:11, 7年前 , 1F
從root算最長跟最短距離不超過2倍（證明的話洪逸說太
12/03 15:11, 1F
真的太感謝大大了！！！
→
12/03 15:11, 7年前 , 2F
複雜了）
12/03 15:11, 2F
推
12/03 15:14, 7年前 , 3F
12/03 15:14, 3F
推
12/03 16:19, 7年前 , 4F
如果你想深入了解紅黑樹的話，我會建議你去網路上找找設
12/03 16:19, 4F
→
12/03 16:19, 7年前 , 5F
計紅黑樹的 Robert Sedgewick 教授的影片，他在普林斯頓
12/03 16:19, 5F
→
12/03 16:19, 7年前 , 6F
演算法課中有簡略說明他當初設計的想法，看完之後你應該
12/03 16:19, 6F
→
12/03 16:19, 7年前 , 7F
可以更了解紅黑樹 "為什麼" 是那樣操作，懂原理之後對於
12/03 16:19, 7F
→
12/03 16:19, 7年前 , 8F
原本的問題應該自己想一下就通了
12/03 16:19, 8F
哈哈 沒很想在考前仔細理解 不過還是感謝大大 ※ 編輯: zaq851017 (140.113.136.218), 12/03/2018 16:38:25 ※ 編輯: zaq851017 (140.113.136.218), 12/03/2018 16:38:53
推
12/03 16:52, 7年前 , 9F
最短一定是全黑，最長一定是紅黑交錯，而從任節點開始
12/03 16:52, 9F
→
12/03 16:52, 7年前 , 10F
到子節點黑色數目相同，故最長最短黑色都一樣數目，而
12/03 16:52, 10F
→
12/03 16:52, 7年前 , 11F
黑紅交錯，紅色數量會跟黑色一樣多，所以不超過兩倍
12/03 16:52, 11F
‣ 更多 zaq851017 的文章
文章代碼(AID): #1S1CRk-c (Grad-ProbAsk)