[理工] AVL樹的建立

看板Grad-ProbAsk作者 (天生我材)時間10年前 (2014/03/25 00:29), 編輯推噓5(5推 0噓 12→)
留言17則, 4人參與, 最新討論串1/1
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
→
03/25 01:26, , 1F
只要高度差2就要一律都要調整，沒看懂AVL定義吧
03/25 01:26, 1F
→
03/25 01:27, , 2F
以第一顆插80為例 以root=40來看height left=1 right=3
03/25 01:27, 2F
推
03/25 07:27, , 3F
接樓上 所以40 65 70要調整
03/25 07:27, 3F
請益樓上 為何會挑 40 65 70 怎不是挑 65 70 80 這區間??不是才剛加入80節點嗎
推
03/25 08:33, , 4F
03/25 08:33, 4F
大大 感謝你的分享圖，但是我還是有幾個地方不解，第四列第二張圖 為何會挑LL 調65 50 40這部分呢? ※ 編輯: oklp1415 來自: 114.39.5.119 (03/25 13:33)
推
03/25 13:29, , 5F
以65為root的子樹為平衡不需要調整
03/25 13:29, 5F
推
03/25 13:36, , 6F
以50為root的樹為平衡(左右子樹高度不超過1)，以65為root的
03/25 13:36, 6F
→
03/25 13:37, , 7F
樹左右子樹不平衡，以root到不平衡的方向找
03/25 13:37, 7F
這個特點我了解，只是不是知道要如何去挑 LL 的部分 所以做題目有點卡卡的!! 希望能找到突破點~"~感謝 因該說 不知道如何看哪個分支要做什麼調整<---- ※ 編輯: oklp1415 來自: 114.39.5.119 (03/25 13:38)
→
03/25 13:40, , 8F
由root到最後你加入那個點的方向
03/25 13:40, 8F
→
03/25 13:45, , 9F
不平衡的樹，一切以root往你加入的那的點開始算兩格
03/25 13:45, 9F
不平衡的樹，一切以root往你加入的那的點開始算兩格，那我的疑惑點是 第四列第二張圖，怎不是去挑40 45 43 而是去挑65 50 40這部分做調整?? 跟第三列最後一張圖比較來看這部分能理解，只是在挑的過程總是解題卡卡的
→
03/25 13:45, , 10F
這邊的root是指不平衡的樹root
03/25 13:45, 10F
→
03/25 13:46, , 11F
不是整棵樹的root
03/25 13:46, 11F
→
03/25 13:49, , 12F
L=左 R=右
03/25 13:49, 12F
※ 編輯: oklp1415 來自: 114.39.5.119 (03/25 13:54)
→
03/25 13:56, , 13F
挑40 45 43必須是 40 35 45 43那棵樹不平衡才挑的
03/25 13:56, 13F
→
03/25 13:59, , 14F
第三列最後一張是因為，小的樹調整完後，可以使整棵樹平衡
03/25 13:59, 14F
→
03/25 14:00, , 15F
原則是小的樹不平衡先調
03/25 14:00, 15F
→
03/25 14:10, , 16F
把每個節點的高度標出來，看2在哪裡，從那點開始算
03/25 14:10, 16F
※ 編輯: oklp1415 來自: 114.39.5.119 (03/25 14:21)
推
04/03 17:05, , 17F
用每個點去檢查左右子樹
04/03 17:05, 17F
‣ 更多 oklp1415 的文章
文章代碼(AID): #1JC5rVjb (Grad-ProbAsk)