使用二叉搜索树的有序映射的实用程序
Utility of an ordered map using binary search tree
我目前正在学习不同的数据结构，但遇到了一些小问题。使用二叉搜索树实现的有序映射有什么用？我的意思是，什么时候这样做比较好？一个实际的例子会很棒！
平衡 BST 有 吨 种不同的用例，我不可能在这里列出所有这些，但这里有一些很好的用例：
BST 支持范围查询，您可以在其中高效地查询两个值之间的所有条目。具体来说，在具有 n 个条目的 BST 中，如果执行将返回 k 个元素的范围查询，则运行时间为 O(log n + k)。将其与使用哈希 table 进行比较，其中运行时间为 O(n)。如果您有兴趣对一组数据进行时间序列分析并希望探索特定范围内的数据，则可以使用此工具。
BST 支持 后继和先行 查询。给定一个 BST，您可以在时间 O(log n) 中要求大于某个值的最小元素或小于某个值的最大元素。总的来说，这可以让您在时间 O(log n) 中找到 BST 中最接近某个目标值的元素，如果您正在获取嘈杂的数据并希望将其映射到数据集中最接近的条目，这将很有用。将此与散列 tables 进行比较，这将花费时间 O(n).
BST 是最坏情况下的效率。许多常见类型的二叉搜索树，如 red/black 树和 AVL 树，对其操作成本提供最坏情况保证。将此与哈希 table 进行对比，其中查询 预期 需要固定时间，但可能会因哈希函数不佳或运气不佳而降级。此外，散列 table 有时必须重新散列，这可能需要一段时间，但 red/black 树和 AVL 树没有这样的情况。 （有一些类型的平衡 BST，如 splay 树和替罪羊树，它们在最坏情况下不是有效的，但这是另一回事。）
BST 可以在时间 O(log n) 内轻松访问 最小值和最大值，即使插入和删除是混合的。哈希 tables 不支持这些操作。
BST 支持有序迭代，因此如果您有一个应用程序希望按排序顺序查看数据，就可以做到"for free"与 BST。举个例子，如果您正在加载学生数据并希望按排序顺序查看分数。哈希 tables 不支持此功能 - 您必须提取数据并对其进行排序才能按排序顺序取回。
BST 可以增强。如果你参加了算法课程，你可能会了解一种称为树扩充的技术，你可以在 BST 的每个节点中添加额外的信息，以比最初看起来更快的速度解决大量问题。例如，您可以扩充 BST 以立即读取中值元素或最近的一对点，或者在基础数据发生变化时有效地解决许多算法问题。哈希 table 不支持这些操作。
BST 支持有效的拆分和合并。 Red/black 树和 splay 树有一个有趣的 属性 ，给定两棵树，其中一棵的所有键都小于另一棵的键，树可以及时组合成一棵树 O (log n) - 比访问树的所有元素快得多！您还可以通过在时间 O(log n) 中将树划分为 "elements less than some value" 或 "elements more than some value" 来将任何 red/black 树或 splay 树分成两棵较小的树。这不是微不足道的，但它是可能的。哈希 table 上相应操作的时间范围是 O(n).
如果我想到什么，我会更新此列表。希望这对您有所帮助！
我目前正在学习不同的数据结构，但遇到了一些小问题。使用二叉搜索树实现的有序映射有什么用？我的意思是，什么时候这样做比较好？一个实际的例子会很棒！
平衡 BST 有 吨 种不同的用例，我不可能在这里列出所有这些，但这里有一些很好的用例：
BST 支持范围查询，您可以在其中高效地查询两个值之间的所有条目。具体来说，在具有 n 个条目的 BST 中，如果执行将返回 k 个元素的范围查询，则运行时间为 O(log n + k)。将其与使用哈希 table 进行比较，其中运行时间为 O(n)。如果您有兴趣对一组数据进行时间序列分析并希望探索特定范围内的数据，则可以使用此工具。
BST 支持 后继和先行 查询。给定一个 BST，您可以在时间 O(log n) 中要求大于某个值的最小元素或小于某个值的最大元素。总的来说，这可以让您在时间 O(log n) 中找到 BST 中最接近某个目标值的元素，如果您正在获取嘈杂的数据并希望将其映射到数据集中最接近的条目，这将很有用。将此与散列 tables 进行比较，这将花费时间 O(n).
BST 是最坏情况下的效率。许多常见类型的二叉搜索树，如 red/black 树和 AVL 树，对其操作成本提供最坏情况保证。将此与哈希 table 进行对比，其中查询 预期 需要固定时间，但可能会因哈希函数不佳或运气不佳而降级。此外，散列 table 有时必须重新散列，这可能需要一段时间，但 red/black 树和 AVL 树没有这样的情况。 （有一些类型的平衡 BST，如 splay 树和替罪羊树，它们在最坏情况下不是有效的，但这是另一回事。）
BST 可以在时间 O(log n) 内轻松访问 最小值和最大值，即使插入和删除是混合的。哈希 tables 不支持这些操作。
BST 支持有序迭代，因此如果您有一个应用程序希望按排序顺序查看数据，就可以做到"for free"与 BST。举个例子，如果您正在加载学生数据并希望按排序顺序查看分数。哈希 tables 不支持此功能 - 您必须提取数据并对其进行排序才能按排序顺序取回。
BST 可以增强。如果你参加了算法课程，你可能会了解一种称为树扩充的技术，你可以在 BST 的每个节点中添加额外的信息，以比最初看起来更快的速度解决大量问题。例如，您可以扩充 BST 以立即读取中值元素或最近的一对点，或者在基础数据发生变化时有效地解决许多算法问题。哈希 table 不支持这些操作。
BST 支持有效的拆分和合并。 Red/black 树和 splay 树有一个有趣的 属性 ，给定两棵树，其中一棵的所有键都小于另一棵的键，树可以及时组合成一棵树 O (log n) - 比访问树的所有元素快得多！您还可以通过在时间 O(log n) 中将树划分为 "elements less than some value" 或 "elements more than some value" 来将任何 red/black 树或 splay 树分成两棵较小的树。这不是微不足道的，但它是可能的。哈希 table 上相应操作的时间范围是 O(n).
如果我想到什么，我会更新此列表。希望这对您有所帮助！