使用二叉搜索树的具体例子？ [英] Concrete examples of using binary search trees?

问题描述

我了解如何实现二叉搜索树，但是我不知道使用它的优势是将大多数编程语言内置到其标准库中的哈希表有哪些优点。

/ p>

解决方案

有一些理论上有一些理论上可以解释的真实问题的例子二进制搜索树在哈希表中的优点：

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. 链接/切割树可用于解决最大-flow问题比大多数常规算法更有效。好的推/重新标记算法使用它来加快其实现。




3. Disjoint-set forest 可用于维护元素分区尽可能渐近地有效地（每更新一次分摊α（n），其中α（n）是Ackermann逆函数）。它们用于许多快速的最小生成树算法以及一些最大匹配算法。




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




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




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




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




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




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




10. Fusion树是可以非常快速地支持查询，插入和删除的整数键的哈希表的替代方法。




11. van Emde Boas树另一个改变对于支持每个元素的O（lg lg n）时间内的查找，插入，删除，后继和前导的整数密钥的本地哈希表。一些数据库系统使用vEB树来优化性能。

我不知道这个答案的主题如何，但它应该给你一个感觉，如何美妙和强大的BST和更一般的树结构可以。

I understand how binary search trees are implemented, but I am not sure what are the advantages of using it over the hash tables that most programming languages have built into their standard libraries.

Could someone please provide examples of real-world problems solvable with binary search trees?

解决方案

There are a few theoretical advantages of binary search trees over hash tables:

1. They store their elements in sorted order. This means that if you want to store the container in a way where you can easily visit the values in sorted order, a BST is probably a better choice than a hash table. For example, if you want to store a collection of students and then print out all the students in alphabetical order, a BST is a substantially better choice than a hash table.

2. They efficiently support range queries. Because BSTs are stored in sorted order, it's easy to answer questions of the form "what values are in the range [x, y]?" in a binary search tree. To do this, you do a lookup in the tree for the smallest element greater than x and the greatest element smaller than y, then iterate over the elements of the tree between them. Both of these queries run in O(lg n) time in a balanced tree, so the total runtime for this operation is O(lg n + k), where k is the number of elements matching the query.

3. They efficiently support nearest-neighbor queries. Hash tables are specifically designed so that even slightly different produce wildly different hash codes. This gives the hash values the dispersion they need to avoid clustering too many elements in one spot. However, it also means that you need to do a linear scan over the hash table to find elements that might be "close" to what you're looking for. With a BST, you can efficiently find the predecessor and successor of any value you'd like, even if it's not in the tree.

4. They can have better worst-case guarantees. Most hash table implementations have some sort of degenerate case in which an operation can degrade to O(n) in the worst-case. A linear probing hash table or a chained hash table can, with a bad set of elements, require O(n) time per lookup or require O(n) time on a rehash. Insertion into some types of balanced BSTs, like red/black trees, AVL trees, or AA trees, is always worst-case O(lg n).

If you're willing to generalize BSTs to more elaborate tree structures, then there are many applications in which a tree can be used to solve problems much more efficiently than in a hash table. Here's a few examples:

1. kd-trees allow you to store multidimensional data while supporting fast range queries in multidimensional space, as well as efficient nearest-neighbor lookups. You can use them for classification (lazy learning algorithms) or computational geometry.

2. Link/cut trees can be used to solve max-flow problems much more efficiently than most conventional algorithms would allow. Good push/relabel algorithms use this to speed up their implementations.

3. Disjoint-set forests can be used to maintain partitions of elements as asymptotically efficiently as possible (amortized α(n) per update, where α(n) is the Ackermann inverse function). They're used in many fast minimum-spanning tree algorithms, as well as some maximum-matching algorithms.

4. Binary heaps can be used to implement priority queues efficiently. More complex trees can be used to build binomial heaps and Fibonacci heaps, which are of great importance in theoretical computer science.

5. Decision trees can be used in machine learning for classification, and as a model in theoretical computer science to prove bounds on the runtimes of various algorithms.

6. Ternary search trees are an alternative to tries that are based on as slightly modified BST. They allow for very fast lookup and insertion of elements and for sparse data sets are quite concise.

7. B-trees are used by many database systems to efficiently look up elements where disk access is a limiting factor.

8. Binary space partitioning trees are a generalization of kd-trees that can be used to quickly render computer graphics (they were used to optimize rendering in the original game Doom) and do collision-detection.

9. BK-trees allow you to quickly determine all words that are within a certain edit distance of some other word, and more generally to find all points in a metric space within a certain distance of some other point.

10. Fusion trees are an alternative to hash tables for integer keys that have extremely fast support for lookups, insertions, and deletions.

11. van Emde Boas trees another alternative to hash tables for integer keys that support lookup, insertion, deletion, successor, and predecessor in O(lg lg n) time per element. Some database systems use vEB trees to optimize performance.

I'm not sure how on-topic this answer is, but it should give you a sense for how wonderful and powerful BSTs and more general tree structures can be.

这篇关于使用二叉搜索树的具体例子？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！