2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It depends on what you are trying to do with the linear array. Preorder depth-first traversals? Then do a preorder depth-first traversal to create the array. (Similarly postorder, in-order and breadth-first vs. depth-first). If you want to do binary searches on the linear array then you need to have the array in sorted order and the question is moot (you need to use an inorder depth-first traversal). If you want to implement a priority queue you need to heapify. Sorting (or heapifying) has the added benefit that you no longer need to keep pointers to children. $\endgroup$ – Wandering Logic Oct 16 '13 at 13:04
  • $\begingroup$ What I want is to ensure that if I traverse down one path of the tree and I hit a leaf, this leaf will be close to other leafs from similar paths. It doesn't matter for me how much the tree traversal jumps around in memory, but I do care about how the leafs are layed out in memory. $\endgroup$ – Anteru Oct 16 '13 at 13:14
  • 1
    $\begingroup$ You need to define "similar". It is starting to sound like you just want to sort your data and do binary searches. When you are doing a traversal, how do you decide whether to traverse to the left child or the right child? Are you comparing to some number? $\endgroup$ – Wandering Logic Oct 16 '13 at 13:34
  • $\begingroup$ Similar paths as in: They share a common (sub-)path for the first N elements. $\endgroup$ – Anteru Oct 16 '13 at 13:48
  • 1
    $\begingroup$ Sounds like a sorted array with a binary search to me then. $\endgroup$ – Wandering Logic Oct 16 '13 at 15:10
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.