Конкатенация/Слияние/Присоединение два дерева AVL
Предположите, что у меня есть два дерева AVL и что каждый элемент от первого дерева меньше тогда любой элемент от второго дерева. Что самый эффективный путь состоит в том, чтобы связать их в одно единственное дерево AVL? Я искал везде, но ничто не нашел полезным.
2 ответа
Предполагая, что вы можете уничтожить входные деревья:
- Удалите самый правый элемент для левого дерева и используйте его для построения Новый корневой узел, чей левый ребенок - это левое дерево, и чей правый ребенок - это правильное дерево: o (log n)
- определите и установите этот коэффициент баланса узла: O (log n). В (временном) нарушении инварианта фактор баланса может быть за пределами диапазона {-1, 0, 1}
- вращается, чтобы получить коэффициент баланса в диапазоне: o (log n) вращения: o (log n)
Таким образом, вся операция может быть выполнена в O (log n).
Редактировать: на второй мысль легче рассуждать о вращении в следующем алгоритме. Это также довольно быстрее:
- определяют высоту обоих деревьев: O (log n).
Предполагая, что правильное дерево выше (другой случай - симметричный): - Удалить крайний элемент из
левогодерева (вращающийся и регулировка его вычисленной высоты при необходимости). Пустьnбыть таким элементом. O (log n) - в правом дереве, навигация налево, пока не достигнете узла, поддерева которого находится не более одного 1 выше
, левый. ДавайтеRбыть таким узлом. O (log n) Замените этот узел новым узлом со значением N, а поддерев
слеваиR. O (1)
По конструкции новый узел AVL-сбалансированный, а его поддерево 1 вышеR.увеличивать баланс своего родителя соответственно. O (1)
- и ребакантность, как вы, после вставки. O (log n)
Я подозреваю, что вам просто придется пройти одно дерево (надеюсь, чем меньше) и индивидуально добавляют каждое из его элементов на другое дерево. Операции AVL INSERT / DELETE не предназначены для обработки добавления целого поддерева одновременно.