2

我目前正在学习不同的数据结构，我面临一个小问题。使用二叉搜索树实现的有序映射有什么用？我的意思是，什么时候这样做比较好？一个实际的例子会很棒！

4

1 回答 1

2

平衡BST有很多不同的用例，我不可能在这里列出所有的用例，但这里有一些很好的用例：

  1. BST 支持范围查询，您可以在其中高效地查询两个值之间的所有条目。具体来说，在具有 n 个条目的 BST 中，如果您执行将返回 k 个元素的范围查询，则运行时间为 O(log n + k)。将其与使用哈希表进行比较，其中运行时间为 O(n)。如果您有兴趣对一组数据进行时间序列分析并希望探索特定范围内的数据，则可以使用此选项。

  2. BST 支持后继和前继查询。给定一个 BST，您可以要求在时间 O(log n) 中大于某个值的最小元素或小于某个值的最大元素。总的来说，这使您可以在 O(log n) 时间内找到 BST 中最接近某个目标值的元素，如果您正在获取嘈杂的数据并希望将其映射到数据集中最近的条目，这将很有用。将此与哈希表进行比较，这将花费时间 O(n)。

  3. BST 在最坏情况下是有效的。许多常见类型的二叉搜索树，如红/黑树和 AVL 树，都为其操作成本提供了最坏情况的保证。将此与哈希表进行对比，在该哈希表中，查询预计会花费恒定的时间，但可能会因哈希函数不佳或运气不佳而降级。此外，有时必须重新哈希表，这可能需要一段时间，但红/黑树和 AVL 树没有这样的情况。（有一些平衡的 BST 类型，例如分叉树和替罪羊树，它们在最坏情况下的效率并不高，但那是另一回事。）

  4. BST 可以在 O(log n) 时间内轻松访问最小值和最大值，即使插入和删除是混合的。哈希表不能支持这些操作。

  5. BST 支持有序迭代，因此如果您有一个应用程序想要按排序顺序查看数据，您可以使用 BST“免费”获得它。例如，如果您正在加载学生数据并希望按排序顺序查看分数，则可以举一个例子。哈希表不支持这一点 - 您必须提取数据并对其进行排序才能按排序顺序返回。

  6. BST 可以增强。如果您参加算法课程，您可能会了解一种称为树增强的技术，在该技术中，您可以在 BST 的每个节点中添加额外信息，以比最初看起来可能的速度更快地解决大量问题。例如，您可以增强 BST 以立即读取中值元素或最近的一对点，或者在基础数据发生更改时有效地解决许多算法问题。哈希表不支持这些操作。

  7. BST 支持高效的 split 和 join。红/黑树和展开树有一个有趣的特性，给定两棵树，其中一个中的所有键都小于另一个中的键，这些树可以在时间 O(log n) 内组合成一棵树 - 很多比访问树的所有元素更快！您还可以通过在时间 O(log n) 内将树划分为“小于某个值的元素”或“大于某个值的元素”，将任何红/黑树或展开树拆分为两个较小的树。做到这一点并非易事，但这是可能的。哈希表上相应操作的时间界限是 O(n)。

如果我想到其他任何事情，我会更新此列表。希望这可以帮助！

于 2016-05-22T22:12:14.637 回答