java - 非静态二叉树的紧凑存储

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 的两倍。此外，一种常见的策略是对分支节点和叶节点使用不同的节点布局。只有分支节点有子指针。每个数据项都在一个叶子节点中，只有叶子节点包含非关键数据。分支节点纯粹用于指导搜索。由于叶节点是迄今为止数量最多的节点，因此其中没有子指针是一种有用的节省。

但是 - 多路树节点很少装满。同样，未使用的阵列插槽也会产生空间开销。通常的规则是每个节点(除了根节点)必须至少半满。一些实现在避免 split 节点方面付出了相当多的努力，从而最大限度地减少了空间开销，但通常预期的开销与项目数大致成正比。

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

也可以将(父指针，子指针)对存储在单独的数据结构中。这对于在数据库中表示树是相当常见的，使用(父 ID，子 ID)对的表，或(父 ID，兄弟索引，子 ID)三元组或其他的表。一个优点是您不需要存储“空”指针。

然而，与其试图减少或消除存储指针的开销相比，最好的选择可能是更好地利用该开销。线程二叉树更好地利用子指针来支持树的有效遍历 - http://en.wikipedia.org/wiki/Threaded_binary_tree .