[理工] AVL Tree Rotation次數 maple205 PTT批踢踢實業坊

作者: maple205 (è‰¾ç‘žå…‹) 2018-12-24 16:46:22

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

作者: b0920075 (Void) 2018-12-24 16:57:00

rotate最多的是O型腿那種，應該兩次吧

作者: magic83v (R7) 2018-12-24 17:07:00

請問哪裡有說是1或2次0.0

作者: sdfg014025xx (隨便就好) 2018-12-24 17:08:00

演算法的定義是single 和 double 資結定義的話新增是一種(RR or LR etc.)演算法的話就是2(最多一次double) 但我不是很確定有錯還請別人補充

作者: AliennC 2018-12-24 17:22:00

double rotation 最多一次 (RL & LR)，但有些書把 double rotation 視為兩次旋轉，因為 single rotation (LL &RR) 只需改變兩個指標，而double rotation 會改變四個指標，所以才有兩種說法

作者: maple205 (è‰¾ç‘žå…‹) 2018-12-24 17:36:00

對就是樓上說得那樣，但考試要依哪種呢？

繼續閱讀