作者x411066 (热开水)
看板Grad-ProbAsk
标题[理工] AVL Tree T/F
时间Thu Jan 2 18:06:58 2020
您好，问题如下:
Which statement(s) is correct for an AVL Tree?
(1) The absolute value of the level difference of any two leaves is at most
one.
(2) The absolute value of the height difference of any two subtrees on the
same level is at most one.
(3) A deletion needs at most two rotation operations to preserve an AVL Tree
to be a height-balanced tree.
(4) After a new node is inserted, the tree height will not increase if
rotation operations are performed.
Ans: (D)
(1)反例
https://imgur.com/e5AyByL
--> 6和30的高度差2
Q: 为什麽(2)的叙述是错误的?
在"相同的Level"的"任意2个子树"的高度差最多差1。
不知道有没有反例可以举出来。
更新:谢谢提醒，我发现(1)的反例也是(2)的反例。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 120.126.33.178 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1577959620.A.E08.html
1F：→ cossetannie: 你自己不就举了一个 01/02 18:10
2F：→ zuchang: 8.30就是啊 再加同父点的话就对 01/02 18:10
※ 编辑: x411066 (120.126.33.178 台湾), 01/02/2020 19:28:27