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

Ваши входные деревья всегда статичны? Если это так, то вы можете использовать алгоритм наименьшего общего предка, чтобы ответить на вопрос о потомках за время O (1) с конструкцией времени/пространства O (n). Запрос LCA получает два узла и спрашивает, какой из них является самым нижним узлом в дереве, поддерево которого содержит оба узла. Затем вы можете ответить на запрос IsDescentent одним запросом 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*

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

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

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

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

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

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

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

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

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

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

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

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

Start[v] ‹= Start[u] и End[u] ‹= End[v].

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

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