通常,基于二叉树的抽象可以使用实际的链接节点对象来实现,其中每个节点具有指向它的两个子节点的指针,或者数组,其中索引k中的节点的子节点是2k和2k + 1.
除了节点的小额外内存开销之外,一般的复杂性似乎是相同的.
一个是否有任何具体优势？有趣的是,我已经看到二进制堆倾向于使用数组实现,而二进制搜索树倾向于使用链接节点实现.有什么理由吗？
rad*_*aph 11
数组不能表示任意形状的二叉树,只能表示完整的树.完整的二叉树是所有级别都已满的,或者除最深级别之外的所有级别都已满,最深级别的所有级别都尽可能地位于左侧.(您可以想象,从左到右填充了节点,在下一个级别开始之前必须填充一个级别.)
根据定义,堆是完整的二叉树 - 因此由于其优越的存储效率而使用阵列实现.另一方面,必须支持在任意位置插入和移除的二叉搜索树(因此可能不是完整的树)不能使用阵列实现.
首先，这是一个合理的问题：二叉树确实可以嵌入到数组中。phari 的答案是不正确的：通过一些努力，可以将任意形状的树嵌入到数组中（只要你有足够的内存）。一个简单的表示涉及将 a 定义Node为变体类型：它是Filled或Empty，其中Filled包含键和辅助数据，并且Empty类似于Nil（也称为空指针）。如果您需要支持的唯一操作是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的数据结构，它使用这种嵌入。我支持在 master 分支上进行build, delete, delete_range, query_range,操作，并在分支上进行实验性操作。项目页面还包含一些基准测试，表明数据结构至少对于某些用途绝对可行。iterinsertinsert
您可能还对这篇解释如何在恒定辅助空间中构建树（实践中非常快速的方法）的博客文章感兴趣。