[理工] 103 台科资工概论 chadcoco1222 PTT批踢踢实业坊

楼主: chadcoco1222 (ha) 2016-02-17 14:51:45

http://i.imgur.com/mFq1HDz.jpg
http://i.imgur.com/UGNBLVG.jpg
各位正取大大好，
想请问第五题的题意是什么
a)列出最大及最小底比较次数
b)关系应该是sibling?
c)是要找obst吗？
第三题有人会吗求教学！
感谢！

作者: HEroKuma (不是Hero,是H+Ero) 2016-02-17 15:49:00

5.a要你列出找出一个数B不在BST里最多/少比较次数5.b a6<a4<a7 或是a6跟a7是兄弟我觉得没有描述很清楚

作者: rockamy82927 (rock) 2016-02-17 15:52:00

所以a是利用题目的树看吗？max4次，min2次？

作者: HEroKuma (不是Hero,是H+Ero) 2016-02-17 15:56:00

5.c我觉得是问说找一个输入能作出一个高度最小的BST且新的输入数列的调整的次数要最小a应该就是min/max = 4/2没错

楼主: chadcoco1222 (ha) 2016-02-17 16:18:00

感谢回复 a b都懂了 c 不知道怎么下手跟avl tree有关吗...

作者: makemyday (make my day) 2016-02-17 17:03:00

就是要balanced BST 所以可以用AVL tree 这题用AVL只会有一次rotation

作者: HEroKuma (不是Hero,是H+Ero) 2016-02-17 17:13:00

所以作完AVL后照level order输出就好! 感谢m大看到这一就瞬间懂解法了XD 刚刚想的太复杂

楼主: chadcoco1222 (ha) 2016-02-17 17:33:00

感谢啊直觉没错xd谢谢h m大

继续阅读