[理工] [資結] 高等樹問題

看板Grad-ProbAsk作者 (guanhao)時間7年前 (2018/11/27 00:02), 7年前編輯推噓3(3推 0噓 10→)
留言13則, 4人參與, 7年前最新討論串1/1
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1543248168.A.41A.html
推
11/27 02:08, 7年前 , 1F
20步 p插錯地方
11/27 02:08, 1F
→
11/27 02:09, 7年前 , 2F
刪除也錯 degree要3-5
11/27 02:09, 2F
推
11/27 11:33, 7年前 , 3F
AVL deletion 最多要 O(lg n) 旋轉
11/27 11:33, 3F
→
11/27 11:35, 7年前 , 4F
同一題 A 和 B 選項應該都錯
11/27 11:35, 4F
→
11/27 11:37, 7年前 , 5F
你可以考慮固定點數 高度最大的 AVL tree (worst case)
11/27 11:37, 5F
→
11/27 22:27, 7年前 , 6F
謝謝，第32題我會了
11/27 22:27, 6F
→
11/27 22:29, 7年前 , 7F
第19題的(A)(B)為什麼錯呀？
11/27 22:29, 7F
※ 編輯: guanhao1370 (49.218.83.128), 11/27/2018 22:30:31
→
11/28 01:28, 7年前 , 8F
avl tree沒有那些定義吧 可以自己畫反例看看
11/28 01:28, 8F
→
11/28 09:57, 7年前 , 9F
AVL tree左右子樹高度差最多為一不是嗎？如果高度差
11/28 09:57, 9F
→
11/28 09:57, 7年前 , 10F
大於等於二就必須做rotation，所以我覺得(A)(B)應該
11/28 09:57, 10F
→
11/28 09:57, 7年前 , 11F
是對的
11/28 09:57, 11F
推
11/28 11:26, 7年前 , 12F
問題是問同一層的高度差 不是問左右子樹高度差
11/28 11:26, 12F
→
11/28 11:27, 7年前 , 13F
反例的構造方式我已經說了 你可以自己畫畫看
11/28 11:27, 13F
‣ 更多 guanhao1370 的文章
文章代碼(AID): #1R_1aeGQ (Grad-ProbAsk)