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

Question

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

Answer 1

一个数组允许random access到其中的每个元素。因此您可以在 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) min/max。

数组通常也比 iterate 更快[假设迭代顺序不重要] 因为你获得更好的 cache表现。此外，与 BST 不同 - 它本质上具有无限大小，数组需要重新分配并在数组已满时复制数据。

改进 BST 可以通过制作它来完成 balanced - 喜欢AVL或 red-black-trees .

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