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

Question

我正在阅读二叉搜索树，并在想我们为什么需要 BST？据我所知，所有事情也可以使用简单的排序数组来实现。例如- 为了构建具有 n 个元素的 BST，我们需要 n*O(log n)时间即O(nlog n)查找时间为O(log n) .但是这个东西也可以用数组来实现。我们可以有一个排序数组(需要 O(nlog n) 时间)，其中的查找时间也是 O(log n)即二进制搜索算法。那么为什么我们需要另一个数据结构呢？ BST 是否还有其他用途/应用使它们如此特别？

——拉维

Answer 1

如果您谈论的是一次写入，多次读取类型的交互，那么数组非常棒。当您着手进行插入、交换和删除时，BST 与数组相比才真正开始大放异彩。由于它们是基于节点的，而不是基于连续的内存块，因此将元素移入集合或移出集合的成本很快，同时仍保持集合的排序性质。

可以将其视为链表与数组之间的插入差异。这是一种过度简化，但它突出了我上面提到的优势的一个方面。