algorithm - Is there any locality-preserving way to flatten a binary tree? -

short version:

it possible flatten 2d space 1d space such if 2 points on 2d space close together, mappings 1d close together. similarly, there way map arbitrary position in binary tree, flat index in array, such if 2 nodes close on tree, close on array?

---

long version:

let tree type of tagged binary trees.

                            /     \            b       c           / \     / \          d   e   f   g         / \ / \ / \ / \         h j k l m n o 

a position on in tree can given bit string 0 means go left, 1 means go right , empty string root (a). example, 011 points k on tree above. moreover, let distance between 2 nodes number of steps takes go 1 another.

what map f :: bitstring -> nat node locations (bitstrings) natural numbers such if distance(a, b) small, |f(a) - f(b)| small?

i think tilmannz's answer (which uses infix ordering) it's going get. consider every node in binary tree, apart root, has 3 neighbors, , in 1d memory layout, 2 of them can distance of 1 away. also, not many other useful orderings come mind.

i've written small perl script compares default ordering depth-first prefix ordering , infix ordering. can throw output @ gnuplot following plot (edit: included van-emde-boas layout):

you can see original ordering has relatively bad locality small tree distances, , both prefix , infix orderings better. infix ordering produces best behaviour of three, though (e.g., nodes @ tree distance of 3 on average 6 memory indices apart). linear curve, should indicator cannot better. v.e.b. layout mentioned in comments not @ least smaller node distances, according distance criterion.

for sake of completeness, here's (somewhat quick , dirty) script used:

#!/usr/bin/perl # compares node distances in memory different layouts of following # binary tree: #                      #                  /       \ #              b               c #            /   \           /   \ #          d       e       f       g #         / \     / \     / \     / \ #        h     j   k   l   m   n   o #       / \ / \ / \ / \ / \ / \ / \ / \ #       p q r s t u v w x y z 0 1 2 3 4  # calculates real node distance. sub dist($$) {   ($i, $j) = @_;   return 0 if ($i == $j);   ($j,$i) = ($i,$j) if ($i > $j);   # $i<$j. go 1 larger node.   return 1 + dist($i, ($j-1)>>1); }  # determines average memory distance nodes function of tree distance. sub get_dists($$) {   $tree = shift;     # original tree ordering   $locality = shift; # locality-based ordering    %dists = ();   %counts = ();    (my $i=0; $i<length($tree); $i++)   {     (my $j=$i; $j<length($tree); $j++)     {       # find location of $i , $j in locality-based ordering.       $ni = substr($tree, $i, 1);       $nj = substr($tree, $j, 1);       $it = index($locality, $ni);       $jt = index($locality, $nj);       $d = (($i <= $j) ? ($j-$i) : ($i-$j));       $dt = (($it <= $jt) ? ($jt-$it) : ($it-$jt));       $treedist = dist($i, $j);       $dists{$treedist} += $dt;       $counts{$treedist}++;     }   }   foreach $k (sort keys %counts)   {     $dists{$k} /= $counts{$k};   }   return %dists; }  $tree = "abcdefghijklmnopqrstuvwxyz01234";    # original (breadth-first prefix) ordering $prefix = "abdhpqirsejtukvwcflxymz0gn12o34";  # depth-first prefix ordering $infix = "phqdrisbtjuevkwaxlyfzm0c1n2g3o4";   # infix ordering $veb = "abcdhpqirsejtukvmflxymz0gn12o34";     # v.e.b. layout (hope got right)  %original_dists = get_dists($tree, $tree); %prefix_dists = get_dists($tree, $prefix); %infix_dists = get_dists($tree, $infix); %veb_dists = get_dists($tree, $veb);  print "set key top left;\n"; print "set title 'locality ratios';\n"; print "set xlabel 'tree distance';\n"; print "set ylabel 'avg. memory distance';\n";  print "plot '-' w lp title 'original', '-' w lp title 'prefix ordering', '-' w lp title 'infix ordering', '-' w lp title 'van-emde-boas layout';\n";  foreach $k (sort keys %original_dists) {   print "$k $original_dists{$k}\n"; } print "e\n"; foreach $k (sort keys %prefix_dists) {   print "$k $prefix_dists{$k}\n"; } print "e\n"; foreach $k (sort keys %infix_dists) {   print "$k $infix_dists{$k}\n"; } print "e\n"; foreach $k (sort keys %veb_dists) {   print "$k $veb_dists{$k}\n"; } print "e\n";