Добавление элемента в дерево

Рассмотрим вершину дерева a, в которой нарушается баланс после добавления элемента. Все нижесказанное будет верным, если это не оговорено особо, и для случая какого-либо изменения одного из поддеревьев вершины a, приводящего к удлинению/укорачиванию соответствующего дерева на 1.

Будем предполагать, что для всех вершин, лежащих ниже a, баланс по модулю не превосходит 1.

Пусть, для определенности, элемент добавляется в левое поддерево вершины a. Справа и сверху от вершины будем писать баланс вершины после добавления новой вершины, а рядом, в круглых скобках, - баланс до добавления. Высоту соответствующего данной вершине поддерева будем писать справа снизу от вершины.

То, что дерево после добавления вершины разбалансировалось, означает, что до добавления вершины [a]=1, а после добавления [a]=2 (будем обозначать баланс вершины с помощью квадратных скобок: баланс вершины a = [a]). Возможны три случая баланса вершины b после изменения дерева: 1, 0, -1. Рассмотрим их

1.После добавления вершины [b]=1 или 0 (или изменения поддерева с корнем b) ([ b]=1 соответствует удлинению левого поддерева b)

На рисунке варианты [b]=1 или 0 печатаются через слеш (косую черту).

Приведенную здесь перестановку вершин (с соответствующими поддеревьями) будем называть правым поворотом (в соответствии с перемещением вершин d-b-a).

Будем обозначать высоты дерева с корнем в вершине xh_x, а баланс этой вершины [x].

Пусть h_e=h, тогда для случая [b]=1

h_d=h+1 (т.к. [b]=1)

h_b=h+2

h_a=h+3

h_c=h (т.к. [a]=2)

Из чего сразу следует, что после правого поворота

[a]=[b]=0

[c], [d], [e] не изменились

Т.о. данное дерево сбалансировалось. При этом, если изменение дерева произошло в результате добавления вершины, его высота не изменилась. Действительно, перед добавлением вершины h_d=h из чего следует, что перед добавлением вершины h_a=h+2. После добавления высота не изменилась. Т.о. в случае [b]=1 процесс балансировки дерева завершен.

Для случая [b]=0 нарисованное дерево тоже остается сбалансированным:

h_d=h (т.к. [b]=0)

h_b=h+1

h_a=h+2

h_c=h-1 (т.к. [a]=2)

Из чего сразу следует, что после правого поворота

[a]=1, [b]=-1

[c], [d], [e] не изменились.

Однако высота всего нарисованного дерева изменяется (была до добавления h_a=h+1, стала h_a=h+2).

Итак, если перед изменением дерева h_b=1, то процесс балансировки завершен. Иначе, может разбалансироваться родитель вершины a, и для нее нужно выполнить тот же алгоритм.

2.После добавления вершины [b]=-1 (или изменения поддерева с корнем b) (удлинение правого поддерева b)

Описанная перестановка может быть проведена за два вращения: левого g-e-b и правого b-e-a:

Возможны три варианта баланса c: [c]=0/1/-1. Пусть h_e=h, тогда, в соответствии с возможными вариантами [c] имеем:

h_f=h-1/h-1/h-2

h_g=h-1/h-2/h-1

h_d=h-1

h_b=h+1

h_a=h+2

h_c=h-1

Из чего сразу следует, что после правого поворота

[b]=0/0/1

[a]=0/-1/0

[e]=0

[d], [f], [g], [c] не изменились.

Т.о. данное нарисованное дерево сбалансировалось. При этом, если изменение дерева произошло в результате добавления вершины, его высота не изменилась. Действительно, перед добавлением вершины h_e=h-1 из чего следует, что перед добавлением вершины h_a=h+1. После добавления высота не изменилась. Т.о. в случае добавления вершины при [b]=-1 процесс балансировки дерева завершен.

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

Итак, мы доказали следующую теорему

Теорема. В сбалансированное дерево поиска, состоящее из N вершин, можно добавить одну вершину за время O(log₂ N). При этом, для балансировки дерева потребуется не более двух поворотов.

Отметим, что хотя балансировок требуется не более двух, весь процесс балансировки, все же, требует времени O(log₂ N), т.к. требуется еще найти – в какой вершине следует производить балансировку.

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