我正在阅读二叉搜索树，并在想我们为什么需要 BST？据我所知，所有事情也可以使用简单的排序数组来实现。例如-为了构建具有 n 个元素的 BST，我们需要n*O(log n)时间，即O(nlog n)查找时间为O(log n). 但是这个东西也可以用数组来实现。我们可以有一个排序的数组（需要O(nlog n)时间），并且其中的查找时间也是O(log n)二进制搜索算法。那么为什么我们需要另一个数据结构呢？BST 是否还有其他用途/应用使它们如此特别？
——拉维
问问题
5220 次
4 回答
12
如果您谈论的是一次写入，多次读取类型的交互，那么数组非常棒。当您着手进行插入、交换和删除时，BST 与数组相比才真正开始大放异彩。由于它们是基于节点的，而不是基于连续的内存块，因此将元素移入集合或移出集合的成本很快，同时仍保持集合的排序性质。
可以将其视为链表与数组之间的插入差异。这是一种过度简化，但它突出了我上面提到的优势的一个方面。
于 2010-10-14T15:53:56.230 回答
7
想象一下，您有一个包含一百万个元素的数组。
您想在位置 5 处插入一个元素。
所以你在数组的末尾插入然后排序。
假设数组已满；这是 O(nlog n)，即 1,000,000 * 6 = 6,000,000 次操作。
想象一下，你有一棵平衡的树。
那是 O(log n)，加上一点平衡 = 6 + 一点，称之为 10 次操作。
因此，您刚刚花费了 6,000,000 次操作来对数组进行排序。然后你想找到那个元素。你做什么工作？二分搜索 - O(log n) - 这与你在树中搜索时要做的完全一样！
现在假设您要分配 -another- 元素。
您的阵列已满！你做什么工作？用 n 个额外的元素重新分配数组并 memcpy 很多？你真的想要memcpy 4mbytes吗？
在树中，您只需添加另一个元素...
于 2010-10-16T09:14:43.033 回答
4
排序插入时间怎么样？
于 2010-10-14T15:30:36.890 回答
1
在图形编程中，如果您有扩展对象（即表示每个维度中的间隔而不仅仅是一个点），您可以将它们添加到它们完全适合的二叉树的最小级别（通常是八叉树）。
而且，如果您不预先计算树/排序列表，则列表中的 O(n) 随机插入时间可能会非常慢。另一方面，树中的插入时间仅为 O(log(n))。
于 2010-10-14T15:36:12.747 回答