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

Question

Предположим, что у меня есть два дерева AVL и каждый элемент из первого дерева меньше, чем любой элемент из второго дерева. Каков наиболее эффективный способ объединить их в одно дерево AVL? Я искал везде, но не нашел ничего полезного.

Answer 1

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

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

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

Редактировать: Если подумать, проще рассуждать о поворотах в следующем алгоритме. Это также скорее всего быстрее:

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

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

5. соответственно увеличивать баланс своего родителя. O (1)

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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