Более локализованный, эффективный алгоритм Lowest Common Ancestor с учетом множества двоичных деревьев?

Question

У меня есть несколько двоичных деревьев, хранящихся в виде массива. В каждом слоте есть либо ноль (или ноль; выберите ваш язык), либо фиксированный кортеж, в котором хранятся два числа: индексы двух «детей». Ни у одного узла не будет только одного дочернего элемента - ни одного, ни двух.

Думайте о каждом слоте как о двоичном узле, который хранит только указатели на его дочерние элементы, а не присуще значение.

Возьмем эту систему двоичных деревьев:

    0       1
   / \     / \
  2   3   4   5
 / \         / \
6   7       8   9
   / \
 10   11

Связанный массив будет:

   0       1       2      3     4      5      6      7        8     9     10    11
[ [2,3] , [4,5] , [6,7] , nil , nil , [8,9] , nil , [10,11] , nil , nil , nil , nil ]

Я уже написал простые функции для поиска прямых родителей узлов (просто путем поиска спереди, пока не найдется узел, содержащий дочерний элемент)

Кроме того, давайте скажем, что в соответствующие моменты времени оба дерева находятся на глубине от нескольких до нескольких тысяч уровней.

Я бы хотел найти функцию

P(m,n)

чтобы найти наименьшего общего предка m и n - для более формального определения, LCA определяется как «самый низкий» или самый глубокий узел, в котором m и n являются потомками (дочерние элементы или дочерние элементы дочерних элементов и т. Д.). .). Если его нет, nil будет верным возвращением.

Несколько примеров, приведенных для нашего данного дерева:

P( 6,11)   # => 2
P( 3,10)   # => 0
P( 8, 6)   # => nil
P( 2,11)   # => 2

Основной метод, который мне удалось найти, - это метод, использующий трассировку Эйлера, которая превращает данное дерево (добавление узла A в качестве невидимого родителя 0 и 1 со «значением» -1) в :

A-0-2-6-2-7-10-7-11-7-2-0-3-0-A-1-4-1-5-8-5-9-5-1-A

И из этого просто найдите узел между заданными вами m и n, который имеет наименьшее число; Например, чтобы найти P (6,11), найдите 6 и 11 на трассе. Число между ними, которое является самым низким, равно 2, и это ваш ответ. Если между ними находится A (-1), вернуть nil.

 -- Calculating P(6,11) --

A-0-2-6-2-7-10-7-11-7-2-0-3-0-A-1-4-1-5-8-5-9-5-1-A
      ^ ^        ^
      | |        |
      m lowest   n

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

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

Но для этого потребуется подняться с уровня, скажем, 3025, обратно на 0, дважды , чтобы посчитать генерацию, и сначала использовать крайне неэффективный алгоритм подъема, а затем восхождение наверх.

Есть ли другие лучшие способы?

---

Разъяснения

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

Это не гарантирует, что если n в поколении X, то в поколении (X-1) нет узлов, которые больше n. Например:

        0
       / \
      /   \
     /     \
    1       2        6
   / \     / \      / \
  2   3   9  10    7   8
     / \              / \
    4   5            11 12

- допустимая древовидная система.

Кроме того, артефакт способа построения деревьев заключается в том, что два непосредственных потомка одного и того же родителя всегда будут последовательно пронумерованы.

Answer 1

Может быть, это поможет: Динамические запросы LCA на деревьях .

Аннотация:

Ричард Коул, Рамеш Харихаран

Мы показываем, как сохранить данные структура на деревьях, которая позволяет следующие операции, все в постоянное время наихудшего случая . 1. Вставка листьев и внутренних узлов. 2. Удаление листьев. 3. Удаление внутренние узлы только с одним ребенком. 4. Определение наименьшего общего предка из любых двух узлов.

Конференция: Симпозиум по дискретному Алгоритмы - SODA 1999

Answer 2

Являются ли узлы в порядке, как в вашем примере, где у детей есть больший идентификатор, чем у родителя?Если это так, вы могли бы сделать что-то похожее на сортировку слиянием, чтобы найти их ... для вашего примера, родительское дерево 6 и 11:

6  -> 2 -> 0
11 -> 7 -> 2 -> 0

Так что, возможно, алгоритм будет:

left = left_start
right = right_start

while left > 0 and right > 0
    if left = right
        return left
    else if left > right
        left = parent(left)
    else
        right = parent(right)

Что будет работать как:

left    right
----    -----
 6        11    (right -> 7)
 6        7     (right -> 2)
 6        2     (left -> 2)
 2        2     (return 2)

Это правильно?

Answer 3

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

(defun lowest-common-ancestor (array node-index-1 node-index-2)
  (cond ((or (null node-index-1)
             (null node-index-2))
         nil)
        ((= node-index-1 node-index-2)
         node-index-1)
        ((< node-index-1 node-index-2)
         (lowest-common-ancestor array
                                 node-index-1
                                 (find-parent array node-index-2)))
        (t
         (lowest-common-ancestor array
                                 (find-parent array node-index-1)
                                 node-index-2))))

Answer 4

Я решил твою проблему в Хаскеле. Предполагая, что вы знаете корни леса, решение требует времени, линейного по размеру леса и постоянной дополнительной памяти. Вы можете найти полный код на http://pastebin.com/ha4gqU0n.

Решение рекурсивное, и основная идея заключается в том, что вы можете вызвать функцию на поддереве, которая возвращает один из четырех результатов:

• В поддереве нет ни m, ни n.
• В поддереве содержится m, но не n.
• В поддереве содержится n, но не m.
• В поддереве содержатся и m, и n, а индекс их наименьшего общего предка - k.

Узел без дочерних элементов может содержать m, n или ни того, ни другого, и вы просто возвращаете соответствующий результат.

Если узел с индексом k имеет двух дочерних элементов, результаты объединяются следующим образом:

join :: Int -> Result -> Result -> Result
join _ (HasBoth k) _ = HasBoth k
join _ _ (HasBoth k) = HasBoth k
join _ HasNeither r = r
join _ r HasNeither = r
join k HasLeft HasRight = HasBoth k
join k HasRight HasLeft = HasBoth k

После вычисления этого результата вы должны проверить индекс k самого узла; если k равно m или n, вы «расширите» результат операции join.

В моем коде используются алгебраические типы данных, но я осторожно предположил, что вам нужны только следующие операции:

• Получить индекс узла
• Узнайте, пуст ли узел, а если нет, найдите его двух дочерних элементов

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

Существуют различные настройки производительности, которые вы можете вставить. Например, если вы найдете корень, который имеет ровно один из двух узлов m и n, вы можете выйти сразу, потому что знаете, что общего предка , Кроме того, если вы посмотрите на одно поддерево и оно имеет общего предка, вы можете проигнорировать другое поддерево (которое я получаю бесплатно, используя ленивую оценку).

Ваш вопрос был прежде всего о том, как сэкономить память. Если линейное решение слишком медленное, вам, вероятно, понадобится вспомогательная структура данных. Пространственные компромиссы - проклятие нашего существования.