实现 Tree 的最佳方法是什么：LinkedList - Array

Question

我正在准备考试，我遇到的一个问题是：实现树、链表或数组的最佳方法是什么。

最有可能： - 数组使用 1 个地址 - LinkedList 使用两个地址。

使用 LinkedList，我们可以插入我们需要的值（我们完美地管理内存），但大多数情况下使用 O(N) 来访问这个元素，而在 Array 中它是 O(1)。

我该如何回答这个问题？或者我应该说这是主观的。

Answer 1

对于 a Binary Search Tree，答案肯定是一个数组（至少希望是一个可扩展的数组，就像 a 一样，vector<>这样你就不受固定大小的限制）。假设树是平衡的，我将对常见操作进行分析。

询问

在 BST 中，节点需要有指向左子节点和右子节点的指针，而且也很常见有父节点指针。在数组实现中，“指针”可以简单地是数组中的整数索引（这意味着数组将存储Node对象）。因此，由于数组索引是恒定的，因此查找节点的父节点和子节点是恒定的。O(1)。链表实现可能还需要存储对其祖先/子代所在位置的引用，因此需要遍历O(N)列表以获取所需的引用。

搜索

root从,开始array[0]，搜索将是一个O(log N)操作。搜索只会调用/获取每个节点的子节点的信息，这是 O(1) 的工作量，大约是 O(log N) 次，因此O(log N)在数组中进行搜索。

链表需要 O(N) 遍历数据才能获取所需的左/右指针，并且也可以在 O(log N) 步骤中完成，从而O(n log n)在链表中进行搜索。

插入

数组与search类似，只不过需要额外的O(1常数时间来进行指针分配。所以O(log N)插入。

链接列表也类似于它们的搜索 例程，除了需要额外的O(n)时间来调整指针，所以O(n log n)

删除

数组也类似于search，除了您可以删除多个单个O(log n)因素，因为您必须遍历树，但它仍然是O(log n).

链接列表也将具有O(n log n)更多的O(n log n)向上遍历功能。O(n log n)对于链表也是如此。

结论

现在答案应该相当明显了:)加上数组，你将获得caching比链表更好的好处。另外，二叉搜索树的一些派生，例如heaps（通常是最小堆/最大堆）通常表示为数组，

我希望这有帮助 ：）