作者maple205 (正取)
看板Grad-ProbAsk
標題[理工] AVL Tree Rotation次數
時間Mon Dec 24 16:46:22 2018
請問AVL做insert最多roatation到底是1還是2次。
兩種說法都看過，弄得我好亂...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.233.66.10
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1545641185.A.C77.html
1F：推 b0920075: rotate最多的是O型腿那種，應該兩次吧12/24 16:57
2F：推 magic83v: 請問哪裡有說是1或2次0.012/24 17:07
3F：推 sdfg014025xx: 演算法的定義是single 和 double 資結定義的話新增12/24 17:08
4F：→ sdfg014025xx: 是一種(RR or LR etc.)演算法的話就是2(最多一次dou12/24 17:08
5F：→ sdfg014025xx: ble) 但我不是很確定 有錯還請別人補充12/24 17:08
6F：推 AliennC: double rotation 最多一次 (RL & LR)，但有些書把 doubl12/24 17:22
7F：→ AliennC: e rotation 視為兩次旋轉，因為 single rotation (LL &12/24 17:22
8F：→ AliennC: RR) 只需改變兩個指標，而double rotation 會改變四個指12/24 17:22
9F：→ AliennC: 標，所以才有兩種說法12/24 17:22
10F：→ maple205: 對 就是樓上說得那樣，但考試要依哪種呢？12/24 17:36
※ 編輯: maple205 (118.233.66.10), 12/24/2018 19:52:53