Найти предшественников в BinaryTree в O (1) - PullRequest
Новая
       19

Найти предшественников в BinaryTree в O (1)

0 голосов
/ 01 мая 2018

У меня возникли проблемы со следующим вопросом

У меня есть заданное двоичное дерево (не обязательно BST) и два указателя (x,y), и мне нужно найти, если X является предшественником Y в сложности O (1), я могу добавить столько полей, сколько захочу.

Я думал о добавлении каждого предшественника в качестве поля, когда я вставляю следующего потомка в дерево, но как я могу искать, если X является предшественником Y в сложности O (1).

1 Ответ

0 голосов
/ 01 мая 2018

Если вы используете узлы, добавьте поле unsigned int, назовите его 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(P) из bits(C), это скажет вам, сколько битов C.L больше, чем P.L. Или сколько уровней C ниже P. 

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

Поскольку C меньше, и все, что мы делали для вычисления C.L, это умножение родительских значений L на два (сдвиг влево) некоторое количество раз, если бы мы переместили С обратно вправо. (делим на 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 - это просто индексы узлов, которые вы хотели бы проверить.

...