[理工] 105交大資演 21,28 疑問

看板Grad-ProbAsk作者 (善良老百姓)時間9年前 (2017/01/03 14:41), 9年前編輯推噓6(6014)
留言20則, 6人參與, 最新討論串1/1
21. http://imgur.com/a/5eAI4 答案是 (C) 想請問 (a) 錯在哪 另外 (c) heap 的 merge 不是需要 O(n) 嗎 28. http://imgur.com/a/kqror 答案是 (C) 請問 (a) 錯在哪 謝謝 -- ◣▂ 丹丹先生,請問你對其他速食店降價 丹你老木! _ 心嘛? ▂▂▂ |════ ◤◤ ▁▃▃˙˙ ▇▇▇▇▇▇▇█ ╭═╮ █████ __ [TV] ██ ◥▆▄_◥██▄▃◢█◣ φjeans1020 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.116.1.136 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483425674.A.BAC.html

01/03 14:47, , 1F
左傾樹的定義只有左比右深 所以skew也算
01/03 14:47, 1F
喔喔喔喔喔喔喔,原來如此,太謝謝了 ※ 編輯: kyuudonut (140.116.1.136), 01/03/2017 14:49:43

01/03 14:53, , 2F
Leftist tree不是也是個Heap嗎?所以他不算是balanced ?
01/03 14:53, 2F

01/03 14:54, , 3F
28(a) Quick Sort應該根amortized沒什麼關係
01/03 14:54, 3F
對齁!qsort 的分析並沒有用到 amortized cost orz

01/03 14:54, , 4F
不算,Heap 要滿足 complete binary tree
01/03 14:54, 4F
※ 編輯: kyuudonut (140.116.1.136), 01/03/2017 14:57:50

01/03 14:57, , 5F
Heap 為 complete binary tree 有可能再考出來QQ
01/03 14:57, 5F

01/03 15:00, , 6F
對所以我的疑問是因為課本上都寫leftist tree又叫leftis
01/03 15:00, 6F

01/03 15:00, , 7F
t heap, 所以他沒有heap是個complete binary tree的性質
01/03 15:00, 7F

01/03 15:01, , 8F
嗎?我原本想說complete B.T應該會是balanced的
01/03 15:01, 8F

01/03 15:04, , 9F
28 amortized 不是算worst cast 嗎 ?
01/03 15:04, 9F

01/03 15:06, , 10F
             case
01/03 15:06, 10F

01/03 15:07, , 11F
阿阿我看到wiki了他說leftist tree is very unbalanced
01/03 15:07, 11F

01/03 15:07, , 12F
leftist tree 不是complete binary tree
01/03 15:07, 12F

01/03 15:31, , 13F
leftist tree + min tree(或max)就叫做leftist heap唷
01/03 15:31, 13F

01/03 15:31, , 14F
並不包含於heap 而以min tree看 他的合併是一直保留小的r
01/03 15:31, 14F

01/03 15:31, , 15F
oot的左子樹 右子樹再跟另一個樹合併 只要花O(logn)
01/03 15:31, 15F

01/03 15:32, , 16F
期間要check有無符合leftist tree的性質 沒有要swap
01/03 15:32, 16F
大大可以幫我看一下 (c) 嗎 ※ 編輯: kyuudonut (140.116.1.136), 01/03/2017 19:43:29

01/06 23:11, , 17F
因為c是在說leftest tree在insert的時候是將兩個tr
01/06 23:11, 17F

01/06 23:11, , 18F
ee做合併 因為是合併原樹與一個one node tree
01/06 23:11, 18F

01/06 23:13, , 19F
刪除就是拿掉min 之後合併左子右子,這題的重點是
01/06 23:13, 19F

01/06 23:13, , 20F
在說要知道他還在繼續問左傾樹
01/06 23:13, 20F
文章代碼(AID): #1OQqUAki (Grad-ProbAsk)