在 O(1) 的二叉树中查找前辈

Question

我遇到了以下问题

我有一个给定的二叉树（不一定是 BST）和两个指针 (x,y)，我需要在 O(1) 复杂度中确定 X 是否是 Y 的前任，我可以添加尽可能多的字段想要.

我正在考虑在将下一个 child 插入树时将每个前任添加为一个字段，但是这样我如何在 O(1) 复杂度中搜索 X 是否是 Y 的前任。

Answer 1

如果您使用节点，请添加一个无符号整型字段，将其命名为L，从 1 开始，根节点。

递归插入时，取前一个节点的值乘以2，向右加1，向左乘2。

您将得到一棵包含 L 个值的树，如下所示：

          1
         / \
        /   \ 
       /     \
      /       \
     10       11 
    /  \      / \
   /    \    /   \
 100   101 110   111
  \             /  \
 1001         1110  1111
   /
10010

祖先 P 应该有一个值 P.L 使得 P.L 是 C.L 的子字符串并且 P.L 中的位数严格小于 C.L 中的位。

树的 L 以 10 为基数的值是：

          1
         / \
        /   \ 
       /     \
      /       \
     2         3
    /  \      / \
   /    \    /   \
  4     5  6     7
  \             / \
   9          14   15
   /
  18

如果你有两个指针，如果你采用 log_2(L)，你将得到该数字中的位数 L，如果你注意到，它代表你在树中的级别.

所以如果：

// Parent (ancestor) has equal or more bits?
if (log(P.L) >= log(C.L)) {

  // parent is not an ancestor because it
  // is either lower in tree, or at same level
}

如果检查通过，从 bits(C) 中减去 bits(P)，这将告诉您 C.L 比 P.L 多多少位。或者，C比P低了多少级。

int D = log(C.L) - log(P.L)

由于 C 较低，我们为计算 C.L 值所做的一切就是将父 L 值乘以二（左移）一些次数，如果我们是将 C 移回右侧（除以 2）D 次，前 D 位应该匹配。

// Divide by 2, D times 
int c = C.L >> D

// Is P.L a substring of C.L?
if (c == P.L) {

  // P.L is a substring of C.L
  // means P is an ancestor of C
}

// If we get here, C is below P in the tree, but C
// is not in a subtree of P because the first `D bits don't match`

本质上，我们使用整数作为字符串来跟踪插入的路径，并且我们使用位操作来检查 C.L 是否是 P.L 在常数时间内的子字符串。

注意，如果您使用数组，那么 P.L 和 C.L 只是您要检查的节点的索引。

在 O(1) 的二叉树中查找前辈

Find predecessors in a BinaryTree in O(1)

binary-tree

time-complexity