[理工] 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大

繼續閱讀