Как эффективно объединить два BST?

Question

Как слить два дерева двоичного поиска, сохраняя свойство BST?

Если мы решили взять каждый элемент из дерева и вставить его в другой, сложность этого метода будет O(n1 * log(n2)), где n1 является количество узлов дерева (скажем T1), который мы расщепленные , а n2 - количество узлов другого дерева (скажем T2). После этой операции только один BST имеет n1 + n2 узлов.

Мой вопрос: можем ли мы сделать лучше, чем O (n1 * log (n2))?

Answer 1

Как насчет выравнивания обоих деревьев в отсортированных списках, слияния списков, а затем создания нового дерева?

Answer 2

• Свергнуть деревья в отсортированные списки.
• Объединить отсортированные списки.
• Создать дерево из объединенного списка.

IIRC, то есть O (n1 + n2).

Answer 3

ответ Naaff с немного более подробно:

• выпрямления BST в отсортированный список является O (N)
  • Это просто «в заказ» итерации по всему дереву.
  • Делать это для обоих O (n1 + n2)
• Объединение двух отсортированных списков в один отсортированный список является O (n1 + n2).
  • Держите указатели глав обоих списков
  • Выберите меньшую голову и продвигать его указатель
  • Это как слияние слияния-рода работ
• Создание идеально сбалансированный BST из отсортированный список - O (N)
  • Значением в середине будет корень и рекурсия.
  • В нашем случае отсортированный список имеет размер n1 + n2. так O (n1 + n2)
  • Полученное дерево будет концептуальная БСТ двоичных поиск в списке

Три стадии O (n1 + n2) приводят к O (n1 + n2)

Для n1 и n2 того же порядка, что лучше, чем O (n1 * журнал (n2))

Answer 4

Джонатан,

После сортировки, у нас есть список длины n1 + n2. Построение двоичного дерева из него займет log (n1 + n2). Это то же самое, что и сортировка слияния, только на каждом рекурсивном шаге мы не будем иметь член O (n1 + n2), как и в алгоритме сортировки слиянием.Таким образом, временной сложностью является log (n1 + n2).

Теперь сложность всей проблемы - O (n1 + n2).

Также я бы сказал, что этот подход хорош, если два списка сопоставимы. Если размеры не сопоставимы, лучше вставить каждый узел маленького дерева в большое дерево. Это займет время O (n1 * log (n2)). Например, если у нас есть два дерева размером 10 и другое размером 1024. Здесь n1 + n2 = 1034 где n1log (n2) = 10 * 10 = 100. Такой подход должен зависеть от размеров двух деревья.

Answer 5

O (n1 * log (n2)) является средним сценарием, даже если у нас есть 2 слияния любого несортированного списка в BST. Мы не используем тот факт, что список отсортирован или BST.

По мне Предположим, что один BST имеет элементы n1, а другой имеет n2 элементов. Теперь конвертируйте один BST в список отсортированных массивов L1 в O (n1).

Merged БСТ (БСТ, массив)

, если (Array.size == 0) возвращают BST , если (Array.size == 1) вставить элемент в BST. return BST;

Найти индекс в массиве, левый элемент < BST.rootnode и правый элемент> = BST.rootnode say Index. если (BST.rootNode.leftNode == NULL) // т.е. без левого узла { вставить все массив из индекса 0, в левом из BST и } еще { Merged BST (BST.leftNode, массив { 0 Индекс})}

если (BST.rootNode.rightNode == NULL) // т.е. нет права узла { вставить все массив из индекса не Array.size в праве BST } еще { Объединенный BST (BST.rightNode, Array {Index to Array.size}) }

возвращение BST.

Этот алгоритм будет принимать < < времени, чем O (n1 * log (n2)), поскольку каждый раз, когда мы разбиваем массив и BST, обрабатываем подзадачу.

---

Answer 6

Идея заключается в использовании итеративного обходного пути. Мы используем два дополнительных стека для двух BST. Поскольку нам нужно печатать элементы в отсортированной форме, всякий раз, когда мы получаем меньший элемент из любого из деревьев, мы печатаем его. Если элемент больше, то мы возвращаем его обратно в стек для следующей итерации.