BST相对于哈希表的优势

哈希表 在Θ（1）时间内支持以下操作。 1） 搜索 2） 插入 3） 删除

在一个自平衡模型中，上述操作的时间复杂性 二叉搜索树（BST） （比如 红黑树 , 平衡二叉树 , 八字树 等）是O（Logn）。

所以哈希表似乎在所有常见的操作中都优于BST。什么时候我们应该选择BST而不是哈希表，优势是什么。以下是支持BST的一些要点。

1. 我们只需按顺序遍历BST就可以获得所有按顺序排列的密钥。这不是哈希表中的自然操作，需要额外的努力。
2. 做 订单统计 , 寻找最接近的较低和较大元素 , 做范围查询 使用BST很容易。与排序一样，这些操作不是哈希表的自然操作。
3. 与哈希相比，BST易于实现，我们可以轻松实现自己定制的BST。要实现哈希，我们通常依赖编程语言提供的库。
4. 使用自平衡BST，所有操作都保证在O（Logn）时间内工作。但对于散列，Θ（1）是平均时间，一些特定的操作可能代价高昂，尤其是在调整表大小时。

本文由 希曼舒古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论