logo标签列表

使用二叉搜索树的具体示例？

data-structurestreehashtablebinary-search-tree
15

我了解二叉搜索树的实现方式，但我不确定使用它相比于大多数编程语言标准库中内置的哈希表有何优势。

有人能举出一些二叉搜索树可以解决的真实问题的例子吗？

可能是二叉树的应用有哪些？的重复问题。 - nawfal
5个回答
32

二叉搜索树相对哈希表具有以下几个理论优势：

  1. 它们以排序的方式存储其元素。这意味着，如果你想以一种容易按排序顺序访问值的方式来存储容器，那么二叉搜索树可能比哈希表更好。例如，如果你想存储一个学生集合并按字母顺序打印出所有学生，那么使用二叉搜索树比哈希表要好得多。

  2. 它们有效地支持区间查询。由于二叉搜索树以排序的方式存储，因此可以很容易地回答形如“在[x，y]范围内的值是什么？”的问题。为了实现这一点，在树中查找大于x的最小元素和小于y的最大元素，然后迭代它们之间的树元素。在平衡树中，这两个查询都以O(lg n)时间运行，因此这个操作的总运行时间是O(lg n + k)，其中k是匹配查询的元素数量。

  3. 它们有效地支持最近邻查询。哈希表专门设计成即使是稍微不同的东西也会产生截然不同的哈希码。这使得哈希值具有避免在一个地方聚集太多元素所需的分散性。然而，这也意味着你需要在哈希表上进行线性扫描，以查找可能与你要查找的内容“接近”的元素。使用二叉搜索树，你可以有效地找到任何你想要的值的前驱和后继，即使它不在树中。

  4. 它们可以提供更好的最坏情况保证。大多数哈希表实现都有某种退化情况，在这种情况下操作最坏情况下可能会退化为O(n)。具有均衡性质的某些类型的平衡二叉搜索树，如红黑树、AVL树或AA树，插入始终是最坏情况下的O(lg n)。

如果你愿意将BST泛化为更复杂的树结构，那么有很多应用场景可以使用树来比哈希表更高效地解决问题。以下是一些例子：

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

  2. Link/cut tree 可以用于比大多数常规算法更高效地解决最大流问题。好的推/重标记算法使用此方法来加速实现。

  3. Disjoint-set forests 可以用于尽可能高效地维护元素的分区（每次更新的摊销时间为α(n)，其中α(n)是Ackermann逆函数）。它们在许多快速最小生成树算法以及一些最大匹配算法中被使用。

  4. Binary heaps 可以用于有效地实现优先级队列。更复杂的树可用于构建二项堆和斐波那契堆，这在理论计算机科学中具有重要意义。

  5. Decision trees 可以用于机器学习中的分类，并作为理论计算机科学中证明各种算法运行时间上限的模型。

  6. Ternary search trees 是trie的一种替代方案，基于稍微修改过的BST。它们允许非常快速地查找和插入元素，并且对于稀疏数据集非常简洁。

  7. B-trees 被许多数据库系统用于在磁盘访问是限制因素的情况下高效地查找元素。

  8. Binary space partitioning trees 是kd-tree的一种泛化形式，可用于快速渲染计算机图形（它们被用于优化原始游戏“毁灭战士”的渲染）和执行碰撞检测。

  • BK树允许您快速确定与其他单词在某个编辑距离内的所有单词，更一般地，在某个距离内查找度量空间中的所有点。

  • 融合树是整数键的哈希表的替代品，具有非常快的支持查找、插入和删除的功能。

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

    • 我不确定这个答案是否与主题相关，但它应该让您了解到BST以及更一般的树结构可以是多么美妙和强大。

    1

    二叉树被需要的一个例子是在计算机图形学中的二叉空间分割。

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

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

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

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

    0

    最常被忽视的是，许多文件系统使用二叉树来管理目录列表。它们很少使用简单的二叉树，而是采用一些变体，如B树。这是因为磁盘存储树的问题对于实现的细节非常重要。它们使用这种结构的原因是为了效率和速度。这使它们能够支持一个目录中的数千个文件。文件创建和删除时间的比较突出了文件系统这个方面的效率。

    二叉树也被用于渲染3D对象的许多游戏中。同样，原因是速度。事实上，速度非常重要，以至于一些游戏引擎，如Quake引擎，实际上已经在地图构建过程中预先生成和优化了二叉树。

    0
    需要注意的一点是二叉搜索树具有高效的空间利用率。例如，如果您有10个整数要存储，并且有一个哈希函数将其映射到0-99，则需要一个包含100个整数的数组。 如果使用二叉搜索树，则只需分配10个元素所需的内存即可。
    0
    这应该是一个注释，但是自平衡二叉搜索树(log(n))比普通的二叉搜索树(BSTs)更广泛地使用。纯粹的二叉搜索树(BSTs)在插入/删除时具有最坏情况O(N)的时间复杂度。
    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接