Слияние двух деревьев

Для двух сбалансированных деревьев поиска T₁ и T₂ таких, что все элементы в T₁ меньше или равнывсех элементов в T₂ : слияние деревьев в одно дерево поиска T.

Выбираем из дерева T₂ наименьший элемент v (самый левый) и удаляем его из дерева T₂ . Элемент v называется стыковочным. Для него верно: T₁£ v£ T₂ .

Возможна ситуация, когда стыковочный элемент присутствует уже в постановке задачи.

Будем, для определенности, предполагать, что высота дерева T₁ больше или равна высоте дерева T₂.

Рассмотрим правую ветвь дерева T₁: {v₁,…,v_K}. В силу сбалансированности дерева имеем: h(v_i) - h(v_i+1) £ 2, тогда на этой ветви найдется вершина v_{l ,} такая что

h(v_l) = h(T₂) или h(v_l) = h(T₂)+1

Сольем дерево с корнем в v_l и T₂ с помощью стыковочной вершины v и подставим новое дерево на место старой вершины v_l.

Вершина v_l и все дерево, с нее начинающееся, окажутся сбалансированными. Высота же дерева, начинающегося с v_l, увеличится на 1, т.к. h(T₂) £h(v_l).

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

Если, при этом, длина данного поддерева восстановится до значения, которому она была равна до слияния деревьев, то далее процесс проверки сбалансированности производить не надо (т.к. дерево T₁ до слияния было сбалансированным). Иначе, процесс проверки следует продолжить.

Отметим, что, в отличии от добавления к дереву одной вершины, в данном случае после уравновешения одной вершины процесс может не завершиться, т.к. возможен следующий вариант

Этот вариант не мог реализоваться при добавлении одной вершины к дереву. В этом случае до слияния деревьев высота дерева с корнем a была равна h+1, а после слияния она стала равной h+2.

Итак, в силу построения алгоритма слияния двух сбалансированных деревьев, верна

Теорема. Для двух сбалансированных деревьев поиска T₁ и T₂ , состоящих из N₁ и N₂ вершин, имеющих высоты h₁ и h₂, и элемента v, таких, что все элементы в T₁ меньше или равны v и v меньше или равно всех элементов в T₂ : слияние деревьев с помощью стыковочного элемента v в одно сбалансированное дерево поиска T можно произвести за время T=O(log₂ (N₁+N₂)) или за время T=O(|h₁-h₂|). Указанные деревья T₁ и T₂ можно слить за время T=O(log₂ (N₁+N₂)).

Отметим здесь, что для слияния двух сбалансированных деревьев требуется сначала извлечения стыковочный элемент из дерева с большей высотой, поэтому эта операция требует большего времени, чем слияние деревьев с готовым стыковочным элементом.

---

Дата добавления: 2015-10-30