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