КОНСПЕКТ ОБЗОРНОЙ ЛЕКЦИИ

Для студентов специальности
Т1002 «Программное обеспечение информационных технологий»

(, старший преподаватель)

Вопрос 42 Сбалансированные деревья.

Сбалансированные и сильноветвящиеся деревья.

Сбалансированные деревья используются для реализации следующих основных операций:

1. Найти элемент по данному ключу,

2. Вставить элемент с заданным значением ключа,

3. Удалить элемент с заданным значением ключа.

Рекурсивно дерево[1] это конечное множество Т состоящее из одного или более элементов, таких, что

a. Имеется одна специально обозначенная вершина – корень дерева.

b. Остальные вершины (исключая корень) содержаться в m попарно непересекающихся подмножествах T1, T2,…, Tm, каждое из которых в свою очередь является деревом. Деревья T1, T2,…, Tm называются поддеревьями данного дерева. Корни этих поддеревьев называются потомками корня и обозначают r(Ti).

Количество поддеревьев данной вершины называется степенью этой вершины.

Вершина нулевой степени называется листом дерева.

Бинарное дерево это:

a. Одна вершина – корень.

b. Корень и единственный лист.

c. Дерево, в котором каждая вершина, не являющаяся листом имеет в точности двух потомков.

Корень дерева – это вершина первого уровня, все потомки вершины k-го уровня расположены на k+1 уровне.

Высота дерева – это максимальная длина пути от корня к листу или наибольший уровень вершины в дереве.

Дерево называется упорядоченным, если для каждой вершины v на множестве ее поддеревьев T1, T2,…, Tm задан относительный порядок. Потомков вершины в бинарном дереве принято называть левым и правым.

НЕ нашли? Не то? Что вы ищете?

Вершины дерева соответствуют записям информационной структуры. Каждой вершине v дерева соответствует ключ K(v). В упорядоченном дереве

K(r(T1))< K(r(T2))<…< K(r(Tm))

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

Определение АВЛ-дерева.

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

Бинарное дерево называется сбалансированным или АВЛ-деревом, если для любой вершины дерева, высота левого и правого поддеревьев отличается не более чем на единицу. Показатель сбалансированности бинарного дерева, равный +1, 0, -1,означает соответственно: правое поддерево выше, они равной высоты, левое поддерево выше. Типичная структура вершины АВЛ-дерева:

node: = record

key: = integer;{ключ вершины}

left, right: ptr,{указатели на корни левого и правого поддеревьев}

bal: balance {-1, 0, +1- показатель сбалансированности}

end

Базовые операции над АВЛ-деревьями.

Вставка элементов.

Поиск и включение элементов в АВЛ-дерево выполняется аналогично процедуре включения элемента в упорядоченное дерево.

proc search (n: integer; {искомый ключ}

var p: ptr; {указатель текущей вершины}

var h boolean); {признак изменения высоты поддерева}

begin

if p=nil then {включение элемента в дерево}

else if p^.key = n

then {нашли}

else if p^.key>n then begin {поиск в левом поддереве}

search (n, p^.left, h)

if h then {выросло левое поддерево, возможно,

необходима балансировка}

end

else begin{поиск в правом поддереве}

search (n, p^. right, h)

if h then {выросло правое поддерево, возможно,

необходима балансировка}

end

end;

end.

Операции вставки элементов в АВЛ-дерево могут нарушить его сбалансированность. Это происходит, когда для некоторой вершины, у которой одно поддерево выше другого увеличивается высота этого поддерева. Схема определения типа поворота при вставке элемента приведена в таблице 1.

V.^Bal	Выросло левое поддерево	Выросло правое поддерево
+1	LR	RR
0	RL
-1	LL
Таблица 1 Схема определения типа поворота при вставке элемента.

С учетом зеркального отображения возможны два случая нарушения балансировки:

- Однократный поворот (LL, RR)

- Двукратный поворот (LR, RL).

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

Пример вставки элемента в дерево приведен на рис 1.

Удаление элементов.

Удаление элементов из АВЛ-дерева выполняется по схеме, аналогичной удалению элементов из упорядоченного дерева:

- Если у удаляемой вершины менее двух потомков, то удаление вершины из АВЛ-дерева аналогично удалению элемента из списка.

- Если у удаляемой вершины два потомка, то она заменяется самой правой вершиной в левом поддереве, которая удаляется из дерева.

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

Bal	Уменьшилось правое поддерево	Уменьшилось левое поддерево
+1	LR	RR
0	LL
-1	RL
Таблица 2. Схема определения типа поворота при удалении элемента

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

Пример удаления элемента приведен на рис 2. В данном случае выполняется двукратная балансировка.

Оценка эффективности.

-Вельский и доказали теорему, согласно которой высота АВЛ-дерева с N внутренними вершинами заключена между log2(N+1) и 1.4404*log2(N+2)-0.328, то есть высота АВЛ-дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%. Для больших N имеет место оценка 1.04*log2(N). Таким образом, выполнение основных операций 1 – 3 требует порядка log2(N) сравнений. Экспериментально выяснено, что одна балансировка приходится на каждые два включения и на каждые пять исключений.

Определение В-дерева.

В-деревья используются для построения индекса таблиц в СУБД. Часть набора данных, считываемая в оперативную память операцией ввода-вывода, называется страницей. Размер страницы m = n до 2n, n - порядок дерева. В-деревья обладают следующими свойствами:

1) каждая страница, кроме корня, содержит m элементов, где .

2) каждая страница либо является листом, либо имеет m +1 потомка.

Замечание. Количество потомков у корня от 2 до 2n + 1.

3) все листья расположены на одном уровне.

4) Ключи на каждом листе упорядочены.

Рассмотрим схему выполнения основных операций на примере В-дерева порядка 2.

Пусть - i-ый потомок вершины v, m – количество элементов в вершине v. поддерево с корнем в вершине . Упорядоченность В-дерева означает, что для каждой вершины v

Если ключ x не найден на странице v, то возможны следующие ситуации:

1. - поиск продолжается на странице.

2. - поиск продолжается на странице.

3. - поиск продолжается на странице.

Если указанная страница не существует, то элемента x не в дереве.