[理工] AVL Tree Rotation次數

[maple205 (正取)]

請問AVL做insert最多roatation到底是1還是2次。
兩種說法都看過，弄得我好亂...

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.233.66.10
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545641185.A.C77.html
推 b0920075: rotate最多的是O型腿那種，應該兩次吧
推 magic83v: 請問哪裡有說是1或2次0.0
推 sdfg014025xx: 演算法的定義是single 和 double  資結定義的話新增
→ sdfg014025xx: 是一種(RR or LR etc.)演算法的話就是2(最多一次dou
→ sdfg014025xx: ble)   但我不是很確定 有錯還請別人補充
推 AliennC: double rotation 最多一次 (RL & LR)，但有些書把 doubl
→ AliennC: e rotation 視為兩次旋轉，因為 single rotation (LL &
→ AliennC: RR) 只需改變兩個指標，而double rotation 會改變四個指
→ AliennC: 標，所以才有兩種說法
→ maple205: 對 就是樓上說得那樣，但考試要依哪種呢？
※ 編輯: maple205 (118.233.66.10), 12/24/2018 19:52:53