[理工] 102 台大 資演

[cthcsni (orange hat_t)]

想請教一個問題

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
推 kyuudonut: 我自己的想法是先把7拿掉，剩下的就可以著色成紅黑樹
→ kyuudonut: 然後再插入7這個點這樣，我會這樣子描述拉...
→ gouya: 題目有說，through a single rotation
推 Transfat: 紅黑樹不一定會一直保持高度平衡，我會把4拿到Root,再去
→ Transfat: 著色
那要如何知道是要將4提上去當root? 提6似乎也可以 提上去後又要如何著色呢?
因為我學到的方法是一個一個新增 新增過程中顏色會依規則改變
而T大您的說法似乎是先將樹做出來，再著色?
※ 編輯: cthcsni (140.119.121.6), 02/07/2017 14:21:34
→ aa06697: 紅黑度高度可能會到2*log(n+1)
推 Transfat: 我覺得是題目解讀的關係，他叫我們draw the constructe
→ Transfat: d red-black tree and labeld its node with ... 我就當
→ Transfat: 做先轉，再著色，不知道題目是不是這個意思
推 Transfat: 我剛剛畫了一下，如果是照2,1,4,3,6,5,8,7 的確也可以畫
→ Transfat: 成一棵Root=4的紅黑樹且只有一次rotation
→ Transfat: 我說照那個順序insertion
請問您畫出來是2 6 7 是紅 其它黑嗎? 謝謝
※ 編輯: cthcsni (140.119.121.6), 02/07/2017 14:38:44
推 Transfat: 是的