Array和Binary搜索树在效率上有什么区别？

Question

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

Answer 1

一个阵列允许随机存取,以在它的每个元素.所以你得到插入,删除和查找特定元素O(1),并在max/min中删除O(n).[你也可以制作最大/最小O(1)并删除O(n)].如果要对数组进行排序,则会导致插入/删除O(n),但您将获得O(logn)查找和O(1)最小/最大.

一个BST被定义排序,并定期[不平衡] BST,你会得到O(n)最糟糕的情况下的行为.对于平衡BST,您可以获得O(logn)插入/删除/查找.您可以获得 O(1)最小/最大两种方式.

由于您获得了更好的缓存性能,因此数组通常也可以更快地迭代 [假设迭代顺序并不重要] .此外,与BST(本质上具有无限大小)不同,数组需要重新分配并在阵列已满时复制数据.

改善 BST可以通过平衡来实现 - 比如AVL或红黑树.

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

Answer 2

数组和二叉搜索树的性能比较:

                 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)

* 假设二元搜索

** 需要额外指向min和max的指针,否则它是O(log n)