通常，基于二叉树的抽象可以使用实际链接的节点对象来实现，其中每个节点都有指向其两个子节点的指针，也可以使用数组来实现，索引k中节点的子节点是2k和2k+1。
除了节点的少量额外内存开销外，其复杂性总体上似乎是相同的。
一个比另一个有什么具体的优势吗？有趣的是，我看到二进制堆倾向于使用数组实现，而二进制搜索树倾向于使用链接节点实现。有什么原因吗？
数组不能有效地表示任意形状的二叉树，只有完整的树。完整的二叉树是指所有级别都已满，或者除最深级别外的所有级别都满，并且最深级别的所有节点都尽可能向左。（你可以想象，这些级别从左到右都填充了节点，在下一个级别开始之前，必须填充一个级别。）
根据定义，堆是完整的二进制树，因此使用数组实现是因为它具有优越的内存效率。另一方面，必须支持在任意位置插入和删除的二进制搜索树（因此可能不是完整的树）不能使用数组实现。
首先，是一个合理的问题：二进制树确实可以嵌入数组中。phari的回答是不正确的：只要你有足够的内存，就可以将任意形状的树嵌入数组中。一个简单的表示将涉及将Node定义为变体类型：它是Filled或Empty，其中Filled包含密钥和辅助数据，而Empty类似于Nil（也称为空指针）。如果您唯一需要支持的操作是delete，那么您已经做好了准备：只需实现build操作以返回完整的树，然后实现普通的二进制树delete操作。不需要平衡来实现O(log n)复杂度边界（其中n是树的初始项目数）。
还可以通过将树保持在平衡的形状来实现CCD_ 12操作。简化一点，您可以维护一个几乎完整的树，其存储大小不超过2n（其中n是树中的当前项目数）。插入新项时，请检查要插入的适当数组单元格的位置：如果它在分配的存储中，则只需将其写入该单元格即可。否则，您将从该单元格的父级开始向上树，直到找到一个子树，该子树的存储空间足以容纳包括新项在内的所有项；如果不存在这样的子树，则将存储空间加倍。找到子树后，将其重建为几乎完整的形状，并将新项插入到正确的数组单元格中（现在可以保证它在分配的存储中）。所有这些都可以在摊销后的O(log^2(n))时间内完成，也可以在摊销前的O(log(n))时间内完成。
上面的算法草图是基于"通过小高度二叉树"。
我已经实现了一个名为TeardownTree的数据结构，它使用了这种嵌入。我支持主分支上的build、delete、delete_range、query_range、iter操作，以及insert分支上的实验性insert操作。项目页面还包含一些基准测试，这些基准测试表明数据结构至少在某些用途上是绝对可行的。
你可能还对这篇博客文章感兴趣，它解释了如何在恒定的辅助空间中构建树（在实践中是一种非常快速的方法）。