14

我了解二叉搜索树是如何实现的，但我不确定使用它相对于大多数编程语言已内置到其标准库中的哈希表有什么优势。

有人可以提供可以用二叉搜索树解决的现实问题的例子吗？

4

5 回答 5

31

与哈希表相比，二叉搜索树有一些理论上的优势：

  1. 他们按排序顺序存储元素。这意味着，如果您想以可以轻松按排序顺序访问值的方式存储容器，则 BST 可能是比哈希表更好的选择。例如，如果您想存储一组学生，然后按字母顺序打印出所有学生，那么 BST 是比散列表更好的选择。

  2. 它们有效地支持范围查询。因为 BST 是按排序顺序存储的，所以很容易回答“[x, y] 范围内的值是什么？”形式的问题。在二叉搜索树中。为此，您在树中查找大于 x 的最小元素和小于 y 的最大元素，然后遍历它们之间的树元素。这两个查询在平衡树中的运行时间为 O(lg n)，因此此操作的总运行时间为 O(lg n + k)，其中 k 是与查询匹配的元素数。

  3. 它们有效地支持最近邻查询。 哈希表是专门设计的，因此即使略有不同也会产生截然不同的哈希码。这为哈希值提供了它们需要的分散性，以避免在一个点聚集太多元素。但是，这也意味着您需要对哈希表进行线性扫描，以查找可能与您要查找的内容“接近”的元素。使用 BST，您可以有效地找到您想要的任何值的前任和后继，即使它不在树中。

  4. 他们可以有更好的最坏情况保证。大多数哈希表实现都有某种退化的情况，在最坏的情况下，操作可能会退化到 O(n)。线性探测哈希表或链式哈希表在元素集错误的情况下，每次查找需要 O(n) 时间，或者重新哈希需要 O(n) 时间。插入某些类型的平衡 BST，如红/黑树、AVL 树或 AA 树，总是最坏情况 O(lg n)。

如果您愿意将 BST 推广到更精细的树结构，那么在许多应用程序中，树可以比哈希表更有效地解决问题。这里有几个例子：

  1. kd-trees允许您存储多维数据，同时支持多维空间中的快速范围查询，以及高效的最近邻查找。您可以将它们用于分类（惰性学习算法）或计算几何。

  2. 链接/切割树可用于比大多数传统算法更有效地解决最大流量问题。好的推送/重新标记算法使用它来加速它们的实现。

  3. 不相交集森林可用于尽可能渐近有效地维护元素的分区（每次更新摊销 α(n)，其中 α(n) 是 Ackermann 反函数）。它们用于许多快速最小生成树算法，以及一些最大匹配算法。

  4. 二进制堆可用于有效地实现优先级队列。更复杂的树可以用来构建二项式堆和斐波那契堆，它们在理论计算机科学中非常重要。

  5. 决策树可用于机器学习进行分类，并作为理论计算机科学中的模型来证明各种算法运行时的界限。

  6. 三元搜索树是基于略微修改的 BST 的尝试的替代方案。它们允许非常快速地查找和插入元素，并且对于稀疏数据集非常简洁。

  7. 许多数据库系统使用B 树来有效地查找磁盘访问是限制因素的元素。

  8. 二进制空间分区树是 kd-trees 的推广，可用于快速渲染计算机图形（它们用于优化原始游戏 Doom 中的渲染）并进行碰撞检测。

  9. BK-trees允许您快速确定在某个其他单词的某个编辑距离内的所有单词，并且更一般地可以在某个其他点的某个距离内找到度量空间中的所有点。

  10. 融合树是整数键的哈希表的替代品，对查找、插入和删除具有极快的支持。

  11. van Emde Boas 树是整数键的另一种哈希表替代方案，它支持每个元素在 O(lg lg n) 时间内进行查找、插入、删除、后继和前驱。一些数据库系统使用 vEB 树来优化性能。

我不确定这个答案有多切题，但它应该让您了解 BST 和更通用的树结构是多么美妙和强大。

于 2011-02-16T00:05:29.443 回答
1

需要二叉树的一个例​​子是计算机图形学中的二进制空间分区

http://en.wikipedia.org/wiki/Binary_space_partitioning

需要二叉树，因为该算法需要保留二叉树中节点之间的关系。还有许多其他算法，树的结构很重要，因此哈希表不是合适的结构。

使用二叉树而不是哈希表的另一个很好的理由是当您无法轻松地为数据项生成有效的哈希时，但您可以生成比较函数。

通常，对于数据的简单存储和检索，哈希表更理想，但实现起来更复杂。

于 2011-02-15T23:53:30.240 回答
0

这可能应该是一个评论，但自平衡 BST(s)(log(n)) 被广泛使用，而不是 BST。普通 BST 具有最坏情况的 O(N) 插入/移除时间。

于 2011-02-16T02:14:19.943 回答
0

最容易被忽视的问题之一是许多文件系统使用二叉树来管理目录列表。他们很少使用普通的二叉树，而是使用一些变体，例如 B-tree。这是因为树的磁盘存储问题对于实现细节非常重要。他们使用这种结构的原因是为了提高效率和速度。这让他们可以做一些事情，比如支持目录中的数千个文件。文件创建和删除时间的比较突出了文件系统这方面的效率。

二叉树也用于许多渲染 3D 对象的游戏。再次，原因是速度。事实上，速度是如此重要，以至于某些游戏引擎（例如 Quake 引擎）实际上在地图构建过程中预先生成和优化了二叉树。

于 2011-02-15T23:56:41.517 回答
0

需要注意的一件事是二叉搜索树是节省空间的。例如，您有 10 个整数要存储，并且您有一个从 0 到 99 映射的哈希函数，那么您需要一个包含 100 个整数的数组。如果您使用二叉搜索树，那么您将只分配 10 个元素所需的内存

于 2011-02-15T23:57:49.750 回答