[理工] 103 台科 資工概論

看板Grad-ProbAsk作者 (ha)時間9年前 (2016/02/17 14:51), 編輯推噓2(2012)
留言14則, 4人參與, 最新討論串1/1
http://i.imgur.com/mFq1HDz.jpg
http://i.imgur.com/UGNBLVG.jpg
各位正取大大好, 想請問第五題的題意是什麼 a)列出最大及最小底比較次數 b)關係應該是sibling? c)是要找obst嗎? 第三題有人會嗎 求教學! 感謝! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.26.115.252 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455691908.A.301.html

02/17 15:49, , 1F
5.a要你列出找出一個數B不在BST裡 最多/少比較次數
02/17 15:49, 1F

02/17 15:51, , 2F
5.b a6<a4<a7 或是a6跟a7是兄弟 我覺得沒有描述很清楚
02/17 15:51, 2F

02/17 15:52, , 3F
所以a是利用題目的樹看嗎?max4次,min2次?
02/17 15:52, 3F

02/17 15:56, , 4F
5.c我覺得是問說找一個輸入能作出一個高度最小的BST
02/17 15:56, 4F

02/17 15:57, , 5F
且新的輸入數列的調整的次數要最小
02/17 15:57, 5F

02/17 15:57, , 6F
a應該就是min/max = 4/2沒錯
02/17 15:57, 6F

02/17 16:18, , 7F
感謝回覆 a b都懂了 c 不知道怎麼下手 跟avl tree
02/17 16:18, 7F

02/17 16:18, , 8F
有關嗎...
02/17 16:18, 8F

02/17 17:03, , 9F
就是要balanced BST 所以可以用AVL tree 這題用AVL只會
02/17 17:03, 9F

02/17 17:03, , 10F
有一次rotation
02/17 17:03, 10F

02/17 17:13, , 11F
所以作完AVL後照level order輸出就好! 感謝m大 看到這一
02/17 17:13, 11F

02/17 17:14, , 12F
就瞬間懂解法了XD 剛剛想的太複雜
02/17 17:14, 12F

02/17 17:33, , 13F
感謝啊 直覺沒錯xd
02/17 17:33, 13F

02/17 17:33, , 14F
謝謝h m大
02/17 17:33, 14F
文章代碼(AID): #1Mn1Y4C1 (Grad-ProbAsk)