作者guanhao1370 (guanhao)
看板Grad-ProbAsk
標題[理工] [資結] 高等樹問題
時間Tue Nov 27 00:02:45 2018
https://imgur.com/ugnpZpC
https://imgur.com/IvluVNd
這一題我覺得(A)(B)(D)都對耶...
(C)是不用rotation嗎？
https://imgur.com/Zf5kVPn
https://imgur.com/l0pElCT
這題我這樣做對嗎？
我的解法：
https://imgur.com/sf2JZXV
https://imgur.com/EkmTbU0
https://imgur.com/9FfarSh
https://imgur.com/YRDZMBO
https://imgur.com/voQWXSC
這題的(a)為什麼是那樣呀？
https://imgur.com/voQWXSC
這是筆記裡寫的解法，不太懂為什麼Ci,j的公式會變成那樣呀？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.218.83.128
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1543248168.A.41A.html
1F：推 magic83v: 20步 p插錯地方11/27 02:08
2F：→ magic83v: 刪除也錯 degree要3-511/27 02:09
3F：推 FRAXIS: AVL deletion 最多要 O(lg n) 旋轉11/27 11:33
4F：→ FRAXIS: 同一題 A 和 B 選項應該都錯11/27 11:35
5F：→ FRAXIS: 你可以考慮固定點數 高度最大的 AVL tree (worst case)11/27 11:37
6F：→ guanhao1370: 謝謝，第32題我會了11/27 22:27
7F：→ guanhao1370: 第19題的(A)(B)為什麼錯呀？11/27 22:29
※ 編輯: guanhao1370 (49.218.83.128), 11/27/2018 22:30:31
8F：→ cossetannie: avl tree沒有那些定義吧 可以自己畫反例看看 11/28 01:28
9F：→ guanhao1370: AVL tree左右子樹高度差最多為一不是嗎？如果高度差 11/28 09:57
10F：→ guanhao1370: 大於等於二就必須做rotation，所以我覺得(A)(B)應該 11/28 09:57
11F：→ guanhao1370: 是對的 11/28 09:57
12F：推 FRAXIS: 問題是問同一層的高度差 不是問左右子樹高度差 11/28 11:26
13F：→ FRAXIS: 反例的構造方式我已經說了 你可以自己畫畫看 11/28 11:27