[理工] 台大電機 97資結 11 15題 tree rotation
這邊有兩題很相近的題目，以前板上有討論一次，只是查了之後發現跟洪逸老師有點出入
，所以拿出來再討論清楚一點，他們討論過11題
台大電機97 11(D)
After inserting a new node to an AVL tree, at most two rotation are needed to
re-balanced the tree.(False)
但討論結果(True)
台大電機97 15 After inserting a new node to a red-black tree, at most two r
otation are needed to re-balanced the tree.(True)
討論的結論：
AVL/R-B insert： [DS]1 Rotation [Algo]2 Rotation
AVL/R-B delete： [DS]2 Rotation [Algo]3 Rotation
是說因為algo視double rotation 為兩次rotate，single rotation 為一次rotate。 在
insert時，最多可能發生一次double rotation，所以稱為”at most two rotation”。
在deletion時，可能發生一次single rotation，再發生一次double rotation，所以”at
most three rotation”?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 150.117.242.146 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1574221254.A.AD4.html
※ 編輯: dsa66253 (150.117.242.146 臺灣), 11/20/2019 11:42:47
※ 編輯: dsa66253 (150.117.242.146 臺灣), 11/20/2019 11:44:08