二叉搜索树相对于哈希表有哪些优点？
哈希表可以在 Theta(1) 时间内查找任何元素，并且添加元素也同样容易......但我不确定相反的优势。
没有人指出的一项优点是二叉搜索树允许您有效地进行范围搜索。
为了说明我的想法，我想举一个极端的例子。假设你想要获取键在 0 到 5000 之间的所有元素。实际上只有一个这样的元素，还有 10000 个键不在该范围内的其他元素。 BST 可以非常有效地进行范围搜索，因为它不会搜索不可能得到答案的子树。
那么，如何在哈希表中进行范围搜索呢？您要么需要迭代每个桶空间，即 O(n)，要么必须查找 1,2,3,4... 最多 5000 个中的每一个是否存在。
（0到5000之间的键是无限集合吗？例如键可以是小数）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
