[理工] 資演 紅黑樹插入

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