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

Question

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

Answer 1

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

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

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

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

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

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

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

6. и выполните повторную балансировку, как если бы вы это сделали после вставки.О (логарифм n)

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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