[理工] [資結] 紅黑樹

看板Grad-ProbAsk作者 (bear)時間8年前 (2017/01/31 14:27), 8年前編輯推噓16(16推 0噓 14→)
留言30則, 15人參與, 最新討論串2/2 (看更多)
http://i.imgur.com/PfzKqbe.jpg
http://i.imgur.com/75D0EAC.jpg
請問一下這題紅黑樹 我和我同學建的不太一樣 但是以紅黑樹的定義似乎兩者都符合欸 所以紅黑樹會唯一嗎@@ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.232.144 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485844064.A.CC6.html ※ 編輯: beargg0305 (223.136.232.144), 01/31/2017 14:30:16 ※ 編輯: beargg0305 (223.136.232.144), 01/31/2017 14:30:36
推
01/31 14:34, , 1F
紅黑樹不唯一，左邊那個是原文書的版本，右邊那個是
01/31 14:34, 1F
→
01/31 14:35, , 2F
洪逸的版本，看你想用哪一個
01/31 14:35, 2F
→
01/31 14:35, , 3F
滿足他的特性就好了
01/31 14:35, 3F
→
01/31 14:37, , 4F
visiualization網站模擬出來也是左邊的版本
01/31 14:37, 4F
→
01/31 17:09, , 5F
建議照原文書 才會跟老師標準解答一樣
01/31 17:09, 5F
推
01/31 17:26, , 6F
左邊一定對
01/31 17:26, 6F
推
01/31 18:48, , 7F
我也是畫左邊
01/31 18:48, 7F
推
01/31 18:54, , 8F
右邊的錯在於30雖然左右子點都是紅 可是已結束
01/31 18:54, 8F
→
01/31 18:54, , 9F
不用color change
01/31 18:54, 9F
→
01/31 18:55, , 10F
除非還有再一個點增加會經過30才需要color change
01/31 18:55, 10F
→
01/31 20:24, , 11F
回樓上 我不覺得右邊有錯 應該都可以
01/31 20:24, 11F
推
01/31 20:40, , 12F
右邊+1
01/31 20:40, 12F
推
01/31 21:47, , 13F
只要最後插入的是紅點基本上我覺得右邊也不能說錯
01/31 21:47, 13F
→
01/31 23:56, , 14F
依插入的順序來看 會畫出右邊
01/31 23:56, 14F
推
02/01 00:38, , 15F
左邊+1 回去翻筆記發現洪逸有多一次換色 不過原因忘了.
02/01 00:38, 15F
推
02/01 02:24, , 16F
右邊按照定義沒錯, 可是畢竟考試, 老師手改依照原文書標準
02/01 02:24, 16F
→
02/01 02:25, , 17F
寫成右邊被改錯的可能性很高就是了...
02/01 02:25, 17F
→
02/01 07:32, , 18F
洪逸多一次換色的原因應該是他在搜尋的過程中遇到就換
02/01 07:32, 18F
→
02/01 07:33, , 19F
色，遇到某點有兩個紅子點就換，沒記錯的話是這樣
02/01 07:33, 19F
→
02/01 07:53, , 20F
----------------左邊6票，右邊2票-------------------
02/01 07:53, 20F
推
02/01 09:44, , 21F
左邊+1
02/01 09:44, 21F
推
02/01 11:12, , 22F
洪逸版本右邊+1
02/01 11:12, 22F
→
02/01 11:56, , 23F
左邊+1 照聖經版畫法肯定不會錯
02/01 11:56, 23F
推
02/02 11:10, , 24F
左邊+1
02/02 11:10, 24F
推
02/03 12:32, , 25F
若是聖經版要怎麼做呢？ 我覺得不是因為搜尋多一次換
02/03 12:32, 25F
→
02/03 12:32, , 26F
色？若沒做兩紅子點要換色的話，會陷入無窮Rotation
02/03 12:32, 26F
推
02/04 15:44, , 27F
大概懂了，應該是說洪逸版在每次遇到兩個子點是紅色時
02/04 15:44, 27F
推
02/04 15:44, , 28F
都會color change，但聖經版是只有兩個子點是紅色，而
02/04 15:44, 28F
推
02/04 15:44, , 29F
其中一個子點又insert新子點時，才需要對new node的父
02/04 15:44, 29F
推
02/04 15:44, , 30F
點跟父點的兄弟進行color change
02/04 15:44, 30F
‣ 更多 beargg0305 的文章
文章代碼(AID): #1Oa2vWp6 (Grad-ProbAsk)
‣ 更多 beargg0305 的文章
文章代碼(AID): #1Oa2vWp6 (Grad-ProbAsk)