O (1) алгоритм, чтобы определить, является ли узел потомком другого узла в многолинейном дереве?

Question

Представьте себе следующее дерево:

    A
   / \
  B   C
 / \   \
D   E   F

Я ищу способ запроса, если, например, F является потомком A (примечание: F не обязательно должен быть прямым потомком A), что в данном конкретном случае было бы правдой. Только ограниченное количество потенциальных родительских узлов необходимо протестировать с большим пулом потенциальных потомков.

При проверке того, является ли узел потомком узла в потенциальном родительском пуле, его необходимо проверить на ВСЕ потенциальные родительские узлы.

Вот что придумал:

• Преобразовать многоканальное дерево в три, т.е. назначить следующие префиксы каждому узлу в вышеприведенном дереве:

   A = 1
   B = 11
   C = 12
   D = 111
   E = 112
   F = 121
  

• Затем зарезервируйте массив битов для каждого возможного размера префикса и добавьте родительские узлы, с которыми нужно проверять, то есть, если C добавлен в пул потенциальных родительских узлов, выполните:

    1    2    3  <- Prefix length
  
  *[1]  [1]  ...
   [2] *[2]  ...
   [3]  [3]  ...
   [4]  [4]  ...
   ...  ...
  

• При проверке, является ли узел потомком потенциального родительского узла, возьмите его префикс trie, ищите первый символ в первом «массиве префиксов» (см. Выше) и, если он присутствует, ищите второй префикс. символ во втором «массиве префиксов» и т. д., т. е. проверка F приводит к:

   F = 1    2    1
  
     *[1]  [1]  ...
      [2] *[2]  ...
      [3]  [3]  ...
      [4]  [4]  ...
      ...  ...
  

  так что да F, является потомком C.

Этот тест выглядит как наихудший случай O (n), где n = максимальная длина префикса = максимальная глубина дерева, поэтому его наихудший случай точно равен очевидному способу просто подняться вверх по дереву и сравнить узлы. Однако это работает намного лучше, если тестируемый узел находится в нижней части дерева, а потенциальный родительский узел находится где-то наверху. Объединение обоих алгоритмов уменьшит оба худших сценария. Однако нехватка памяти вызывает беспокойство.

Есть ли другой способ сделать это? Любые указатели очень ценятся!

Answer 1

Ваши входные деревья всегда статичны? Если это так, то вы можете использовать алгоритм Lowest Common Ancestor для ответа на вопрос о потомках в O (1) времени с O (n) временной / пространственной конструкцией. Запросу LCA дается два узла и спрашивается, какой узел является самым низким в дереве, поддерево которого содержит оба узла. Затем вы можете ответить на запрос IsDescendent одним запросом LCA, если LCA (A, B) == A или LCA (A, B) == B, то один является потомком другого.

Этот алгоритм Topcoder дает подробное обсуждение проблемы и несколько решений на различных уровнях сложности / эффективности кода.

Answer 2

Я не знаю, подойдет ли это вашей проблеме, но один из способов сохранить иерархии в базах данных, с быстрыми функциями «дай мне все от этого узла и ниже», - это сохранить «путь».

Например, для дерева, которое выглядит так:

    +-- b
    |
a --+       +-- d
    |       |
    +-- c --+
            |
            +-- e

вы бы сохранили строки следующим образом, предполагая, что буква в вышеприведенном дереве является "id" каждой строки:

id    path
a     a
b     a*b
c     a*c
d     a*c*d
e     a*c*e

Чтобы найти всех потомков определенного узла, вы должны выполнить запрос «STARTSWITH» для столбца пути, т.е. все узлы с путем, который начинается с a*c*

Чтобы выяснить, является ли конкретный узел потомком другого узла, вы увидите, начинается ли самый длинный путь с самого короткого пути.

Так, например:

• e является потомком, поскольку a*c*e начинается с a
• d является потомком c, так как a*c*d начинается с a*c

Будет ли это полезно в вашем случае?

Answer 3

Обход любого дерева потребует шагов "глубины дерева".Поэтому, если вы поддерживаете сбалансированную древовидную структуру, можно доказать, что вам потребуются операции O (log n) для операции lookup .Из того, что я понимаю, ваше дерево выглядит особенным, и вы не можете поддерживать его сбалансированным образом, верно?Так что O (n) будет возможно.Но в любом случае это плохо при создании дерева, поэтому вы, вероятно, умрете, прежде чем использовать lookup в любом случае ...

В зависимости от того, как часто вам понадобится lookup операция по сравнению с вставка , вы можете решить заплатить в течение вставка для поддержания дополнительной структуры данных.Я бы предложил хеширование, если вам действительно нужно амортизироваться O (1) .При каждой операции вставки вы помещаете всех родителей узла в хеш-таблицу.По вашему описанию это может быть O (n) элементов на данном insert .Если вы сделаете n вставки , это звучит плохо (к O (n ^ 2) ), но на самом деле ваше дерево не может ухудшить , что плохо, так что вы, вероятно, получите общий амортизируемый общий размер O (n log n) .(на самом деле, log n зависит от степени деградации вашего дерева. Если вы ожидаете, что оно будет максимально деградировано, не делайте этого.)

Итак, вы заплатитео O (log n) на каждую вставку и получите хэш-таблицу эффективности O (1) для поиска .

Answer 4

Для M-way дерева, вместо вашего битового массива, почему бы просто не сохранить двоичный "идентификатор trie" (используя M бит на уровень) с каждым узлом?Для вашего примера (при условии M == 2) : A=0b01, B=0b0101, C=0b1001, ...

Затем вы можете выполнить тест в O (1):

bool IsParent(node* child, node* parent)
{ 
   return ((child->id & parent->id) == parent->id)
}

Вы можете сжатьпамять для хранения (lg2 ​​(M)) битов на уровень, если у вас есть быстрая функция FindMSB () , которая возвращает позицию набора старших значащих бит:

mask = (1<<( FindMSB(parent->id)+1) ) -1;
retunr (child->id&mask == parent->id);

Answer 5

При обходе предварительного заказа каждый набор потомков является смежным.Например,

A B D E C F
+---------+ A
  +---+ B
    + D
      + E
        +-+ C
          + F

Если вы можете выполнить предварительную обработку, тогда все, что вам нужно сделать, - это пронумеровать каждый узел и вычислить интервал по потомкам.

Если вы не можете выполнить предварительную обработку, тогда link / cut tree обеспечивает производительность O (log n) как для обновлений, так и для запросов.

Answer 6

Взгляните на Модель вложенного набора Очень эффективно выбирать, но слишком медленно обновлять

Answer 7

Вы можете ответить на запрос вида "Является ли узел A потомком узла B?"в постоянное время, просто используя два вспомогательных массива.

Предварительно обработайте дерево, посетив в порядке «Глубина-Первый», и для каждого узла A сохраните его время начала и окончания при посещении в двух массивах Start [] и End [].

Итак, допустим, что End [u] и Start [u] - соответственно время окончания и начала посещения узла u.

Тогда узел u является потомком узла v тогда и только тогда, когда:

Start [v] <= Start [u] и End [u] <= End [v].</p>

и все готово, проверка этого условия требует только двух поисков в массивах Start и End