作者kaidi620 (萬能史哥)
看板Grad-ProbAsk
標題AVL Tree
時間Thu Feb 14 21:05:15 2019
小弟真的是讀都頭腦壞掉了 現在有一些簡單的反而都忘掉
想請問一下AVL 高度差要為1 但當子樹和整顆樹高度差都為2時 需要以哪一個作rotation
呢？
avl樹若用一個順序插入 那AVL是不是唯一的呢 請大神指點一下
附上清大兩題 考試前突然當機忘了怎麼作
https://i.imgur.com/oYSra4M.jpg
https://i.imgur.com/emSMoNK.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.5.170
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1550149517.A.1D5.html
1F：推 mage594088: 子樹，能盡量不改變就不改變~ 02/14 21:08
2F：推 ghost1025: 以新插入點最近造成不平衡的為準 02/14 21:09
3F：推 bmpss92196: 調離插入點最近的不平衡點 02/14 21:09
4F：推 Faker0613: 從下面往上數012 第一個2的下面要旋轉 02/14 21:11
5F：推 sooge: 我是眼鏡當機....鬼遮眼看成binary tree直接噴五分 02/14 21:25
6F：→ GeniusPuddin: 7.因為binary heap的節點個數就可以確定它的形狀 02/14 21:28
7F：→ GeniusPuddin: 所以就把它10個樹的結點畫出來 再用inorder依序填入 02/14 21:29
8F：推 imadog: 我也當機 分數噴一波QQQQ 02/14 21:32
9F：噓 magic83v: 背一堆priority heap結果忘記avl要拉誰... 02/14 21:46
10F：→ kaidi620: 真的 我覺得看太多東西前面有些會搞混 不小心忘記一些 02/14 21:54
11F：→ kaidi620: 以調離插入最近的不平衡點 所以AVL做出來是唯一的嗎? 02/14 21:54
12F：推 bmpss92196: avl的順序跟你插入順序有關，順序一樣就一樣 02/14 22:16
13F：推 cool9203: 我也鬼遮眼QQ最後1分鐘才發現自己畫錯，只來得及改到一 02/14 22:18
14F：→ cool9203: 題而已QQ 02/14 22:18
15F：推 akkevin00: 沒記錯應該是唯一 02/14 22:25
16F：推 y2j60537: 靠北 我看成LEVEL ORDER ㄎㄎ 02/14 22:30
17F：→ kaidi620: 所以就是改距離插入點最近的就是了 這樣我懂了感恩~~ 02/14 22:39
18F：→ Neverfor: 對 "最近" 02/15 09:23
20F：→ S2067030: 可以考慮看這個，交大考完我也有點忘記 02/15 21:58
21F：→ S2067030: 筆記又忘記帶去新竹，在旅店的時候上網找這個看 02/15 21:58
22F：→ S2067030: 隔天考清大就完全沒問題了 02/15 21:58
23F：→ S2067030: 有字幕，可以考慮調快播放倍率，節省付息時間 02/15 21:59