[理工] 資結 關於Tree

[nova06091 ()]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1516169042.A.47B.html
推 q1qip123: (B) avl跟紅黑樹都是高度平橫樹，紅黑樹由root到leaf的
→ q1qip123: 黑色子點個數都一樣
→ q1qip123: http://i.imgur.com/4MF8xLx.jpg
推 kai3570: https://imgur.com/RQn5mrt
→ kai3570: https://imgur.com/RQn5mrt.jpg
→ kai3570: (C) 上面那張圖，維基找到的解釋
→ kai3570: (D)如果是用資結的full tree定義去看的話
→ kai3570: 我反而覺得是false耶
→ kai3570: (E)我覺得應該是因為每個node一開始宣告的大小就要比較大
→ kai3570: 所以大m的記憶體需求量會比小m還多
推 FRAXIS: A O(1) 跟 O(lg n) 好像不衝突.. 該選什麼？
→ nova06091: 樓上對欸  但看起來要選 tightly bounded
→ nova06091: 看之前討論應該是 CDE
推 ping780520: B false，紅黑樹最多高低差2倍，AVL高低差+-1
推 Dora5566: b false吧
推 PunchShadow: B錯 R-B tree不用滿足balance的性質
推 PunchShadow: E. 因為B-tree是用來做external sorting的，所以需要
→ PunchShadow: 一次從disk搬整個node上來，如果m(degree)變大，則一
→ PunchShadow: 次要搬的node大小就會變大
推 PunchShadow: B. 抱歉有點說錯,AVL樹高最多1.44log(n+2) RB tree
→ PunchShadow:  樹高最多可到 2log(n+1)