4

想象一个完整的二叉树，其中每个深度级别的节点从左到右编号。

  • 节点 1 有子节点 2 和 3。
  • 节点 2 有孩子 4 和 5。
  • 节点 3 有孩子 6 和 7。

等等

在深度 D 将有 2^D 节点，编号为 2^D ... 2^(D+1)-1

任何深度的完整树的深度优先搜索遍历是确定性的。

例如，将始终遍历深度为 4 的树：1,2,4,8,9,5,10,11,3,6,12,13,7,14,15。

我正在寻找一种方法来对数字列表进行排序，根据它们在任何树的 DFS 遍历中的位置。

特别是，我想要一个比较函数，它可以采用两个数字并确定在 DFS 遍历中哪个先出现。

有任何想法吗？

预先计算某个最大树大小的 DFS 遍历是一种方法，但我更喜欢不需要计算和存储该信息的数学解决方案。

4

5 回答 5

1

具有最佳性能的算法将是 FUD 建议的算法，因为您只需要遍历树一次，然后比较将是O(1).

但是，如果您不想遍历整个树，而只想要一个比较器，那么有一个O(log n)比较器（可以优化为O(log log n)，或者实际上O(1)）。

这个想法是：

观察1：如果两个节点的深度相同，编号较高的节点将被稍后遍历。

观察 2：如果两个节点不在同一深度上，则通过注意始终先访问父节点，然后再访问后代，我们将较深节点的祖先与较浅节点的深度相同。然后使用观察 1 进行比较。

使用完整二叉树中的数字系统，您可以通过获取节点的父n节点n/2。所以，在得到每个节点的深度之后（可以在 中完成O(log n)，或预先计算），比如说d1 < d2，我们将更深的节点除以2^(d2-d1)（幂可以在 中完成O(log p)，在这种情况下p是O(log n)，所以它是O(log log n)）。然后看看哪个更大=）

在 C++ 中：

// This method can be modified to be faster
// See: http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-an-i
int depth(int n){
    int result=-1;
    for(;n>0; result++, n/=2);
    return result;
}

bool n1_before_n2(int n1, int n2){
    int d1 = depth(n1);
    int d2 = depth(n2);
    if(d1>d2) n1 >>= (d1-d2);
    if(d2>d1) n2 >>= (d2-d1);
    return n1<n2;
}
于 2013-11-15T04:55:57.617 回答
1

这是@Abhishek 答案的C 实现：

//returns -1 if a before b; 0 if same; else 1
int treesort(unsigned int a,unsigned int b)
{
  int diff, swap=1, side=0;
  unsigned int ra, rb;
  if (a==b) return 0;  
  //ensure deeper node is always in b.
  if (b<a) { int t=a;a=b;b=t;swap=-1;}
  //treat 0 as before everything else
  if (a==0) return -1*swap;
  //clear all but the msb
  ra=base(a); rb=base(b);
  //move up to same level, tracking child side
  while (rb!=ra)  { side=b&1;rb/=2;b/=2; }
  //compare parents at same level
  diff = (b-rb)-(a-ra);
  //if same parent, answer depends on side.
  if (diff==0) diff = side;
  //restrict to [-1,1], be sure to handle swap
  return (diff>0?-1:1)*swap;
}

base是一个清除除最高有效位之外的所有内容的函数。我
int base(unsigned int x){return 1<<(msb32(x)-1);}使用这个问题中的 Slick 爵士的 msb32()进行了测试。

于 2013-11-15T20:38:28.730 回答
0

您可以预先计算完整树中的最大深度级别。并为每个节点分配一组增加的值，例如在您的深度 4 树中

v[1]=1, v[2]=3, v[4]=3 ...

那么比较函数就是

int cmp(i,j):
    return v[i]<v[j]
于 2013-11-15T04:26:37.587 回答
0

如果您注意到这种模式，您可以尝试以下方法。我不确定，它可能需要一些改进，但它为您提供了一些进一步探索的想法。

  1. 对于每个节点，找到小于该值的 2 的最高幂。例如，如果我们比较 7 和 13，那么对于 7，它将是 4，对于 13，它将是 8。

  2. 现在计算这些值及其各自 2 的幂之间的差值。对于 7，它将是 3，对于 13，它将是 5。

  3. 如果两者的幂相同，则差值较小的先于差值较大的。

  4. 对于我们的例子，计算 13 与 7 在同一行中的父级。这将是 13 / 2^（7 和 13 之间的级别差）。

因此，13 的父级 = 13 / 2^1 = 6。
由于 6 < 7，我们可以说 13 在 7 之前。

编辑：按照建议，删除了不必要的第 3 步。

于 2013-11-15T05:11:10.810 回答
0

这是问题的数学解决方案，但我无法得到方程的封闭形式：-

要在总节点 N 的树中找到节点 k 的 DFS 索引： -

DFS-order(k) = DFS-order((k-1)/2) + 2^(log(N+1) - log((k-1)/2) - 1)       if k is odd

DFS-order(k) = DFS-order(k/2) + 1             if k is even 

Base Case: DFS-order(1) = 0

您可以找到上述方程的封闭形式，我认为这是更高层次的数学。

解释：-

对于奇数节点，我们首先遍历父节点的所有左子树节点，并为新索引加 1。我们知道，左子树的一半节点都以节点的父节点为根，不包括父节点。完整 BT 中的节点总数2^d - 2不包括根。左子树有一半2^(d-1) - 1。d 是父级树根的深度。以节点 k 为根的树的深度为Total depth - log(k)。总深度为log(N+1)。因此，左子树中的节点数为2^(log(N+1) - log((k-1)/2) - 1) - 1。因此，我们将 1 用于从父节点到当前节点的另一次遍历final sum = 2^(log(N+1) - log((k-1)/2) - 1)。我们将它添加到父索引以获取当前节点索引DFS-order(k) = DFS-order((k-1)/2) + 2^(log(N+1) - log((k-1)/2) - 1)。

对于偶数节点，它的索引是父索引 + 1 是微不足道的

注意：方程可以找到节点 k 在 O(log(k)) 时间和日志函数中的索引，使用地板运算符来获取离散值。

于 2013-11-15T12:56:29.367 回答