[理工] 資結 關於Tree

看板Grad-ProbAsk作者時間8年前 (2018/01/17 14:04), 編輯推噓8(8推 0噓 13→)
留言21則, 7人參與, 8年前最新討論串1/1
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
推
01/17 14:12, 8年前 , 1F
(B) avl跟紅黑樹都是高度平橫樹，紅黑樹由root到leaf的
01/17 14:12, 1F
→
01/17 14:12, 8年前 , 2F
黑色子點個數都一樣
01/17 14:12, 2F
→
01/17 14:14, 8年前 , 3F
01/17 14:14, 3F
推
01/17 15:15, 8年前 , 4F
01/17 15:15, 4F
→
01/17 15:17, 8年前 , 5F
01/17 15:17, 5F
→
01/17 15:18, 8年前 , 6F
(C) 上面那張圖，維基找到的解釋
01/17 15:18, 6F
→
01/17 15:19, 8年前 , 7F
(D)如果是用資結的full tree定義去看的話
01/17 15:19, 7F
→
01/17 15:20, 8年前 , 8F
我反而覺得是false耶
01/17 15:20, 8F
→
01/17 15:20, 8年前 , 9F
(E)我覺得應該是因為每個node一開始宣告的大小就要比較大
01/17 15:20, 9F
→
01/17 15:25, 8年前 , 10F
所以大m的記憶體需求量會比小m還多
01/17 15:25, 10F
推
01/17 15:53, 8年前 , 11F
A O(1) 跟 O(lg n) 好像不衝突.. 該選什麼？
01/17 15:53, 11F
→
01/17 17:19, 8年前 , 12F
樓上對欸 但看起來要選 tightly bounded
01/17 17:19, 12F
→
01/17 22:41, 8年前 , 13F
看之前討論應該是 CDE
01/17 22:41, 13F
推
01/18 08:13, 8年前 , 14F
B false，紅黑樹最多高低差2倍，AVL高低差+-1
01/18 08:13, 14F
推
01/18 13:08, 8年前 , 15F
b false吧
01/18 13:08, 15F
推
01/18 21:20, 8年前 , 16F
B錯 R-B tree不用滿足balance的性質
01/18 21:20, 16F
推
01/18 21:23, 8年前 , 17F
E. 因為B-tree是用來做external sorting的，所以需要
01/18 21:23, 17F
→
01/18 21:23, 8年前 , 18F
一次從disk搬整個node上來，如果m(degree)變大，則一
01/18 21:23, 18F
→
01/18 21:23, 8年前 , 19F
次要搬的node大小就會變大
01/18 21:23, 19F
推
01/18 21:38, 8年前 , 20F
B. 抱歉有點說錯,AVL樹高最多1.44log(n+2) RB tree
01/18 21:38, 20F
→
01/18 21:38, 8年前 , 21F
樹高最多可到 2log(n+1)
01/18 21:38, 21F
‣ 更多 nova06091 的文章
文章代碼(AID): #1QNkTIHx (Grad-ProbAsk)