Sam*_*ang 14 tree hashtable binary-search-tree data-structures
我理解二叉搜索树是如何实现的,但我不确定在大多数编程语言已经内置到其标准库中的哈希表中使用它有什么好处.
有人可以提供二叉搜索树可解决的现实问题的例子吗？
tem*_*def 30
二进制搜索树比哈希表有一些理论上的优势:
它们按排序顺序存储元素.这意味着如果您希望以可以按排序顺序轻松访问值的方式存储容器,则BST可能是比哈希表更好的选择.例如,如果您想存储一组学生,然后按字母顺序打印出所有学生,那么BST是一个比哈希表更好的选择.
它们有效地支持范围查询.因为BST按排序顺序存储,所以很容易回答"什么值在[x,y]范围内？"形式的问题.在二叉搜索树中.为此,在树中查找大于x的最小元素和小于y的最大元素,然后迭代它们之间的树的元素.这两个查询都在O(lg n)时间内在平衡树中运行,因此此操作的总运行时间为O(lg n + k),其中k是与查询匹配的元素数.
它们有效地支持最近邻居查询. 哈希表是专门设计的,即使稍微不同也会产生完全不同的哈希码.这为散列值提供了它们所需的分散,以避免在一个点中聚集太多元素.但是,这也意味着您需要对哈希表进行线性扫描,以找到可能与您要查找的内容"接近"的元素.使用BST,您可以有效地找到您想要的任何值的前任和后继,即使它不在树中.
他们可以有更好的最坏情况保证.大多数哈希表实现都有某种退化情况,在最坏的情况下,操作可能会降级为O(n).线性探测哈希表或链式哈希表可以使用错误的元素集,每次查找需要O(n)时间或在重新散列时需要O(n)时间.插入某些类型的平衡BST,如红/黑树,AVL树或AA树,总是最坏情况O(lg n).
如果您愿意将BST推广到更复杂的树结构,那么有许多应用程序可以使用树来比哈希表更有效地解决问题.以下是一些例子:
kd-tree允许您存储多维数据,同时支持多维空间中的快速范围查询,以及有效的最近邻查找.您可以将它们用于分类(惰性学习算法)或计算几何.
链接/切割树可以用于比大多数传统算法允许的更有效地解决最大流问题.好的push/relabel算法使用它来加速它们的实现.
可以使用不相交集森林来尽可能渐近地有效地维护元素的分区(每次更新分摊α(n),其中α(n)是阿克曼逆函数).它们用于许多快速最小生成树算法,以及一些最大匹配算法.
二进制堆可用于有效地实现优先级队列.更复杂的树可用于构建二项式堆和斐波纳契堆,这在理论计算机科学中非常重要.
决策树可以用于机器学习中进行分类,也可以作为理论计算机科学中的模型来证明各种算法运行时的界限.
三元搜索树是基于稍微修改的BST的尝试的替代方案.它们允许非常快速地查找和插入元素,并且对于稀疏数据集非常简洁.
许多数据库系统使用B树来有效地查找磁盘访问是限制因素的元素.
二进制空间分区树是kd-tree的一种推广,可用于快速渲染计算机图形(它们用于优化原始游戏Doom中的渲染)并进行碰撞检测.
BK树允许您快速确定在某个其他单词的某个编辑距离内的所有单词,更一般地,可以在某个其他点的某个距离内找到度量空间中的所有点.
融合树是整数键的哈希表的替代,它对查找,插入和删除具有极快的支持.
van Emde Boas树是每个元素的O(lg lg n)时间内支持查找,插入,删除,后继和前任的整数键的哈希表的另一种替代方法.某些数据库系统使用vEB树来优化性能.
我不确定这个答案的主题是什么,但它应该让你了解BST和更一般的树结构是多么美妙和强大.