алгоритм - Как эффективно объединить два бинарных дерева поиска?

Question

Я не спрашиваю, как объединить два бинарных дерева поиска, как этот вопрос сделал Как эффективно объединить два BST?

Я действительно спрашиваю, как объединить два дерева.Таким образом, если все узлы дерева A меньше любого узла дерева B, мы можем объединить два дерева.Но как мне сделать это эффективно?

Моя идея состоит в том, чтобы найти минимум дерева B, а затем позволить дереву A быть левым дочерним элементом минимума (дерево B).

Это достаточно просто ивремя составляет O(height of B).

Но, думаю, у этого решения есть некоторые проблемы:

1. это может привести к тому, что окончательное большое дерево больше не будет сбалансировано
2. Что еслинаихудшее время выполнения - O(h), где h - максимальная высота двух деревьев?

Собственно, книга " Руководство по разработке алгоритмов " содержит этот акциз,Достаточно ли моего простого решения для этого упражнения?

Операция сцепления берет два набора S1 и S2, где каждый ключ в S1 меньше любого ключа в S2, и объединяет их вместе. Дайте алгоритм объединения двух двоичных деревьев поиска в одно двоичное дерево поиска .Наихудшее время выполнения должно быть O (h), где h - максимальная высота двух деревьев.

Спасибо

Answer 1

Пусть A будет меньшим множеством.Предположим, что x = максимум_элемента (A) и y = минимум_элемента (B).

Мы знаем, что x z = (x+y)/2, и сделайте A его левым поддеревом, а B - его правым поддеревом.удалить добавленный узел (с ключом z) из этого BST.

Answer 2

Я собираюсь определить:

• h_A = максимальная высота A
• h_B = максимальная высота B
• h = min(h_A, h_B)

Наихудшее время выполнения вашего решения - O(h_B), которое происходит, когда глубина min(B) равна h_B.

Вопрос задан для O(h) худшего случая. Решение O(h) предпочтительнее, поскольку, если h_B намного больше, чем h_A, нам лучше присоединить B к правому дочернему элементу max(A), чем к вашему текущему решению, которое присоединяет A к левый ребенок min(B).

Вот как это сделать:

1. Рекурсивный ход вниз по правому краю A и по левому краю B.
2. Прекратите движение, когда доберетесь до или max(A) или min(B).
3. Возможна одна из трех вещей:
   1. Вы получили max(A). В этом случае установите max(A).right = B
   2. Вы получили min(B). В этом случае установите min(B).left = A
   3. Вы получили max(A) и min(B). В этом случае выполните любой из указанных выше вариантов.

В большинстве случаев мы прошли h_A или h_B шагов, в зависимости от того, что меньше. То есть h шагов. Присоединение одного дерева к элементу является постоянным. Таким образом, время работы O (ч).