字典實現（平衡二進制搜索樹與哈希表）

Question

在什麼情況下使用平衡二叉搜索樹而不是散列表實現字典ADT會更好？

我的假設是，由於其自​​然順序，使用二叉搜索樹總是更好。

但是的確，哈希表的搜索時間可以和O（1），v.s一樣好。 O（logn）爲二叉樹。

所以我不確定環境會是什麼。

Answer 1

你的問題中已經包含了答案：

如果你不需要任何內在的順序，然後使用一個哈希表有更好的表現。如果您的需求需要某種訂購，請考慮使用樹。

Answer 2

哈希表填滿時需要重新分配內存（在硬實時系統環境中）時，哈希表可能會有性能問題。二叉樹不存在此問題。 哈希表需要比實際使用更多的內存，其中二叉樹使用盡可能多的內存。