[Solved]: Tree flattening with layout guarantees

Problem Detail: 

I want to flatten a binary tree into a linear array, and I wonder if there are specific algorithms to improve locality in the linearized representation (for instance, ensuring that all data from the left child of the root node appears before the data from the right child is an easy optimization.) What is the recommended approach to maintain high locality?

Asked By : Anteru

Answered By : Mahmoud A.

one solution might be Van Emde Boas layout (vEB). It is used in a hierarchical memory to optimize the number of cache misses (since it is a cache-oblivious method).

Here is how we lay a complete binary tree that has $N$ nodes in an array: split the tree in the middle (i.e. at height $h/2$ where $h= \log N + 1$). This breaks the tree into a top subtree $T_0$ of height $\lceil h/2 \rceil$ and several bottom subtrees $T_1,...,T_k$ of height $\lfloor h/2 \rfloor$, each dangling from a leaf of $T_0$. Now store $T_0$ in the first part of array and the bottom subtrees next to it, in the order from left to right. You need to store each $T_i$ recursively, i.e. beaking into smaller subtrees until the subtrees contains only one node.

http://erikdemaine.org/papers/BRICS2002/paper.pdf

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16134