二叉树，数组 vs 链表

Question

二叉树，数组 vs 链表

binary-tree

15

通常，基于二叉树的抽象可以使用实际链接节点对象或数组来实现，其中每个节点都有指向其两个子节点的指针。在索引为k的节点中，其子节点为2k和2k+1。

除了节点占用少量额外内存之外，总体复杂度似乎是相同的。

它们之间是否存在具体优势？据我所见，二叉堆倾向于使用数组实现，而二叉搜索树倾向于使用链接节点实现。这样做的原因是什么呢？

- Taylor Huston

2个回答

5

首先，这是一个合法的问题：二叉树确实可以嵌入数组中。phari's answer 是不正确的：只要有足够的内存，就可以将任意形状的树嵌入数组中。直接的表示方法涉及定义一个变体类型的Node：它要么是Filled，包含键和辅助数据，要么是类似于Nil（也称为空指针）的Empty。如果您需要支持的唯一操作是delete，那么您已经准备好了：只需实现build操作以返回完整的树，然后实现正常的二叉树delete操作即可。不需要平衡来实现O(log n)复杂度界限（其中n是树中初始项的数量）。

通过保持树的平衡形状，可以付出相当大的努力来实现insert操作。简单地说，您维护一个近乎完整的树，存储大小不超过2n（其中n是树中当前项目数）。插入新项目时，您检查要插入的适当数组单元格的位置：如果它在分配的存储内部，则只需将其写入该单元格。否则，您从该单元格的父项开始向上遍历树，直到找到一个子树，其存储具有足够的空间来容纳所有项目，包括新项目；如果不存在这样的子树，则将存储器加倍。找到该子树后，将其重建为近乎完整的形状，并将新项目插入正确的数组单元格（现在保证在分配的存储内）。所有这些都可以在摊销的O(log^2(n))时间内完成，或者通过更多的努力在摊销的O(log(n))时间内完成。

上述算法草图基于“Cache Oblivious Search Trees via Binary Trees of Small Height”。

我已经实现了一种名为TeardownTree的数据结构，它使用了这种嵌套方式。在主分支上，我支持build、delete、delete_range、query_range和iter操作，并在insert分支上进行了实验性的insert操作。该项目页面还包含一些基准测试，显示该数据结构至少对某些用途是可行的。

您可能还会对this blog post感兴趣，该博客文章解释了如何在恒定辅助空间中构建树(这是一种在实践中非常快速的方法)。

- kirillkh

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- radiaph · Accepted Answer

数组不能有效地表示任意形状的二叉树，只能表示完全二叉树。完全二叉树是指所有层都是满的，或者除最深层外的所有层都是满的，最深层的节点尽可能靠左。（您可以想象每一层从左到右填充节点，并且必须在下一层开始之前填满一层。）

堆是完全二叉树，因此使用数组实现由于其卓越的内存效率。另一方面，必须支持在任意位置插入和删除的二叉搜索树（因此可能不是完全二叉树）无法使用数组实现。