[理工] 资料结构 ΑVL tree can18 PTT批踢踢实业坊

[理工] 资料结构 ΑVL tree

楼主: can18 (18号) 2017-10-03 18:56:26

https://i.imgur.com/SdBExgu.jpg
第三题的 C 选项
the level difference of any pair of leaves is at most one
答案给true
可是我找到的反例(AVL tree)
https://i.imgur.com/bABAbbJ.jpg
蓝点 level 差了2
请问是答案错误还是我画错了呢

作者: s1020824 (HowardW) 2017-10-03 20:48:00

定义是左右子树高度差左子树高度=5 右子树高度=4所以没问题吧

楼主: can18 (18号) 2017-10-03 21:52:00

没问题的是答案还是我画的XD

作者: s1020824 (HowardW) 2017-10-03 22:11:00

答案没问题你画的也没问题AVL tree的定义是|左右子树高度差|<=1 且左右子树也是AVL tree左子树高度是5 右子树高度是4相差=1 分别看也都符合AVL tree

楼主: can18 (18号) 2017-10-03 22:43:00

可是我找到选项的反例为何还是true?

作者: s1020824 (HowardW) 2017-10-03 23:02:00

你画的不是反例

作者: sarsman (DeNT15T♠) 2017-10-03 23:31:00

difference of “any pair” of leaves感觉是答案的问题

楼主: can18 (18号) 2017-10-03 23:47:00

s10 大为何不是反例呢?两个蓝色点都是leaf

作者: s1020824 (HowardW) 2017-10-04 00:16:00

真的欸对不起我误会你的意思了QQ

作者: kobebset105 (小小小妹) 2017-10-04 13:01:00

他的意思可能是一对子叶对一对子叶高度差一。你画的是一颗节点对节点

继续阅读

Re: [理工] 拉氏逆转换Honor1984 [理工] 拉氏逆转换ab4010800 [理工] 张凡计组p.513 multiple issueclonsey1314 [理工] [线代] 黄子嘉2-51范例4s90210jackle [理工] 计组第四章练习题bobsonlin [理工] 资料结构Quick sortlovepipi [理工] 离散子群证明问题s1020824 [计组]96政大资科-virtual address cacheking8313 [理工] 计组程序呼叫概念ahahahahah [理工] 线代 eigenvalue 个数jerry900287