作者nova06091 ()
看板Grad-ProbAsk
标题[理工] 资结 关於Tree
时间Wed Jan 17 14:04:00 2018
http://i.imgur.com/3UTbIBn.jpg
(A)false. 不论single 或 double rotation都是O(1)
(B) 不知道...
(C)True
(D)True
(E)不知道，m变大则搜寻次数变少(True)，记忆体耗费会如何呢？
求开释
-----
Sent from JPTT on my Asus ASUS_Z017DA.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 49.214.32.112
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1516169042.A.47B.html
1F：推 q1qip123: (B) avl跟红黑树都是高度平横树，红黑树由root到leaf的 01/17 14:12
2F：→ q1qip123: 黑色子点个数都一样 01/17 14:12
6F：→ kai3570: (C) 上面那张图，维基找到的解释 01/17 15:18
7F：→ kai3570: (D)如果是用资结的full tree定义去看的话 01/17 15:19
8F：→ kai3570: 我反而觉得是false耶 01/17 15:20
9F：→ kai3570: (E)我觉得应该是因为每个node一开始宣告的大小就要比较大 01/17 15:20
10F：→ kai3570: 所以大m的记忆体需求量会比小m还多 01/17 15:25
11F：推 FRAXIS: A O(1) 跟 O(lg n) 好像不冲突.. 该选什麽？ 01/17 15:53
12F：→ nova06091: 楼上对欸 但看起来要选 tightly bounded 01/17 17:19
13F：→ nova06091: 看之前讨论应该是 CDE 01/17 22:41
14F：推 ping780520: B false，红黑树最多高低差2倍，AVL高低差+-1 01/18 08:13
15F：推 Dora5566: b false吧 01/18 13:08
16F：推 PunchShadow: B错 R-B tree不用满足balance的性质 01/18 21:20
17F：推 PunchShadow: E. 因为B-tree是用来做external sorting的，所以需要 01/18 21:23
18F：→ PunchShadow: 一次从disk搬整个node上来，如果m(degree)变大，则一 01/18 21:23
19F：→ PunchShadow: 次要搬的node大小就会变大 01/18 21:23
20F：推 PunchShadow: B. 抱歉有点说错,AVL树高最多1.44log(n+2) RB tree 01/18 21:38
21F：→ PunchShadow: 树高最多可到 2log(n+1) 01/18 21:38