logo标签列表

为什么要使用二叉搜索树？

data-structuresbinary-treebinary-search-tree
6
我正在阅读二叉搜索树，并思考为什么我们需要BST？据我所知，所有的事情都可以通过简单的有序数组来实现。例如，构建具有n个元素的BST需要n*O(log n)时间，即O(nlog n)，并且查找时间为O(log n)。但是这个东西也可以使用数组来实现。我们可以拥有一个排序的数组（需要O(nlog n)时间），在其中查找时间也是O(log n)，即二进制搜索算法。那么我们为什么需要另一种数据结构呢？还有其他BST的用途/应用，使它们如此特殊吗？
2
数组版本的插入/删除效率如何？如果涉及到移动数组中的所有其他元素，那么代价可能很高。 - Kirk Woll
1
好的...找到新/现有元素的正确位置仍然是O(log n)，但是移动将会是一个问题...不过只是这一个...根据我阅读过的文本，它们(BST)似乎非常特别？我想知道使它们如此特别的事情。 - Ravi Gupta
可能是二分查找与二叉搜索树的重复问题。 - nawfal
非常抱歉我投票关闭了一个较新的问题，但它表述更清晰，并且得到了更多的关注。 - nawfal
4个回答
12

如果你需要进行一次写操作并多次读取操作，那么数组是非常好的选择。但是，当涉及到插入、交换和删除时，与数组相比，BST真正开始发挥其优势。由于它们是基于节点而不是连续的内存块，所以将元素移动到集合中或者从集合中移除元素的成本很低，同时仍然保持了集合的排序特性。

可以将其类比为链表和数组之间插入操作的区别。虽然这是一种过度简化，但它强调了我上面提到的优势方面。

8

假设你有一个包含一百万个元素的数组。

你想在第五个位置插入一个元素。

所以你在数组末尾插入，然后排序。

假设这个数组是满的；那么这需要 O(nlog n) 的时间复杂度，也就是 1,000,000 * 6 = 6,000,000 次操作。

假设你有一棵平衡树。

那么这需要 O(log n) 的时间复杂度，再加上一些用于平衡的操作，约为 6 次操作。

因此，你刚刚花费了 6,000,000 次操作来对数组进行排序。现在你想要 查找 这个元素。你该怎么办？使用二分查找 - O(log n) - 这与在树中搜索时所做的事情完全相同！

现在想象一下，你想要分配 -另一个- 元素。

你的数组已经满了！你该怎么办？重新分配一个具有额外 n 个元素的数组，并将所有元素都复制过去吗？你真的想要复制 4MB 吗？

在树中，你只需要添加另一个元素...

4
如何按排序插入时间排序？
好的... 找到新元素的正确位置仍然是O(log n)，但移位会成为一个问题... 只有这个 ... 根据我所读的文本，它们（BST）似乎非常特殊？ 我想更多地了解使它们如此特殊的事情。 - Ravi Gupta
1
我认为其他答案可能会对你有所帮助。另一件要记住的事情是，BST不是最终的数据结构，而是更复杂、更高效的结构的基础，这解释了它们的流行。例如，您可能已经意识到，在最坏的情况下搜索BST是线性的；解决这个问题的答案是AVL树。您还可以使用红黑树、2-3-4树、后缀/前缀树和DAWGs等，它们以不同的方式概括了BST，并产生了有效的算法，这些算法用数组实现将超出我们的能力范围。 - Anthony Labarre
1
在图形编程中，如果您有扩展对象（即代表每个维度的间隔而不只是一个点），您可以将它们添加到二叉树（通常是八叉树）的最小层级中，以完全适应它们。
而且，如果您不预先计算树/排序列表，列表中的O(n)随机插入时间可能会非常慢。然而，在树中的插入时间仅为O(log(n))。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接