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

Naaff's answer with a little more details:

• Flattening a BST into a sorted list is O(N)
  • It's just "in-order" iteration on the whole tree.
  • Doing it for both is O(n1+n2)
• Merging two sorted lists is into one sorted list is O(n1+n2).
  • Keep pointers to the heads of both lists
  • Pick the smaller head and advance its pointer
  • This is how the merge of merge-sort works
• Creating a perfectly balanced BST from a sorted list is 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}

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

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

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

Jonathan,

После сортировки у нас есть список длины 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. Таким образом, подход должен зависеть от размеров двух деревьев.

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

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

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

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

Найти индекс в массиве, левый элемент которого < BST.rootnode, а правый элемент >=BST.rootnode, скажем Index. if(BST.rootNode.leftNode ==null ) //т.е. нет левого узла { вставьте весь массив от индекса до 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 для решения подзадачи.