我正在阅读二叉搜索树,并在想我们为什么需要 BST?据我所知,所有事情也可以使用简单的排序数组来实现。例如-为了构建具有 n 个元素的 BST,我们需要n*O(log n)
时间,即O(nlog n)
查找时间为O(log n)
. 但是这个东西也可以用数组来实现。我们可以有一个排序的数组(需要O(nlog n)
时间),并且其中的查找时间也是O(log n)
二进制搜索算法。那么为什么我们需要另一个数据结构呢?BST 是否还有其他用途/应用使它们如此特别?
——拉维
我正在阅读二叉搜索树,并在想我们为什么需要 BST?据我所知,所有事情也可以使用简单的排序数组来实现。例如-为了构建具有 n 个元素的 BST,我们需要n*O(log n)
时间,即O(nlog n)
查找时间为O(log n)
. 但是这个东西也可以用数组来实现。我们可以有一个排序的数组(需要O(nlog n)
时间),并且其中的查找时间也是O(log n)
二进制搜索算法。那么为什么我们需要另一个数据结构呢?BST 是否还有其他用途/应用使它们如此特别?
——拉维
如果您谈论的是一次写入,多次读取类型的交互,那么数组非常棒。当您着手进行插入、交换和删除时,BST 与数组相比才真正开始大放异彩。由于它们是基于节点的,而不是基于连续的内存块,因此将元素移入集合或移出集合的成本很快,同时仍保持集合的排序性质。
可以将其视为链表与数组之间的插入差异。这是一种过度简化,但它突出了我上面提到的优势的一个方面。
想象一下,您有一个包含一百万个元素的数组。
您想在位置 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吗?
在树中,您只需添加另一个元素...
排序插入时间怎么样?
在图形编程中,如果您有扩展对象(即表示每个维度中的间隔而不仅仅是一个点),您可以将它们添加到它们完全适合的二叉树的最小级别(通常是八叉树)。
而且,如果您不预先计算树/排序列表,则列表中的 O(n) 随机插入时间可能会非常慢。另一方面,树中的插入时间仅为 O(log(n))。