作者fightforlive (学历无用论是屁)
看板Grad-ProbAsk
标题[理工] 资结 AVLtree问题
时间Sun Jul 3 18:42:14 2022
底下是102中山资工的题目
想问一下这三个选项
(A)和(B)看起来都没错啊...有反例的?
(C)应该是不一定,主要是在删除後需要向上调整,一直到全部平衡系数都正常为止
https://i.imgur.com/1ktnmUj.jpg
----
Sent from
BePTT on my iPhone XR
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.51.120.117 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1656844936.A.FFC.html
1F：推 NCTUCKCurry: B才是对的 AVL tree可以长得很歪 A就有可能会错 07/04 16:14
2F：→ fightforlive: 为什麽AVL tree可以长得很歪? 07/04 17:56
3F：推 NCTUCKCurry: 因为AVL Tree限制的是左右subtree的高度 不是限制lea 07/04 18:06
4F：→ NCTUCKCurry: f 07/04 18:06
5F：→ NCTUCKCurry: 随便画应该就可以画出反例了 07/04 18:07
6F：→ fightforlive: 还是画不出来...左右subtree在长高,leaf也是跟增长 07/04 18:15
7F：→ fightforlive: ,偏左或偏右长下去,也会让上面的Node不平衡,这样不 07/04 18:15
8F：→ fightforlive: 是要让另一边跟着长? 07/04 18:15
10F：→ NCTUCKCurry: ht-difference-between-leaves-in-an-avl-tree 07/04 18:19
11F：→ fightforlive: 感谢~~我好笨...其实满好画的,刚刚画出来了 07/04 18:23