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

Question

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

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

Answer 1

Bob Copeland 在 GitHub 上有一个很好的van Emde Boas 树实现。他使用隐式指针并通过首先计算广度优先指针来计算指针，然后vEB指针是一个简单的条件。