KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
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?
Tags (comma-separated)
Save Edits
Cancel