为什么是二元搜索树?

数组是很好的,如果你说一次写,多次读类型的交互。当您开始插入、交换和删除时,BST确实开始比数组亮。因为它们是基于节点的,而不是基于连续的内存块,所以将元素移入集合或移出集合的成本很快,同时仍然保持集合的排序性质。

把它想象成链接列表和数组之间插入的区别。这过于简单化了,但它突出了我上面提到的优势的一个方面。

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

要在位置5插入元素。

所以在数组的末尾插入,然后排序。

假设你有一棵平衡的树。

这是O(log n),加上一点用于平衡=6+一点,称之为10次操作。

所以,你刚刚花了6000000次操作来排序你的数组。然后你想 找到 那个元素。你是做什么的?二进制搜索-o(log n)-即 确切地 就像你在树上搜索时要做的一样!

现在假设您想要分配另一个元素。

您的阵列已满!你是做什么的?用n个额外的元素重新分配数组,并对该批进行memcpy?你真的想记忆4个字节?

在树中,只需添加另一个元素…

排序后的插入时间如何?

在图形编程中,如果您有扩展对象(即表示每个维度中的间隔,而不仅仅是一个点),则可以将它们添加到二进制树的最小级别(通常是八叉树),使它们完全适合。

如果不预先计算树/排序列表,那么列表中的O(N)随机插入时间可能会非常慢。另一方面,树中的插入时间仅为o(log(n))。