资结 AVL tree 问题 mloop PTT批踢踢实业坊

楼主: mloop (mloop) 2016-08-01 15:57:08

http://i.imgur.com/7r7RuqD.jpg
我想请问一下C选项答案是给说正确
但是在AVL树应该的确是存在有高度差超过1的Leaves
例如这棵
http://i.imgur.com/q2v1Y4o.jpg
想请问是我想法哪里有误

作者: ken52011219 (呱) 2016-08-01 17:23:00

第二张图还没平衡过不算AVL TREE正确AVL TREE的balanceFcator∈{-1,0,1} 题目无误

作者: gary19941208 2016-08-01 17:07:00

针对每个节点，左右子树高度差小于等于1，你去检视那颗树的每个节点就会发现其实他高度差没有超过1哦哦！没看清楚...那我也觉得可以...

作者: ken52011219 (呱) 2016-08-01 17:50:00

你说的有理QQ 那我觉得问题应该是any pair of leaves题目在玩文字游戏了

楼主: mloop (mloop) 2016-08-01 17:43:00

http://i.imgur.com/pizadRh.jpg这样子看起来应该是不需要调整吧http://i.imgur.com/x9e3REm.jpg然后根据高度5最小棵的AVL树画出来是长这样所以应该树是正确的

楼主: mloop (mloop) 2016-08-01 17:03:00

我是想问选项C 因为选项的意思看起来是任两个Leaves的高度不超过1 但应该是可以

作者: gary19941208 2016-08-01 16:36:00

AVL tree不会有高度差超过1，是指左子树和右子树的高度差

继续阅读