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

Как объединить два двоичных дерева поиска, сохраняющих свойство BST?

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

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

Ответы

Ответ 1

Наафф ответил немного подробнее:

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

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

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

Джонатан

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

Теперь сложность всей задачи равна O (n1 + n2).

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

Ответ 5

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

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

Объединенный BST (BST, Массив)

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

Найдите индекс в массиве, левый элемент которого < BST.rootnode и правый элемент >= BST.rootnode say Index. if (BST.rootNode.leftNode == null)//i.e Нет слева node { вставьте весь массив из индекса в 0 влево от BST и  } еще {  Объединенный BST (BST.leftNode, Array {0 to Index}) }

if (BST.rootNode.rightNode == null)//i.e Нет права node { вставьте весь массив из Index в Array.size вправо от BST  } еще {  Объединенный BST (BST.rightNode, Array {Index to Array.size}) }

возвращает BST.

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

Ответ 6

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