我正在准备考试，我遇到的一个问题是:实现树、链表或数组的最佳方法是什么。
最有可能的:
- 数组使用 1 个地址
- LinkedList 使用两个地址。
使用 LinkedList，我们可以插入我们需要的值(我们完美地管理内存)，但大多数情况下使用 O(N) 来访问这个元素，而在 Array 中它是 O(1)。
我该如何回答这个问题？或者我应该说这是主观的。
最佳答案
对于 Binary Search Tree ，答案肯定是一个数组(至少希望是一个可扩展的数组，比如 vector<> 这样你就不受固定大小的限制)。我来分析一下常见的操作，假设树是平衡的 .
查询
在 BST 中，节点需要有指向左右 child 的指针，并且有父指针也很常见。在数组实现中，“指针”可以简单地是数组的整数索引(这意味着数组将存储 Node 对象)。因此查找节点的父节点和子节点是常量，因为对数组的索引是常量。 O(1) .链表实现可能还需要存储对其祖先/ child 所在位置的引用，因此需要 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)在链表中搜索。
插入
数组类似于 搜索 ，除非需要额外的 O(1 ) 指针分配的恒定时间。所以O(log N)插入。
链表也将类似于它们的 搜索 例程，除了附加 O(n)是时候调整指针了，所以 O(n log n)
删除
数组也类似于 搜索 ，除非您可以携带多个 O(log n)要删除的因素，因为您必须遍历树，但它仍然是 O(log n).
链表也会有 O(n log n)加上更多 O(n log n)为了遍历。所以O(n log n)也用于链表。
结论
现在答案应该很明显了 :) 加上数组，您将获得更好的好处 caching比链表。另外，还有一些二叉搜索树的衍生物，比如 heaps (通常是最小堆/最大堆)通常表示为数组，
我希望这有帮助 :)
关于data-structures - 实现 Tree : LinkedList - Array 的最佳方法是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22290414/