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