非静态二叉树的紧凑型存储

Question

我已经看到静态二叉树的基于数组的实现，它不浪费指针的内存，而是在当前索引上执行操作以转到其父项或子项。是否有任何文章谈论二叉树的类似方法，您将不得不插入或删除。我可以看到该数组将不再有用，除非您对允许的插入数量有上限。

Answer 1

这是总是可能在数组中构建一个二叉树，使用简单的算法从父级找到子节点。 （特别是对于二进制堆）的常用方法是使用以下...

left_child_index = (2 * parent_index) + 1 
right_child_index = (2 * parent_index) + 2 

所以在0根节点具有子在图1和2中，在1节点具有3和4等

儿童

这种方案的缺点是，当你通过不存储指针获得空间时，通常会因为未使用的节点需要在数组中留下间隙而损失空间。二进制堆通过完成二叉树来避免这种情况 - 当前数量的项目范围内的每个节点都是有效的。这适用于堆，但不能用于二叉搜索树操作。

只要你能调整你的阵列（如用C std::vector ++），你并不需要放置一个上限插入的数目，但你可以在更深的差距的很多结束你的数组的一部分，特别是如果树不平衡。

您还需要某种方法来确定数组中的位置是否包含有效节点 - 无论是在有效节点中不能出现的标志或数据值。标志可能被存储为一个打包的位阵列，与主节点分开。

另一个缺点是重构树意味着移动数据 - 而不仅仅是调整指针。指针旋转（许多平衡二叉树，如红黑树和AVL树需要）变成潜在的非常昂贵的操作 - 它们不仅需要移动通常的三个节点，而且整个子树都是从旋转的节点开始下降的。这就是说，如果你的物品非常小，并且如果你的树会保持很小，或者你可以用简单的不平衡树，那么这个方案可能是有用的。也许，这可能仅仅是一个整数集合数据结构。

顺便说一句 - “似是而非”并不意味着“推荐”。即使你设法找到效率更高的案例，我也很难相信开发时间是合理的。

可能更为有用...

多路树包含的项小数组中的每个节点，而不是通常的一个关键。它们通常用于硬盘上的数据库索引。最着名的是B树，B +树和B *树。

多维树具有子节点指针，但对于最多可容纳n个键的节点，子指针的数量通常为n或n + 1 - 而非两次n。另外，一个常见的策略是对分支节点和叶节点使用不同的节点布局。只有分支节点具有子指针。每个数据项都位于叶节点中，只有叶节点包含非关键数据。分支节点纯粹用于指导搜索。由于叶子节点是迄今为止数量最多的节点，因此没有子节点指针是非常有用的节省。

但是 - 多路树节点很少打满。再次，未使用的阵列插槽有空间开销。通常的规则是每个节点（除了根节点）必须至少有一半满。一些实现花费了相当多的精力来避免分割节点，从而最小化了空间开销，但通常会有一个与项目数量大致成正比的预期开销。

我也听说过一种树形式，每个节点拥有多个键，但每个节点只有两个子指针。我甚至不记得这是什么，恐怕。

也可以将（父指针，子指针）对存储在单独的数据结构中。这对于在数据库中表示树，使用（父ID，子ID）对或者（父ID，兄弟索引，子ID）表的三元组表或其他类型的表是相当常见的。一个好处是你不需要存储'空'指针。

但是，可能最好的选择，不是试图减少或消除存储指针的开销，而是为了更好地使用这些开销。树形二叉树更好地利用子指针来支持树的高效遍历 - http://en.wikipedia.org/wiki/Threaded_binary_tree。

Answer 2

至少在C++中，使用数组而不是单独分配的结构的好处之一是避免创建每个对象的开销。 （C++中的结构数组在内存中是连续的，没有头或分配对齐问题）通过比较保存一个指针可能很小。

不幸的是，在Java中，一个对象数组不能以这种方式工作，所以使用数组不会给你带来好处。在C++中，计算每个对象的引用，但是在Java中，对每个对象的引用都存储在内存中，即使它们恰好是连续的。

Java为您做的唯一事情是在64位JVM中使用32位引用。

除非您拥有内存有限的设备，或者数据结构非常庞大（例如数百万个元素），否则您不太可能注意到其中的差异，您可以购买16 GB以内的低于100英镑的内存。