Конкатенация/слияние/объединение двух деревьев AVL

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

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 будет этим элементом. О (журнал п)
3. В правом дереве перемещайтесь влево, пока не дойдете до узла, поддерево которого не более чем на 1 выше, чем left. Пусть r будет этим узлом. О (журнал п)

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

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

6. и перебалансируйте, как после вставки. О (журнал п)

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

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

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

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

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

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