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

Question

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

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

У меня вопрос: можем ли мы добиться большего успеха, чем O (n1 * log (n2))?

Answer 1

Ответ Нааффа с чуть более подробной информацией:

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

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

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

[1] Алгоритм создания сбалансированного BST из отсортированного списка (в Python):

def create_balanced_search_tree(iterator, n):
    if n == 0:
        return None
    n_left = n//2
    n_right = n - 1 - n_left
    left = create_balanced_search_tree(iterator, n_left)
    node = iterator.next()
    right = create_balanced_search_tree(iterator, n_right)
    return {'left': left, 'node': node, 'right': right}

Answer 2

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

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

Answer 3

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

Answer 4

Jonathan

После сортировки у нас есть список длины n1 + n2. Построение двоичного дерева из него займет время журнала (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

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

Answer 6

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

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

Объединенный BST (BST, Array)

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

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

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

возврат BST.

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

---