通常，基于二叉树的抽象可以使用实际的链接节点对象来实现，其中每个节点具有指向它的两个子节点的指针，或者数组，其中索引k中的节点的子节点是2k和2k 1 .
除了节点的小额外内存开销之外，一般的复杂性似乎是相同的 .
一个是否有任何具体优势？有趣的是，我已经看到二进制堆倾向于使用数组实现，而二进制搜索树倾向于使用链接节点实现 . 有什么理由吗？
数组不能表示任意形状的二叉树，只能表示完整的树 . 完整的二叉树是所有级别都已满的，或者除最深级别之外的所有级别都已满，最深级别的所有级别都尽可能地位于左侧 . （您可以想象，从左到右填充了节点，在下一个级别开始之前必须填充一个级别 . ）
根据定义，堆是完整的二叉树 - 因此由于其优越的存储效率而使用阵列实现 . 另一方面，必须支持在任意位置插入和移除的二叉搜索树（因此可能不是完整的树）不能使用阵列实现 .
首先，它是一个合法的问题：二叉树确实可以嵌入到数组中 . phari's answer是不正确的：可以通过一些努力将任意形状的树嵌入到数组中（只要你有足够的内存） . 直接表示将涉及将 Node 定义为变体类型：它是 Filled 或 Empty ，其中 Filled 包含密钥和辅助数据， Empty 类似于 Nil （也称为空指针） . 如果您需要支持的唯一操作是 delete ，那么您已全部设置：只需实现 build 操作即可返回完整的树，然后实现正常的二叉树 delete 操作 . 实现 O(log n) 复杂性绑定不需要 balancer （其中 n 是树的初始项目数） .
Node
Filled
Empty
Nil
delete
build
O(log n)
n
通过将树保持 balancer 形状来实现 insert 操作也是可能的 . 简化一下，您可以维护一个几乎完整的树，其存储大小不超过 2n （其中 n 是树中当前的项目数） . 插入新项目时，您可以检查要插入的相应数组单元的位置：如果它位于已分配的存储区域内，则只需将其写入该单元格即可 . 否则，您从该单元格的父级开始向上移动树，直到找到一个子树，其存储空间足以容纳所有项目，包括新项目;如果不存在这样的子树，则将存储量加倍 . 找到该子树后，将其重建为几乎完整的形状，并将新项插入正确的阵列单元（现在保证在分配的存储区内） . 所有这些都可以在摊销的 O(log^2(n)) 时间内完成，或者在摊销的 O(log(n)) 时间内完成 .
insert
2n
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 操作 . 项目页面还包含一些基准测试，表明数据结构至少对某些用途来说是绝对可行的 .
delete_range
query_range
iter
您可能也对this blog post感兴趣，解释如何在恒定辅助空间中构建树（实践中非常快速的方法） .
2 回答
数组不能表示任意形状的二叉树，只能表示完整的树 . 完整的二叉树是所有级别都已满的，或者除最深级别之外的所有级别都已满，最深级别的所有级别都尽可能地位于左侧 . （您可以想象，从左到右填充了节点，在下一个级别开始之前必须填充一个级别 . ）
根据定义，堆是完整的二叉树 - 因此由于其优越的存储效率而使用阵列实现 . 另一方面，必须支持在任意位置插入和移除的二叉搜索树（因此可能不是完整的树）不能使用阵列实现 .
首先，它是一个合法的问题：二叉树确实可以嵌入到数组中 . phari's answer是不正确的：可以通过一些努力将任意形状的树嵌入到数组中（只要你有足够的内存） . 直接表示将涉及将
Node定义为变体类型：它是Filled或Empty，其中Filled包含密钥和辅助数据，Empty类似于Nil（也称为空指针） . 如果您需要支持的唯一操作是delete，那么您已全部设置：只需实现build操作即可返回完整的树，然后实现正常的二叉树delete操作 . 实现O(log n)复杂性绑定不需要 balancer （其中n是树的初始项目数） .通过将树保持 balancer 形状来实现
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感兴趣，解释如何在恒定辅助空间中构建树（实践中非常快速的方法） .