Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. В появившемся окне Добавление таблицы выделить имя таблицы “Студенты”®Добавить®Закрыть.
  2. В себя соотнесение с элементами, составляющими более
  3. Возможные темы дебатов с элементами политического кейса
  4. ГЛАВА ПЯТНАДЦАТАЯ КАК ПОВАЛИТЬ ДЕРЕВО
  5. Дерево Добра и Зла
  6. Добавление бобышки
  7. Добавление выпадающих меню

Рассмотрим вершину дерева 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).

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

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

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

hb=h+2

ha=h+3

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

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

[a]=[b]=0

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

 

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

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

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

hb=h+1

ha=h+2

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

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

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

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

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

 

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

 

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

 

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

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

hf=h-1/h-1/h-2

hg=h-1/h-2/h-1

hd=h-1

hb=h+1

ha=h+2

hc=h-1

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

[b]=0/0/1

[a]=0/-1/0

[e]=0

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

 

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

 

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

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

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

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


Дата добавления: 2015-10-30; просмотров: 155 | Нарушение авторских прав


Читайте в этой же книге: Структуры данных. | Struct SStack3 st3; | Стек. Реализация 5 (на основе указателя на указатель). | Struct SQueue | Стандартная ссылочная реализация списков | InsertData( value, head, current); | Реализация L2-списка на основе двух стеков | Поиск пути в графе с наименьшим количеством промежуточных вершин | Поиск кратчайшего пути в графе | Добавление элемента |
<== предыдущая страница | следующая страница ==>
Сбалансированные и идеально сбалансированные бинарные деревья поиска| Разбиение дерева по разбивающему элементу

mybiblioteka.su - 2015-2024 год. (0.007 сек.)