时间戳

首页 > 解决方案 > 在 O(1) 中找到二叉树中的前辈

time-complexity - 在 O(1) 中找到二叉树中的前辈

问题描述

我一直遇到以下问题

我有一个给定的二叉树（不一定是 BST）和两个指针(x,y)，我需要在 O(1) 复杂度中查找 X 是否是 Y 的前身，我可以添加任意数量的字段。

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

标签： time-complexitybinary-tree

解决方案

如果您使用节点，请添加一个 unsigned int 字段，调用它L，从 1 开始，以 root 开头。

当您递归插入时，取前一个节点的值并乘以 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。

以 10 为底的树的L值为：

          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(P)从减去bits(C)，这将告诉您 CL 比 PL 多多少位，或者，C比 低多少级P。

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

由于C较低，并且我们计算C.L值所做的只是将父L值乘以 2（左移）一定次数，如果我们要将 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只是您要检查的节点的索引。

推荐阅读