作者g2578141 (CJR)
看板Grad-ProbAsk
標題[理工] 資演 紅黑樹插入
時間Sun Apr 26 23:41:42 2020
各位安安
洪毅老師說紅黑樹的插入規則其中一項
Insert一個新值 在search過程中所經的Node若遇
兩子點皆紅需color change 和 連續紅色Nodes需要做rotation
然後這種情況每插入一次頂多發生一次
回家練習到有個例子 插入18做完後 接著插入2
search Node的過程中發生兩次cc的狀況
前面的步驟來回檢查也都有符合紅黑樹的定義
https://imgur.com/5YEylk4
是我誤會老師的意思嗎? 第一次發文 小弟不才請大大們幫我解答
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.242.143 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1587915708.A.170.html
※ 編輯: g2578141 (36.228.242.143 臺灣), 04/26/2020 23:46:16
1F：推 mi981027: color change本來就可能發生很多次 是rotation只會發生 04/28 05:24
2F：→ mi981027: 一次 04/28 05:24
3F：→ mi981027: 不過這邊要勸世一下 洪毅教的是紅黑樹的top down insert 04/28 05:24
4F：→ mi981027: , 其實很冷門 洪毅選擇這樣教的原因是比較好教 04/28 05:24
5F：→ mi981027: 但聖經本CLRS用的是bottom up insert，兩者有什麼差嗎？ 04/28 05:24
6F：→ mi981027: 有，印象中交大曾經考過一題紅黑樹 insert，用top down 04/28 05:24
7F：→ mi981027: 跟bottom up做出來的答案不一樣 而交大那年給的答案是 04/28 05:24
8F：→ mi981027: 用bottom up做出來的結果 04/28 05:24
9F：→ mi981027: 而且事實上大部分的學校都是用CLRS的定義，所以建議趁 04/28 05:24
10F：→ mi981027: 早把top down insert忘掉 網路上有很多紅黑樹insert的 04/28 05:24
11F：→ mi981027: 教學都不錯 可以參考看看 04/28 05:24
12F：→ mi981027: 事實上bottom up insert只需考慮uncle為紅 跟uncle為黑 04/28 05:24
13F：→ mi981027: 兩種情況 一點都沒有比較難 04/28 05:24
14F：→ g2578141: 原來如此！那我會在去查查bottom up的插入法 謝謝mi大 04/28 12:16
15F：→ g2578141: 的解釋 04/28 12:16
16F：推 zuchang: 以top down來講 20插入就好了 不用回頭檢查 04/29 16:34
17F：推 Handsomeshen: 可以去youtube找教學，有人畫例子會比較好懂 05/03 03:42