[理工] [DS]-93交大-電機控制所

[assassin88 (AI)]

《資料結構》 洪逸 P.9-109
給定以下key值，請造出red-black tree：
15 57 27 45 30 40 33 39 36 37

最右下角那兩個圖，是不是畫錯？
    27
    /\
  15 *45
     /  \
   *33   57
   / \
  30  40

插入39後↓

    27
    /\
  15 *45
     /  \
   *33   57
   / \
  30  40
      /
     39

應該是45這個node先不平衡，所以調成↓

    27
    / \
  15  40
     /  \
    33   45
   / \    \
  30  39   57

再來是27不平衡，所以調成↓

    33
    / \
  27   40
 / \   / \
15 30 39 45
           \
           57

這樣才對吧？有錯麻煩指證一下....
另外想請問紅黑樹在旋轉時，就是發生LR或者RL情況，
旋轉後尚未調整平衡前，node的顏色不變嗎？
調整後再改變~是這樣嗎？

請指導~感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.57.78.8
→ ieric:我是看法是1開始你不能插入39 因為圖形得先做旋轉
推 polomoss:答案沒有錯...這只能體會~~"
→ assassin88:我會錯意~XD
→ supergud:45不會不平衡阿
推 taitin:第一步要先rotation，才可插入
→ assassin88:其實我發現我看錯圖..其實第二排開始就錯了(不平衡)
→ assassin88:↑指書上