Объединение/объединение/объединение двух деревьев AVL

Ответ 1

Предполагая, что вы можете уничтожить входные деревья:

• удалить самый правый элемент для левого дерева и использовать его для создания нового корня node, левым дочерним элементом которого является левое дерево, а правый дочерний элемент - это правильное дерево: O (log n)
• определить и установить коэффициент node: O (log n). В (временном) нарушении инварианта коэффициент баланса может быть вне диапазона {-1, 0, 1}
• поверните, чтобы вернуть коэффициент баланса в диапазон: O (log n): O (log n)

Таким образом, вся операция может быть выполнена в O (log n).

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

• Определите высоту обоих деревьев: O (log n).
  Предполагая, что правильное дерево выше (другой случай симметричен):
• удалите самый правый элемент из дерева left (при необходимости повернув и вывернув его вычисленную высоту). Пусть n - этот элемент. O (log n)
• В правом дереве перемещайтесь влево, пока не достигнете node, чье поддерево не более чем на один выше, чем left. Пусть r - node. O (log n)

• замените node на новый node со значением n и поддеревьями left и r. O (1)
  По конструкции новый node является AVL-сбалансированным, а его поддерево 1 выше, чем r.

• соответственно увеличивает свой родительский баланс. O (1)

• и перебалансировку, как и после вставки. O (log n)

Ответ 2

Одно ультра простое решение (которое работает без каких-либо предположений в отношениях между деревьями) таково:

• Сделайте слияние обоих деревьев в один объединенный массив (одновременно итерации обоих деревьев).
• Создайте дерево AVL из массива - возьмите средний элемент в качестве корня и примените рекурсивно к левой и правой половине.

Оба этапа - это O (n). Основная проблема заключается в том, что для O (n) требуется дополнительное пространство.

Ответ 3

Лучшее решение, которое я прочитал для этой проблемы, можно найти здесь. Очень близко от ответа meriton, если вы исправите эту проблему:

На третьем этапе алгоритм перемещается влево до тех пор, пока вы не достигнете node, чье дочернее дерево имеет ту же высоту, что и левое дерево. Это не всегда возможно (см. Контрпример). Правильный способ сделать этот шаг - это два найти для поддерева с высотой h или h+1, где h - высота левого дерева

Ответ 4

Я подозреваю, что вам просто нужно пройти одно дерево (надеюсь, меньше) и индивидуально добавить каждый из его элементов в другое дерево. Операции вставки/удаления AVL не предназначены для одновременной обработки всего поддерева.