是否有任何保留位置的方法来展平二叉树？

Question

短版：

It is possible 将 2D space 展平为 1D space 这样如果 2D space 上的两个点靠得很近，那么它们到 1D 的映射将也靠得很近。同样，有没有办法将二叉树中的任意位置映射到数组中的平面索引，这样如果两个节点在树上靠得很近，那么它们在数组上也会靠得很近？

长版：

设Tree为标记二叉树的类型。

               A 
            /     \
           B       C
          / \     / \
         D   E   F   G
        / \ / \ / \ / \
        H I J K L M N O

Tree 中的位置可以由位串给出，其中 0 表示 go left，1 表示 go right 和空字符串是根 (A)。例如，011 指向上面树上的 K。此外，设两个节点之间的 distance 为从一个节点到另一个节点所需的步数。

什么是从节点位置（位串）到自然数的映射 F :: BitString -> Nat，如果 distance(A, B) 很小，那么 |F(A) - F(B)| 也很小？

Answer 1

也许您想查看 space-填充曲线。最简单的一个是 z-curve（也称为 Morton 顺序），它可以通过将 x 和 y 坐标的位交织成称为 z 值的东西来创建。如果两个 2D 点的结果 z 值距离很小，那么原始点也不远。不幸的是，反过来并不总是正确的，有一些例外情况，相邻的 2D 点得到非常不同的 z 值。

更好的接近度（小 distance(A,B) 的可能性 -> 小 |F(A)-F(B)| 可以用 Hilbert curves 实现，但是它们更难计算。

对于这两种算法，都可以使用一些位级别的技巧来非常快速地计算它们，例如参见优秀的 Hacker's delight 书（我不隶属于它，我只是非常喜欢它）。

Answer 2

如果你想压平一棵已知高度的树，那么基本的方法可能是交错节点。对于上面的示例，这将导致一个包含 [H,D,I,B,J,E,K,A,...] 的数组，依此类推。接近度并不理想，但可能会尽可能接近。要计算位置，您可以执行以下操作。假设 h 是节点的高度，从 0（底部：H,I,J,K,..）到 3（顶部：A）计数。如果您按照描述对节点进行编码，即 H=000,B=00,I=001,，则数组位置将为 pos(node)=value(node)*2 + (2^h)-1。例如 pos(H=000)=0、pos(B=00)=1、pos(I=001)=2、...

一个问题显然是增加树的高度最好通过在'A'上方插入节点来完成，否则你将不得不重新映射所有节点。

编辑该算法的局部性要求对于顶级节点（A/B）当然不是很好，但对于大多数较低级别的节点（K/L除外）来说相当好。这真的取决于哪种类型的地方很重要。如果高层节点的位置很重要，那么问题评论中的 ABCDEFG 顺序可能是最好的。

我认为没有适用于所有情况的完美解决方案。

Answer 3

我认为（使用中缀排序）已经差不多了。考虑二叉树中的每个节点，除了根之外，都有三个邻居，并且在一维内存布局中，实际上只有两个可以相距 1。此外，没有想到很多其他有用的顺序。

我写了一个小 Perl script which compares the default ordering to a depth-first prefix ordering and an infix ordering. You can throw the output at Gnuplot 以获得以下情节（编辑：包括 van-Emde-Boas 布局）：

你可以看到原始排序对于小树距离的局部性相对较差，前缀和中缀排序都更好。不过，中缀排序产生了三者中最好的行为（例如，树距离为 3 的节点平均相隔 6 个内存索引）。它也是一条几乎是线性的曲线，这应该是一个很好的指标，表明你不能做得更好。 V.E.B。根据您的距离标准，评论中提到的布局至少对于较小的节点距离而言效果不佳。

为了完整起见，这是我使用的（有点快速和肮脏的）脚本：

#!/usr/bin/perl
# Compares node distances in memory for different layouts of the following
# binary tree:
#                      A
#                  /       \
#              B               C
#            /   \           /   \
#          D       E       F       G
#         / \     / \     / \     / \
#        H   I   J   K   L   M   N   O
#       / \ / \ / \ / \ / \ / \ / \ / \
#       P Q R S T U V W X Y Z 0 1 2 3 4

# Calculates the real node distance.
sub dist($$)
{
  my ($i, $j) = @_;
  return 0 if ($i == $j);
  ($j,$i) = ($i,$j) if ($i > $j);
  # $i<$j. Go one up from the larger node.
  return 1 + dist($i, ($j-1)>>1);
}

# Determines the average memory distance for nodes as a function of tree distance.
sub get_dists($$)
{
  my $tree = shift;     # Original tree ordering
  my $locality = shift; # Locality-based ordering

  my %dists = ();
  my %counts = ();

  for (my $i=0; $i<length($tree); $i++)
  {
    for (my $j=$i; $j<length($tree); $j++)
    {
      # Find location of $i and $j in the locality-based ordering.
      my $ni = substr($tree, $i, 1);
      my $nj = substr($tree, $j, 1);
      my $it = index($locality, $ni);
      my $jt = index($locality, $nj);
      my $d = (($i <= $j) ? ($j-$i) : ($i-$j));
      my $dt = (($it <= $jt) ? ($jt-$it) : ($it-$jt));
      my $treedist = dist($i, $j);
      $dists{$treedist} += $dt;
      $counts{$treedist}++;
    }
  }
  foreach my $k (sort keys %counts)
  {
    $dists{$k} /= $counts{$k};
  }
  return %dists;
}

my $tree = "ABCDEFGHIJKLMNOPQRSTUVWXYZ01234";    # original (breadth-first prefix) ordering
my $prefix = "ABDHPQIRSEJTUKVWCFLXYMZ0GN12O34";  # depth-first prefix ordering
my $infix = "PHQDRISBTJUEVKWAXLYFZM0C1N2G3O4";   # infix ordering
my $veb = "ABCDHPQIRSEJTUKVMFLXYMZ0GN12O34";     # V.E.B. layout (hope I got it right)

my %original_dists = get_dists($tree, $tree);
my %prefix_dists = get_dists($tree, $prefix);
my %infix_dists = get_dists($tree, $infix);
my %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 my $k (sort keys %original_dists)
{
  print "$k $original_dists{$k}\n";
}
print "e\n";
foreach my $k (sort keys %prefix_dists)
{
  print "$k $prefix_dists{$k}\n";
}
print "e\n";
foreach my $k (sort keys %infix_dists)
{
  print "$k $infix_dists{$k}\n";
}
print "e\n";
foreach my $k (sort keys %veb_dists)
{
  print "$k $veb_dists{$k}\n";
}
print "e\n";

是否有任何保留位置的方法来展平二叉树？

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

language-agnostic

algorithm

tree

binary-tree

data-structures