[理工] 紅黑樹驗證

看板Grad-ProbAsk作者 (thisisfornote)時間9年前 (2017/01/20 01:54), 9年前編輯推噓28(28推 0噓 42→)
留言70則, 12人參與, 最新討論串1/1
http://i.imgur.com/oZM8Yy5.jpg
請問這串數字建紅黑樹是對的嗎？ 圈起來表Red Node ----- Sent from JPTT on my InFocus M350. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.100.196 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484848498.A.C8F.html
推
01/20 04:47, , 1F
我畫出來也是
01/20 04:47, 1F
推
01/20 08:17, , 2F
算第一次跟你們一樣，第二次發現是錯的
01/20 08:17, 2F
推
01/20 08:20, , 3F
最後插入1時，會看到root左子(5red)右子(22red)要C.C(
01/20 08:20, 3F
→
01/20 08:20, , 4F
變色)
01/20 08:20, 4F
推
01/20 09:24, , 5F
01/20 09:24, 5F
推
01/20 09:46, , 6F
我倒是覺得原po的圖是正確的 因為不是只要看有沒有違
01/20 09:46, 6F
→
01/20 09:46, , 7F
反「不要連續兩個紅節點的原則」就好了 好像沒有必要
01/20 09:46, 7F
→
01/20 09:46, , 8F
看到root節點
01/20 09:46, 8F
推
01/20 09:55, , 9F
我跟a199和boy畫的一樣,是插入12的時候對2跟10做cc,插入
01/20 09:55, 9F
→
01/20 09:56, , 10F
1的時候再對5跟22做cc,沒錯吧？
01/20 09:56, 10F
推
01/20 09:59, , 11F
可是明明插入1red的時候就沒有違反紅黑樹的定義啊
01/20 09:59, 11F
→
01/20 10:04, , 12F
01/20 10:04, 12F
→
01/20 10:06, , 13F
上面字請無視 我一直都是照著楓葉講解做的
01/20 10:06, 13F
推
01/20 10:16, , 14F
作法同樓上 我是看資結原文書學的 （個人覺得洪毅講的方
01/20 10:16, 14F
→
01/20 10:16, , 15F
法很奇怪
01/20 10:16, 15F
推
01/20 10:18, , 16F
我剛剛用模擬跑了一下，的確是跟ken那張圖一樣
01/20 10:18, 16F
→
01/20 10:18, , 17F
所以插入遇到兩個Red child,是要在什麼情況下要做cc啊？
01/20 10:18, 17F
推
01/20 10:20, , 18F
插入節點的叔叔節點為red的時候
01/20 10:20, 18F
推
01/20 10:23, , 19F
叔叔節點:插入節點的祖父節點除了插入節點父節點的另一
01/20 10:23, 19F
→
01/20 10:23, , 20F
個分支
01/20 10:23, 20F
推
01/20 10:25, , 21F
按照ken52011219大的圖來看就是在插入12red那時候
01/20 10:25, 21F
→
01/20 10:27, , 22F
就是一個很標準的父子連續兩個紅節點且叔叔節點為紅的
01/20 10:27, 22F
→
01/20 10:27, , 23F
狀況
01/20 10:27, 23F
推
01/20 10:28, , 24F
叔:2red 祖父:5 父:10red 子:12red
01/20 10:28, 24F
推
01/20 10:44, , 25F
了解，感謝
01/20 10:44, 25F
推
01/20 12:58, , 26F
其實我也是照洪逸方法，話說哪個才是正解?
01/20 12:58, 26F
推
01/20 13:06, , 27F
推叔叔節點這個說法，好容易記，我一開始也是洪逸派的
01/20 13:06, 27F
→
01/20 13:06, , 28F
現在注意到這個問題來改成原文書派的好了
01/20 13:06, 28F
推
01/20 13:24, , 29F
先老實承認叔叔節點也是我從網路上看到的說法
01/20 13:24, 29F
推
01/20 13:26, , 30F
to a19930301大:你可以看看先看看紅黑樹的定義 再慢慢
01/20 13:26, 30F
→
01/20 13:26, , 31F
推導看每一步的旋轉顏色轉變平衡是否需要
01/20 13:26, 31F
推
01/20 15:36, , 32F
01/20 15:36, 32F
→
01/20 15:37, , 33F
www.cs.usfca.edu/~galles/visualization/RedBlack.html
01/20 15:37, 33F
後來再算一次 發現跟boy一樣 洪逸解答也是給boy那張圖的
推
01/20 15:40, , 34F
假如在ck那張圖再插入51會變怎樣呢，因為跟老師講的不一
01/20 15:40, 34F
→
01/20 15:40, , 35F
樣..
01/20 15:40, 35F
→
01/20 15:41, , 36F
插入如果做完color change,又變成連續兩紅Red（因為cc)
01/20 15:41, 36F
→
01/20 15:41, , 37F
對於那連續兩Red nodes,我要先做Rotation再把新點插入
01/20 15:41, 37F
→
01/20 15:41, , 38F
還是？
01/20 15:41, 38F
推
01/20 15:45, , 39F
我跑了simulator，他是先cc之後發現又有連續2紅，但是
01/20 15:45, 39F
→
01/20 15:46, , 40F
連續2紅的那個叔叔節點也是紅，所以做cc就好，沒做
01/20 15:46, 40F
→
01/20 15:46, , 41F
rotation
01/20 15:46, 41F
推
01/20 16:10, , 42F
加入51後同yupog2003大的只變色沒旋轉
01/20 16:10, 42F
推
01/20 17:21, , 43F
所以到底是boy大還是ken大的對啊 是每次遇到雙紅都要
01/20 17:21, 43F
→
01/20 17:21, , 44F
旋轉還是只有靠近會影響的那次
01/20 17:21, 44F
我覺得boy大 遇到雙紅子點color change 遇到連續紅旋轉
→
01/20 17:26, , 45F
我的理解是兩個都可以造出合格的red-black tree，
01/20 17:26, 45F
※ 編輯: fornote (36.231.97.35), 01/20/2017 17:27:49
→
01/20 17:27, , 46F
反正red-black tree本來就不會唯一，但考試的時候一定
01/20 17:27, 46F
→
01/20 17:28, , 47F
要挑一種版本，我認為挑原文書用的版本比較好，畢竟他
01/20 17:28, 47F
→
01/20 17:28, , 48F
是教授出題的時候會參考的版本
01/20 17:28, 48F
推
01/20 17:30, , 49F
可是原文也很難說吧 很多科原文一樣東西定義不同哇勒
01/20 17:30, 49F
→
01/20 17:31, , 50F
A大說的也對拉XD height定義不同、complete full
01/20 17:31, 50F
→
01/20 17:31, , 51F
定義不同...
01/20 17:31, 51F
→
01/20 17:32, , 52F
考簡答還可以跟教授說我想用的定義，考選擇題目沒考慮
01/20 17:32, 52F
→
01/20 17:32, , 53F
到就直接擲茭
01/20 17:32, 53F
→
01/20 17:36, , 54F
以台交清而言我信 原文書，已經有很多都是從楓葉本
01/20 17:36, 54F
→
01/20 17:36, , 55F
的習題裡面原封不動地拿出來考了
01/20 17:36, 55F
→
01/20 17:37, , 56F
只不過還是老話一句，相信自己的答案 尤其越到了這個
01/20 17:37, 56F
→
01/20 17:37, , 57F
時候
01/20 17:37, 57F
→
01/20 17:39, , 58F
還記得修我們系上的演算法課的時候 教授曾說過
01/20 17:39, 58F
→
01/20 17:39, , 59F
市面上有蠻多種紅黑樹插入的演算法 當時我其實不太
01/20 17:39, 59F
→
01/20 17:40, , 60F
理解 覺得哪有可能 一定有唯一的方法可以達到通解
01/20 17:40, 60F
→
01/20 17:41, , 61F
只不過紅黑樹是種規則，並非演算法 必然就有不同的演
01/20 17:41, 61F
→
01/20 17:41, , 62F
算法 去完成這個規則
01/20 17:41, 62F
→
01/20 17:42, , 63F
以上，覺得誰的可信或不可信都可，找到自己的方法去
01/20 17:42, 63F
→
01/20 17:42, , 64F
正確解決在考場上遇到的問題才是重點
01/20 17:42, 64F
→
01/20 17:44, , 65F
題外話，就因為插入有不只一種的方法去詮釋它
01/20 17:44, 65F
→
01/20 17:44, , 66F
所以我想這也是為什麼紅黑樹刪除幾乎不考的原因吧
01/20 17:44, 66F
推
01/20 18:49, , 67F
同意ken52011219大說的
01/20 18:49, 67F
推
01/20 19:02, , 68F
推ken大 我認同
01/20 19:02, 68F
推
02/17 16:13, , 69F
推
02/17 16:13, 69F
推
03/02 18:49, , 70F
紅黑樹的刪除真的很少考 (海大103資結3b)
03/02 18:49, 70F
‣ 更多 fornote 的文章
文章代碼(AID): #1OWFrooF (Grad-ProbAsk)