作者QoiiwWe (台GO)
看板Grad-ProbAsk
標題[理工] [資結] 高等樹
時間Sat Jan 29 00:46:13 2011
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
1F:推 cksh3300110:1是對的 這個在原文書11.2 B-TREE上有講到 01/29 01:12
2F:推 cksh3300110:2 A是因為插入機率很高用AVLTREE每次都要O(logn) 01/29 01:16
3F:→ cksh3300110:比起hash只有O(1)的時間 01/29 01:17
4F:→ cksh3300110:b是因為搜尋用AVL 只需O(logn) 但是HASH可能會發生 01/29 01:18
5F:→ cksh3300110:collision而需要花到O(N)的時間 01/29 01:18
6F:→ QoiiwWe:謝謝樓上 沒有想到collision@@ 01/29 09:54
7F:推 FRAXIS:照這樣講,Hash Table做insert也會collision.. 01/29 11:46
8F:→ FRAXIS:也是會變成O(n) Hash Table有一個缺點是很難inorder印出 01/29 11:47
9F:→ FRAXIS:或許這是他列出print rate的原因.. 01/29 11:47
10F:推 st84514:我覺得若以hash碰撞的角度來看這題不好區分是該用哪種 01/29 21:42
11F:→ st84514:a常作insert屬於data unstable的情形應該不適合用於hash 01/29 21:43