16

I'd like to implement a cache-oblivious binary tree that is stored in an array using the van Emde Boas layout, using implicit pointers. All items in the tree are 32-bit integers and the tree will get fairly big, so storing the pointers would mean at least 3x more data.

The problem is that I can't think of any non-iterative way to calculate pointers to the left and right children, given a node index (I can track any information while traversing the tree). Many papers/lectures refer to such trees with implicit pointers, but I haven't seen an algorithm to calculate the pointers. Is there an efficient way to do it?

Lukáš Lalinský
  • 40,587
  • 6
  • 104
  • 126
  • Do you need to calculate it from an index? It seems to me that you just need to calculate a particular child node from a current node. If you are willing to be aware of the current level, keep a stack of offsets on the path to the current node, and have an array of all of the offsets at different levels, you should be able to do it. I don't know how much overhead tracking those stacks will add, it may not be worthwhile. – btilly Feb 05 '11 at 17:46
  • You are right, I don't need to calculate it from arbitrary index. I'm not sure I understand the idea with an array to all offsets? Do you mean offsets to all items on a specific level? – Lukáš Lalinský Feb 05 '11 at 18:31
  • 3
    Have you checked [this paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.762&rep=rep1&type=pdf) out? They give how to lay out a tree using the van Emde Boas layout in section 2.1. – jswolf19 Feb 15 '11 at 10:20

1 Answers1

6

Bob Copeland has a very good implementation of van Emde Boas trees at GitHub. He uses implicit pointers and calculates the pointers by first calculating the breadth-first pointer, after which vEB pointers are a simple conditional.

Seth
  • 2,683
  • 18
  • 18