作者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/cn.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