1) 时间复杂度
发现跟成大某题一样类型
就直接问这题好了
https://i.imgur.com/iuZWgA7.jpg
https://i.imgur.com/X7ryees.jpg
解答看不太懂
他画的递回树是n^2>M的情况吗？
为什么第二层是16c
而不是16*c/2=8c
那为什么n^2<=M的情况就不用管了？
2)
https://i.imgur.com/SdZScFH.jpg
(c)小题
画一个最少结点的AVL Tree
Ok! 但之后要填入红黑树就不太明白了
所以就是随便画
只要符合就好了吗？
例如
https://i.imgur.com/xknYcCW.jpg
还是有规则吗？
3)
https://i.imgur.com/ushGfR4.jpg
https://i.imgur.com/q8dZgAy.jpg
(a)这题应该是要写计算过程吧？
用看的应该拿不到分数？
解法应该是用Floyd-Warshall做4次
可是9*9矩阵好像有点大XD
请问有别的作法吗？

对 就是有那个性质的红黑树即可网址被截掉了QQhttps://www.ptt.cc/bbs/Grad-ProbAsk/M.1479362612.A.90A.html上面两行麻烦加在一起xDD

谢谢 我研究一下

2.c 之前版上有人解不同的答案，我也还在困惑https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479362612.4.c 就只要满足Smallest height 3 AVL tree即可5.a 我是用Dijkstra 先解出最短path，再带入限制条件把(E,G)、(G,H)换成(E,H)5.a 说错，替换结果应该是(A,D)换(A,B)+(B,D)

5.a 用bellman 做4次？成大复杂度那题我算O(n^4/M)

对是Bellman我搞错了XDD

2c 确保root到所有leaf经过的黑node数一样、没有连续两颗红node相连就行1 因为他分割成16个子问题，每个子问题需时theta(1)，加总就是16c