[理工] 102 台大 資演

看板Grad-ProbAsk作者 (orange hat_t)時間7年前 (2017/02/07 13:52), 7年前編輯推噓5(5推 0噓 8→)
留言13則, 4人參與, 最新討論串1/1
想請教一個問題 102年的第2-b題 題目問說要如何將這樹轉成紅黑樹 請問大家是怎麼思考這題的呢? 我一開始切入觀點是把它當成空樹 依照2 1 4 3 6 5 8 7的順序去insert (如果不是這個順序 可能沒辦法做出原題之BST) 然後過程中要隨時保持紅黑樹特性 但看一下之前的文章，好像只是把原本的樹調整為AVL樹這樣的平衡樹 請問大家怎麼想這題呢? 謝謝 PS 請問紅黑樹在插入的過程也會一直保持高度平衡嗎 我插入到5的時候就發現它不是平衡了 有版友可以畫畫看討論一下嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.119.121.6 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486446774.A.620.html ※ 編輯: cthcsni (140.119.121.6), 02/07/2017 14:04:32
推
02/07 14:09, , 1F
我自己的想法是先把7拿掉，剩下的就可以著色成紅黑樹
02/07 14:09, 1F
→
02/07 14:09, , 2F
然後再插入7這個點這樣，我會這樣子描述拉...
02/07 14:09, 2F
→
02/07 14:13, , 3F
題目有說，through a single rotation
02/07 14:13, 3F
推
02/07 14:14, , 4F
紅黑樹不一定會一直保持高度平衡，我會把4拿到Root,再去
02/07 14:14, 4F
→
02/07 14:14, , 5F
著色
02/07 14:14, 5F
那要如何知道是要將4提上去當root? 提6似乎也可以 提上去後又要如何著色呢? 因為我學到的方法是一個一個新增 新增過程中顏色會依規則改變 而T大您的說法似乎是先將樹做出來，再著色? ※ 編輯: cthcsni (140.119.121.6), 02/07/2017 14:21:34
→
02/07 14:22, , 6F
紅黑度高度可能會到2*log(n+1)
02/07 14:22, 6F
推
02/07 14:25, , 7F
我覺得是題目解讀的關係，他叫我們draw the constructe
02/07 14:25, 7F
→
02/07 14:26, , 8F
d red-black tree and labeld its node with ... 我就當
02/07 14:26, 8F
→
02/07 14:26, , 9F
做先轉，再著色，不知道題目是不是這個意思
02/07 14:26, 9F
推
02/07 14:31, , 10F
我剛剛畫了一下，如果是照2,1,4,3,6,5,8,7 的確也可以畫
02/07 14:31, 10F
→
02/07 14:32, , 11F
成一棵Root=4的紅黑樹且只有一次rotation
02/07 14:32, 11F
→
02/07 14:32, , 12F
我說照那個順序insertion
02/07 14:32, 12F
請問您畫出來是2 6 7 是紅 其它黑嗎? 謝謝 ※ 編輯: cthcsni (140.119.121.6), 02/07/2017 14:38:44
推
02/07 14:41, , 13F
是的
02/07 14:41, 13F
‣ 更多 cthcsni 的文章
文章代碼(AID): #1OcM2sOW (Grad-ProbAsk)