Предположим, что у меня есть два дерева AVL и что каждый элемент из первого дерева меньше, чем любой элемент из второго дерева. Каков наиболее эффективный способ объединить их в одно дерево AVL? Я искал везде, но не нашел ничего полезного.
Конкатенация/слияние/объединение двух деревьев AVL
Ответы (4)
Предполагая, что вы можете уничтожить входные деревья:
- удалите самый правый элемент левого дерева и используйте его для создания нового корневого узла, левый дочерний элемент которого является левым деревом, а правый дочерний элемент - правым деревом: O(log n)
- определить и установить коэффициент баланса этого узла: O (log n). При (временном) нарушении инварианта коэффициент баланса может быть вне диапазона {-1, 0, 1}
- повернуть, чтобы вернуть коэффициент баланса в диапазон: O(log n) оборотов: O(log n)
Таким образом, всю операцию можно выполнить за O(log n).
Редактировать: если подумать, проще рассуждать о поворотах в следующем алгоритме. Это также вполне вероятно быстрее:
- Определите высоту обоих деревьев: O(log n).
Предполагая, что правое дерево выше (другой случай симметричен): - удалить крайний правый элемент из дерева
left
(при необходимости повернув и отрегулировав его вычисленную высоту). Пустьn
будет этим элементом. О (журнал п) - В правом дереве перемещайтесь влево, пока не дойдете до узла, поддерево которого не более чем на 1 выше, чем
left
. Пустьr
будет этим узлом. О (журнал п) замените этот узел новым узлом со значением n и поддеревьями
left
иr
. O(1)
По построению новый узел является AVL-сбалансированным, а его поддерево на 1 выше, чемr
.соответственно увеличить баланс своего родителя. О(1)
- и перебалансируйте, как после вставки. О (журнал п)
h
или h+1
, где h
— высота левого дерева.
- person rareyesdev; 29.10.2014
Одно очень простое решение (которое работает без каких-либо предположений в отношениях между деревьями) таково:
- Выполните сортировку обоих деревьев в один объединенный массив (одновременно повторите оба дерева).
- Постройте дерево AVL из массива — возьмите средний элемент в качестве корня и рекурсивно примените к левой и правой половинам.
Оба шага равны O(n). Основная проблема с ним заключается в том, что он занимает O (n) дополнительного места.
Лучшее решение этой проблемы, которое я прочитал, можно найти здесь< /а>. Очень близко к ответу meriton, если вы исправите эту проблему:
На третьем шаге алгоритма навигация влево, пока не будет достигнут узел, поддерево которого имеет ту же высоту, что и левое дерево. Это не всегда возможно (см. изображение контрпримера). Правильный способ выполнить этот шаг — найти два поддерева высотой h
или h+1
, где h
— высота левого дерева
Я подозреваю, что вам просто нужно будет пройтись по одному дереву (надеюсь, меньшему) и индивидуально добавить каждый из его элементов к другому дереву. Операции вставки/удаления AVL не предназначены для единовременного добавления всего поддерева.