How to calculate pointers in a binary tree with the van Emde Boas layout

Question

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?

Answer 1

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.