[理工] [資結] 高等樹

[QoiiwWe (台GO)]

1.
T or F
All B-tree of order 2 are full binary trees.
洪逸答案給True 可是我覺得是False耶
不保證一定full吧~?

2. 用AVL Tree跟Hash Table哪種DS較好?

a.high insertion rate
  high search rate
  high printing rate

b.low insertion rate
  high search rate
  very low printing rate

我是覺得都Hash Table較好
但洪逸答案給b是AVL Tree
為什麼呢?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.126.29.52
推 cksh3300110:1是對的 這個在原文書11.2 B-TREE上有講到
推 cksh3300110:2 A是因為插入機率很高用AVLTREE每次都要O(logn)
→ cksh3300110:比起hash只有O(1)的時間
→ cksh3300110:b是因為搜尋用AVL 只需O(logn) 但是HASH可能會發生
→ cksh3300110:collision而需要花到O(N)的時間
→ QoiiwWe:謝謝樓上 沒有想到collision@@
推 FRAXIS:照這樣講，Hash Table做insert也會collision..
→ FRAXIS:也是會變成O(n)  Hash Table有一個缺點是很難inorder印出
→ FRAXIS:或許這是他列出print rate的原因..
推 st84514:我覺得若以hash碰撞的角度來看這題不好區分是該用哪種
→ st84514:a常作insert屬於data unstable的情形應該不適合用於hash
→ sneak: 或許這是他列出prin https://daxiv.com