二叉搜索樹，2-3樹和B-樹的用法，優缺點

Question

我在回顧我的數據結構類中的材料，我對這三種樹的用法感到困惑。那麼我們應該如何更好地使用二叉搜索樹，2-3樹和B樹？有什麼優點和缺點？

太謝謝你了！我對數據結構的東西很陌生...

Answer 1

所有這三種結構都是有序字典的實現 - 它們在維持一個集合的同時有效地支持插入，刪除，查找，後繼和前驅查詢。

二叉搜索樹和2-3樹與B樹不同，BST和2-3樹是（通常）主存數據結構，而B樹是（通常）外部存儲器數據結構。具體而言，B樹被設計爲存儲在讀取或寫入磁盤頁面的成本顯着高於執行簡單計算的成本的磁盤上。如果您計劃存儲大量不適合主內存的數據，則B樹是數據結構的絕佳選擇。另一方面，在主存中，具有非常大的分支因子的B樹將比BST或2-3樹更慢，因爲每個B樹插入或刪除可能需要大量的指針重新分配。對於符合主內存的數據集，2-3樹和BSTs通常是優越的選擇（儘管有一些研究表明，由於緩存效應，低階B樹可以在主內存中勝過BSTs）。

至於BST和2-3樹：「二叉搜索樹」不是一個單一的數據結構。有沒有平衡的純BST，紅/黑樹，AVL樹，AA樹，張角樹，treaps，替罪羊樹，重量平衡樹，RAVL樹等等。這些數據結構中的每一個試圖使用一些規則來平衡BST所以查找，插入和刪除都很快。 2-3樹是BST的一個變種，它允許每個節點有多個密鑰，以便爲維持平衡提供簡單的規則。這個問題通常不會是「什麼時候BST比2-3樹好，反之亦然」和「2-3樹相比其他平衡BST有什麼優勢，反之亦然」，這是一個問題你必須通過分析來弄清楚。

希望這有助於！