[理工] AVL Tree Rotation次數

看板Grad-ProbAsk作者 (正取)時間7年前 (2018/12/24 16:46), 7年前編輯推噓4(4推 0噓 6→)
留言10則, 5人參與, 7年前最新討論串1/1
請問AVL做insert最多roatation到底是1還是2次。 兩種說法都看過，弄得我好亂... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.233.66.10 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545641185.A.C77.html
推
12/24 16:57, 7年前 , 1F
rotate最多的是O型腿那種，應該兩次吧
12/24 16:57, 1F
推
12/24 17:07, 7年前 , 2F
請問哪裡有說是1或2次0.0
12/24 17:07, 2F
推
12/24 17:08, 7年前 , 3F
演算法的定義是single 和 double 資結定義的話新增
12/24 17:08, 3F
→
12/24 17:08, 7年前 , 4F
是一種(RR or LR etc.)演算法的話就是2(最多一次dou
12/24 17:08, 4F
→
12/24 17:08, 7年前 , 5F
ble) 但我不是很確定 有錯還請別人補充
12/24 17:08, 5F
推
12/24 17:22, 7年前 , 6F
double rotation 最多一次 (RL & LR)，但有些書把 doubl
12/24 17:22, 6F
→
12/24 17:22, 7年前 , 7F
e rotation 視為兩次旋轉，因為 single rotation (LL &
12/24 17:22, 7F
→
12/24 17:22, 7年前 , 8F
RR) 只需改變兩個指標，而double rotation 會改變四個指
12/24 17:22, 8F
→
12/24 17:22, 7年前 , 9F
標，所以才有兩種說法
12/24 17:22, 9F
→
12/24 17:36, 7年前 , 10F
對 就是樓上說得那樣，但考試要依哪種呢？
12/24 17:36, 10F
※ 編輯: maple205 (118.233.66.10), 12/24/2018 19:52:53
‣ 更多 maple205 的文章
文章代碼(AID): #1S89pXnt (Grad-ProbAsk)