algorithm - 如何使用 van Emde Boas 布局计算二叉树中的指针

Question

我想使用 van Emde Boas 布局和隐式指针实现一个存储在数组中的无缓存二叉树。树中的所有项目都是 32 位整数，树会变得相当大，因此存储指针将意味着至少多 3 倍的数据。

问题是，在给定节点索引的情况下，我想不出任何非迭代的方法来计算指向左右子节点的指针(我可以在遍历树时跟踪任何信息)。许多论文/讲座都提到了带有隐式指针的此类树，但我还没有看到计算指针的算法。有什么有效的方法吗？

Answer 1

Bob Copeland 很好地实现了 van Emde Boas trees at GitHub .他使用隐式指针，通过先计算广度优先指针来计算指针，然后vEB指针是一个简单的条件。