[理工] AVL樹的建立

[oklp1415 (天生我材)]

Show the detail steps of inserting the following values into an AVL tree:

65, 35, 40, 70, 50, 80, 55, 60, 45, 43, 30


我的問題是這樣

        40
      /    \
     35     65
          /    \
         50     70
                  \
                   80   加入80後要如何去做調整呢??  還是無須作調整
                                                    繼續下一個node?
                                               因為對這種辨別方式不太了解

        40
      /    \
     35     65
          /    \
         50     70
           \      \
            55     80

等到這樣才需要做調整嗎??  求AVL詳解，3Q

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.8.119
→ kiki86151:只要高度差2就要一律都要調整，沒看懂AVL定義吧
→ kiki86151:以第一顆插80為例 以root=40來看height left=1 right=3
推 hsuanyao:接樓上 所以40 65 70要調整
請益樓上  為何會挑  40 65 70  怎不是挑  65 70 80 這區間??不是才剛加入80節點嗎
推 cs228:http://imgur.com/EUujsNh
大大 感謝你的分享圖，但是我還是有幾個地方不解，第四列第二張圖 為何會挑LL
調65 50 40這部分呢?
※ 編輯: oklp1415        來自: 114.39.5.119         (03/25 13:33)
推 cs228:以65為root的子樹為平衡不需要調整
推 cs228:以50為root的樹為平衡(左右子樹高度不超過1)，以65為root的
→ cs228:樹左右子樹不平衡，以root到不平衡的方向找
這個特點我了解，只是不是知道要如何去挑 LL 的部分  所以做題目有點卡卡的!!
希望能找到突破點~"~感謝
因該說  不知道如何看哪個分支要做什麼調整<----
※ 編輯: oklp1415        來自: 114.39.5.119         (03/25 13:38)
→ cs228:由root到最後你加入那個點的方向
→ cs228:不平衡的樹，一切以root往你加入的那的點開始算兩格
不平衡的樹，一切以root往你加入的那的點開始算兩格，那我的疑惑點是
第四列第二張圖，怎不是去挑40  45  43 而是去挑65 50 40這部分做調整??
跟第三列最後一張圖比較來看這部分能理解，只是在挑的過程總是解題卡卡的
→ cs228:這邊的root是指不平衡的樹root
→ cs228:不是整棵樹的root
→ cs228:L=左 R=右
※ 編輯: oklp1415        來自: 114.39.5.119         (03/25 13:54)
→ cs228:挑40 45 43必須是 40 35 45 43那棵樹不平衡才挑的
→ cs228:第三列最後一張是因為，小的樹調整完後，可以使整棵樹平衡
→ cs228:原則是小的樹不平衡先調
→ PTT007:把每個節點的高度標出來，看2在哪裡，從那點開始算
※ 編輯: oklp1415        來自: 114.39.5.119         (03/25 14:21)
推 hsuanyao:用每個點去檢查左右子樹