我目前正在学习不同的数据结构，但遇到了一个小问题。使用二叉搜索树实现的有序映射有什么用？我的意思是，什么时候这样做比较好？一个实际的例子就太好了!
最佳答案
平衡 BST 有大量不同的用例，我不可能在这里列出所有这些用例，但这里有一些很好的用例:
BST 支持范围查询，您可以在其中高效地查询两个值之间的所有条目。具体来说，在具有 n 个条目的 BST 中，如果执行将返回 k 个元素的范围查询，则运行时间为 O(log n + k)。与使用哈希表相比，运行时间为 O(n)。如果您有兴趣对一组数据进行时间序列分析并希望探索特定范围内的数据，则可以使用此方法。
BST 支持后继和先行查询。给定 BST，您可以在时间 O(log n) 内要求大于某个值的最小元素或小于某个值的最大元素。总的来说，这可以让您在时间 O(log n) 内找到 BST 中最接近某个目标值的元素，如果您获得噪声数据并希望将其映射到数据集中最接近的条目，这会很有用。将此与哈希表进行比较，这需要时间 O(n)。
BST 在最坏情况下效率。许多常见类型的二叉搜索树，例如红/黑树和 AVL 树，都对其操作成本提供了最坏情况的保证。将此与哈希表进行对比，其中查询预计需要恒定的时间，但可能会因错误的哈希函数或仅仅由于运气不好而降低性能。此外，哈希表时不时地需要重新哈希，这可能需要一段时间，但红/黑树和 AVL 树没有这样的情况。 (有些类型的平衡 BST，如伸展树(Splay Tree)和替罪羊树，在最坏情况下效率不高，但这是一个不同的故事。)
即使插入和删除混合在一起，BST 也可以在 O(log n) 时间内轻松访问最小值和最大值。哈希表不支持这些操作。
BST 支持有序迭代，因此，如果您有一个应用程序想要按排序顺序查看数据，则可以通过 BST“免费”获得它。例如，如果您正在加载学生数据并希望按排序顺序查看分数，就是这样的一个例子。哈希表不支持这一点 - 您必须提取数据并对其进行排序才能按排序顺序恢复。
BST 可以增强。如果您学习算法类(class)，您可能会学习一种称为树增强的技术，在该技术中，您可以在 BST 的每个节点中添加额外的信息，以比最初看起来更快的速度解决大量问题。例如，您可以增强 BST，以便能够立即读取中值元素或最接近的点对，或者在基础数据发生更改时有效地解决许多算法问题。哈希表不支持这些操作。
BST 支持高效的拆分和连接。红/黑树和拉伸(stretch)树有一个有趣的特性，即给定两棵树，其中一棵树的所有键都小于另一棵树的键，这些树可以在时间 O(log n) - 多的时间内组合在一起形成一棵树比访问树的所有元素还要快!您还可以通过在时间 O(log n) 内将树划分为“小于某个值的元素”或“大于某个值的元素”，将任何红/黑树或伸展树(Splay Tree)拆分为两棵较小的树。做到这一点并不简单，但这是可能的。哈希表上相应操作的时间范围为 O(n)。
如果我想到其他任何事情，我会更新此列表。希望这有帮助!
关于data-structures - 使用二叉搜索树的有序映射的实用性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37379735/