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

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

    A
   / \
  B   C
 / \   \
D   E   F

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

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

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

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

     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 = максимальная длина префикса = максимальная глубина дерева, поэтому его наихудший случай точно равен очевидному способу подняться вверх по дереву и сравнить узлы. Тем не менее, это работает намного лучше, если тестируемый узел находится в нижней части дерева, а потенциальный родительский узел находится где-то наверху. Объединение обоих алгоритмов уменьшит оба худших сценария. Однако нехватка памяти вызывает беспокойство.

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

Источник

8 ответов

Решение

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

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

Источник

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

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

    +-- 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*

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

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

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

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

Источник

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

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

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

Источник

Для 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)
}

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

mask = (1<<( FindMSB(parent->id)+1) ) -1;
retunr (child->id&mask == parent->id);
Источник

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

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

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

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

Источник

Как бы то ни было, то, о чем вы здесь просите, эквивалентно проверке того, является ли класс подтипом другого класса в иерархии классов, а в реализациях, подобных CPython, это просто сделано старомодным добрым "итерацией родителей, ищущих родительский "путь".

Источник

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

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

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

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

Начало [v] <= начало [u] и конец [u] <= конец [v].

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

Источник

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

Источник
Другие вопросы по тегам