Luk*_*ský 16 algorithm binary-tree cache-oblivious
我想使用隐式指针实现一个缓存无关的二叉树,它使用van Emde Boas布局存储在一个数组中.树中的所有项都是32位整数,并且树会变得相当大,因此存储指针意味着至少要多3倍的数据.
问题在于,在给定节点索引(我可以在遍历树时跟踪任何信息)时,我无法想到计算指向左右子节点的指针的任何非迭代方法.许多论文/讲座都是用隐式指针引用这些树,但我还没有看到计算指针的算法.有没有一种有效的方法呢？
Set*_*eth 6
Bob Copeland 在GitHub上很好地实现了van Emde Boas树.他使用隐式指针并通过首先计算广度优先指针来计算指针,之后vEB指针是一个简单的条件.
归档时间：
14 年，7 月 前
查看次数：
2316 次
最近记录：
14 年，5 月 前