arrays - 数组和二叉搜索树在效率上有什么区别？

Question

我想知道什么是最好的：数组或二进制搜索树（插入、删除、查找最大值和最小值）以及如何改进它们？

Answer 1

数组允许随机访问其中的每个元素。因此您可以在 中插入、删除和查找特定元素O(1)，并在 中查找最大/最小、删除O(n)。[您也可以设置 max/min并改为O(1)delete ]。O(n)如果您保持数组排序，它将导致插入/删除为O(n)，但您将获得O(logn)查找和O(1)最小/最大值。

BST按定义排序，对于常规的 [不平衡] BST，您会得到最坏O(n)的情况。对于平衡的 BST，您将获得O(logn)插入/删除/查找。你可以得到 O(1)最小值/最大值。

数组的迭代速度通常也更快[假设迭代顺序并不重要]，因为您可以获得更好的缓存性能。此外，与 BST 不同 - 它本质上具有无限大小，当您的数组已满时，数组需要重新分配和复制数据。

可以通过平衡AVL或红黑树来改进BST 。

哪个更好？这取决于应用程序。通常，当您计划插入数据并对其进行排序时，将首选 BST。如果随机访问或迭代是主要目的：您通常使用数组。

Answer 2

Performance comparison of Arrays and Binary search trees:

                 Array                     Binary search tree
          Unsorted   Sorted           Average            Worst case
Space      O(n)       O(n)             O(n)               O(n)
Search     O(n)       O(log n) *       O(log n)           O(n)
Max/Min    O(n)       O(1)             O(1) **            O(1) **
Insert     O(1)       O(n)             O(log n)           O(n)
Delete     O(1)       O(n)             O(log n)           O(n)

* assuming binary search

** requires extra pointers to min and max, otherwise it's O(log n)