任意树的DFS顺序比较函数

Question

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

- 节点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遍历是一种方法，但我更喜欢不需要计算和存储该信息的数学解决方案。

- logworthy

---

你可以使用一些术语来代替你所写的内容: "ideal tree" -> "complete binary tree", "traversal .. is constant" -> "traversal .. is deterministic" - justhalf

谢谢，我已经更新了问题。 - logworthy

Answer 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是一个函数，它清除除最高有效位之外的所有位。我使用这个问题中的Sir Slick的msb32()测试了以下代码：
int base(unsigned int x){return 1<<(msb32(x)-1);}

- AShelly

Answer 2

最佳性能的算法是由FUD提出的那个，因为你只需要遍历一次树，然后比较就只是O(1)。

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

思路如下：

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

观察2：如果两个节点不在同一深度，则通过观察父节点总是先于子节点访问的规律，我们取深度更深的节点的祖先与深度较浅的节点在相同深度上的节点进行比较。然后使用观察1进行比较。

使用完全二叉树中的数字系统，您可以通过取 n/2 来获得节点 n 的父节点。因此，在获取每个节点的深度（可以在 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: https://dev59.com/DXRB5IYBdhLWcg3wSVcI
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;
}

- justhalf

---

节点编号为n的深度可以使用floor(log(2, n))在O(1)时间内获取。不过我不确定您的回答，我们找到深度之后，会将其除以深度差异的2次方吗？那么如何比较深度相同的两个节点，例如2和3呢？ - logworthy

“log(2,n)”在理论上不是“O(1)”，但可以这样假设。如果您有相同深度的节点，则使用第一个观察结果，编号较高的节点后访问。除法是为了获取更深节点的祖先。祖先将与其他节点处于相同的深度。 - justhalf

Answer 3

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

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

那么比较函数就只需要是这样的

int cmp(i,j):
    return v[i]<v[j]

- FUD

---

当然。我想要一个数学解决方案，不涉及编写DFS算法或随着树的大小增加而增加的存储。我将更新问题以进行说明。 - logworthy

深度优先搜索对于具有结构的树来说效率低下，例如在2^10-1个节点的完全二叉树中查找索引为3的节点需要进行2^9次遍历。我们知道，在完全二叉树中，左子树的节点数是非根节点总数的一半，因此我们可以轻松地推导出一个公式。 - Vikram Bhat

Answer 4

这是一个数学问题的解决方案，但是我无法得到该方程式的闭合形式：

要找到树中总共有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。

注意：方程式可以在O(log(k))时间内找到节点k的索引值，而log函数使用floor运算符来获取离散值。

- Vikram Bhat

Answer 5

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

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

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

3. 如果2的幂相同，则具有较低差异的那个应排在具有较高差异的那个前面。

4. 对于我们的情况，在与7相同的行中计算13的父级。这将是13 / 2^(7和13之间级别差异)。

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

编辑：如建议所述，删除了不必要的第3步。

- Abhishek Bansal

---

你不需要步骤2和3。步骤4和5将覆盖所有情况。 - justhalf