作者dsa66253 (Kobe Mary)
看板Grad-ProbAsk
标题[理工] 台大电机 97 11题 balanced tree rotate
时间Wed Nov 20 11:40:52 2019
这边有两题很相近的题目，以前板上有讨论一次，只是查了之後发现跟洪逸老师有点出入
，所以拿出来再讨论清楚一点，他们讨论过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://webptt.com/cn.aspx?n=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