[理工] [資結]102清大

看板Grad-ProbAsk作者 (yraid)時間13年前 (2013/02/07 18:43), 編輯推噓6(6推 0噓 13→)
留言19則, 8人參與, 最新討論串1/1
有一題要我們為紅黑樹上色， 是說一直覺得那題怪怪的... 標完之後會有紅-紅的情況， 所以是還要再做旋轉才是答案嗎? 考試的時候頗困擾... 因為不知道能不能再做旋轉然後當答案... 有人能不用轉然後標顏色的嗎? 感謝回答~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.194.219.134
→
02/07 19:00, , 1F
b,b,b,b,b,r,r,b,b,b,b,r,r topologicl順序
02/07 19:00, 1F
→
02/07 19:15, , 2F
請問新插入的點不是會標紅色嗎?然後就會有個黑父有兩個紅子,
02/07 19:15, 2F
→
02/07 19:15, , 3F
直到又有新點插到他們下面，才會做父子的color change..
02/07 19:15, 3F
→
02/07 19:16, , 4F
那這樣為什麼root的左子樹的leaf會是黑色呢?
02/07 19:16, 4F
→
02/07 19:17, , 5F
還有右子樹為什麼會有個父點有兩紅子，他們下面卻還有其他點
02/07 19:17, 5F
→
02/07 19:18, , 6F
呢? (這樣敘述頗混亂= = 不知道能不能了解我在說甚麼QQ
02/07 19:18, 6F
→
02/07 19:37, , 7F
他又不一定要是插入 有可能做完刪除過
02/07 19:37, 7F
→
02/07 19:38, , 8F
反正重點就是樹根是黑的 然後到每個外部節點的
02/07 19:38, 8F
→
02/07 19:38, , 9F
黑色路徑長度一樣 還有不能連續二洪
02/07 19:38, 9F
→
02/07 20:07, , 10F
喔喔@@ 原來如此~ 謝謝 :)
02/07 20:07, 10F
→
02/07 20:23, , 11F
今年很喜歡考 red-black tree 不知道甚麼原因
02/07 20:23, 11F
推
02/07 22:16, , 12F
紅黑樹一直都是主流 不管是不是在考試上
02/07 22:16, 12F
推
02/12 11:56, , 13F
塗顏色跟做插入不一樣，我用插入的無法不做旋轉，可是如果
02/12 11:56, 13F
→
02/12 11:57, , 14F
是塗成符合紅黑樹規定的顏色的話是可以的
02/12 11:57, 14F
→
02/12 12:02, , 15F
另外好奇一下，這題塗色法唯一嗎@@?
02/12 12:02, 15F
推
02/12 19:37, , 16F
不唯一 還可以畫出b,b,r,b,b,b,b,b,b,b,r,b,b
02/12 19:37, 16F
推
02/12 19:39, , 17F
這種順序也沒有違反紅黑樹定義 只不過插入弄不出來....
02/12 19:39, 17F
推
02/13 16:53, , 18F
一樓大大的答案好像怪怪的leaf不能有r吧?
02/13 16:53, 18F
推
02/13 18:11, , 19F
阿不對 我搞錯了 沒事
02/13 18:11, 19F
‣ 更多 yraid 的文章
文章代碼(AID): #1H4uLYRH (Grad-ProbAsk)