Курсовая работа
Сбалансированные деревья
Основные понятия 3
Включение в сбалансированное дерево 5
Удаление из сбалансированного дерева 12
Заключение18
Задачи 18
Приложение 19
Основные понятия
Связанный граф без циклов называется деревом.
Определим терминологию деревьев:
• Корнем дерева называют единственную вершину, находящуюся вверху « первернутого » дерева;
• Самые нижние вершины называются листьями;
• Вершину называют внутренней, если она не является ни корнем, и ни листом;
• О вершине, которая находится непосредственно над другой вершиной, говорят, что она – родитель (предок), а вершина, которая расположена непосредственно под другой вершиной, называется потомком.
Считают, что корень дерева расположен на первом уровне. Его потомки находятся на втором и т.д. максимальный уровень какой – либо вершины дерева называется глубиной, или высотой дерева. Число потомков вершины называется ее степенью. Максимальное значение этих степеней есть степень дерева.
Суть двоичных деревьев, широко распространенных в программировании, следует из названия. Степень дерева равна двум. Вершина (узел) дерева может иметь не более двух потомков, их называют левыми и правыми. Двоичные (бинарные) деревья поиска (подкласс двоичных деревьев) характеризуются тем, что значение информационного поля, связанного с вершиной дерева, больше любого соответствующего значения из левого поддерева и меньше, чем содержимое любого узла его правого поддерева. Описание этой вершины имеет вид:
Type Ref = ^Item;
Item = Record
Key: Integer;
Left, Right: Ref; (0)
End;
С таким деревом можно легко осуществлять простейшие операции: вставка, удаление, обход дерева. Деревья упрощают оперирование с данными, поскольку имеют ряд преимуществ по сравнению с другими структурами данных, как то: динамический принцип выделения памяти под переменные, быстрый поиск переменной с нужным числовым полем и наглядность работы с переменными.
Двоичное дерево считается идеально сбалансированным, если для каждой его вершины количество вершин в его левом и правом поддеревьях различается не более чем на 1. Для одних и тех же данных, например, целых чисел от 1 до N (в зависимости от порядка их поступления в обработку), структура двоичного дерева поиска будет различной. Возможны варианты как от идеально сбалансированного дерева, так и до простого линейного списка, когда или все левые, или все правые ссылки узлов равны nil. Реализация операций восстановления идеальной сбалансированности при случайной вставке или удалении элемента из двоичного дерева поиска, разумеется, возможна, однако она не рассматривается в учебной литературе из-за ее сложности.
Рассмотрим сбалансированные деревья по тому определению, которое было предложено Г.М. Андельсоном – Вельским и Е.М. Ландисом в 1962г.
Критерий сбалансированности следующий
Дерево называются сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на единицу.
Деревья, удовлетворяющие этому условию, часто называют АВЛ-деревьями (по фамилиям их изобретателей). Будем называть их просто сбалансированными деревьями, так как их критерий сбалансированности оказывается наиболее подходящим. (Отметим, что все сбалансированные деревья так же являются АВЛ-сбалансированными.)
Это определение не только простое, но также приводит к легко выполнимой балансировке, а средняя длина поиска остается практически такой же, как у идеально сбалансированного дерева.
Со сбалансированными деревьями можно выполнять следующие операции за O(Log(n)) единицу времени даже в наихудшем случае:
1. Найти узел с данным ключом.
2. Включить узел с данным ключом.
3. Удалить узел с данным ключом.
Это является прямым следствием теоремы, доказанной Андельсоном – Вельским и Ландисом, которая утверждает, то сбалансированное дерево никогда не будет более чем на 45% выше соответствующего идеально сбалансированного дерева независимо от количества узлов. Если обозначить высоту сбалансированного дерева с n узлами через hb(n), то
log(n+1)<= hb(n)<=1.4404*log(n+2)-0.328 (1)
Разумеется, оптимум достигается, если дерево идеально сбалансировано, при n=2k-1. Но какова структура наихудшего АВЛ-сбалансированного дерева?
Чтобы найти максимальную высоту h всех сбалансированных деревьев с n узлами, возьмем фиксированное h и попробуем построить сбалансированное дерево минимальным количеством узлов. Такая стратегия рекомендуется, поскольку, как и в случае минимального h, это значение может быть достигнуто только при некоторых, определенных значениях n.
Рис. 1. Деревья Фибоначчи высотой 2,3 и 4.
Обозначим такое дерево с высотой h через Th. Очевидно, что T0 – пустое дерево, а T1- дерево с одним узлом. Чтобы построить дерево Th для h>1, зададим корень с двумя поддеревьями, которые также имеют минимальное число узлов. Следовательно, поддеревья также являются T – деревьями. Очевидно, что одно поддерево обязано иметь высоту h-1, а другому позволено иметь высоту на единицу меньше, т.е. h-2. на рис. 1 показаны деревья высотой 2, 3 и 4. Поскольку принцип их организации напоминает принцип построения чисел Фибоначчи, подобные деревья называют деревьями Фибоначчи. Они определяются следующим образом:
1. Пустое дерево есть дерево Фибоначчи с высотой 0.
2. Один узел есть дерево Фибоначчи с высотой 1.
3. Если Th-1 и Th-2 – деревья Фибоначчи с высотой h-1 и h-2, то Th=< Th-1, X, Th-2> есть дерево Фибоначчи с высотой h.
4. Никакие другие деревья не являются деревьями Фибоначчи.
Число узлов в Th определяется простым рекуррентным соотношением:
N0=0, N1=1, Nh= Nh-1+ Nh-2, (2)
Ni – это количество узлов, для которых можно получить наихудший случай (верхнюю границу h).
Включение в сбалансированное дерево
Посмотрим, что может произойти, когда в сбалансированное дерево включается новый узел. Пусть дан корень R с левыми и правыми поддеревьями L и R. Предположим, что в L включается новый узел, вызывая увеличение его высоты на 1.
Рис.2. Сбалансированное дерево.
Возможны три случая:
1. hL= hR : L и R становятся неравной высоты, но критерий сбалансированности не нарушается.
2. hL< hR : L и R приобретают равную высоту, т.е. сбалансированность даже улучшается не нарушается.
3. hL> hR : критерий сбалансированности нарушается, и дерево нужно перестраивать.
Рассмотрим дерево на рис 2. Узлы с ключами 9 и 11 можно вставить без балансировки; дерево с корнем 10 становится односторонним (случай 1), а с корнем 8 улучшает свою сбалансированность (случай 2). Однако включение узлов с корнями 1, 3, 5 или 7 требует последующей балансировки.
При внимательном изучении этой ситуации можно обнаружить, что имеются лишь две существенно различные возможности, требующие индивидуального подхода. Оставшиеся могут быть получены симметричными преобразованиями этих двух. Случай 1 определяется включением ключа 1 или 3 в дерево на рис. 2, случай 2 – включением ключа 5 или 7.
Случай 1. Случай 2.
Рис.3. Несбалансированность, возникающая при включении.
Эти два случая в общем виде показаны на рис. 3, где поддеревья обозначены прямоугольниками, а увеличение высоты при включении указано перечеркнутыми квадратами. Простые преобразования этих двух структур восстанавливают нужную сбалансированность. Их результат приведен на рис. 4; отметим, что допускаются перемещения лишь в вертикальном направлении, в то время как относительное горизонтальное расположение показанных узлов и поддеревьев должно оставаться без изменений.
Случай 1. Случай 2.
Рис. 4. Восстановление баланса.
Алгоритм включения и балансировки полностью определяется способом хранения информации о сбалансированности дерева. Крайнее решение состоит в хранении этой информации полностью неявно в самой структуре дерева. Но в этом случае показатель сбалансированности узла должен заново вычисляться каждый раз, когда узел затрагивается включением, что приводит к чрезвычайно высоким затратам. Другая крайность – явно хранить показатель сбалансированности в информации, связанной с каждым узлом. Тогда определение типа узла расширяется до
Type node = record
key: integer;
Count: integer;
Left, right: ref; (3)
Bal: -1..+1
End;
В дальнейшем будем интерпретировать показатель сбалансированности узла как высоту его правого поддерева минус высота его левого поддерева и будем строить алгоритм, исходя из узлов описанного в (3) типа.
В общих чертах процесс включения узла состоит из последовательности трех этапов:
1. Следовать по пути поиска, пока не окажется, что ключа нет в дереве.
2. Включить новый узел и определить новый показатель сбалансированности.
3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла.
Хотя этот метод и требует некоторой избыточной проверки (если сбалансированность установлена, то для предков соответствующего узла ее проверять уже не надо), будем придерживаться этой, очевидно, корректной схемы, так как ее можно реализовать с помощью простого расширения уже разработанной процедуры поиска с включением из программы для идеально сбалансированных деревьев. Эта процедура описывает операцию поиска для каждого отдельного узла, и благодаря рекурсивной формуле ее можно дополнить операцией, выполняемой «по дороге назад вдоль пути поиска». На каждом шаге должна передаваться информация о том, увеличилась ли высота поддерева (в которое произведено включение). Поэтому добавим к списку параметров процедуры булевскую переменную h, означающую «высота поддерева увеличилась». Очевидно, что h должна быть параметром-переменной, поскольку используется для передачи результата.
Теперь предположим, что алгоритм возвращается к узлу с левой ветви (см. рис. 3) с указанием, что ее высота увеличилась. Мы должны различать три возможные ситуации в зависимости от высоты поддеревьев перед включением:
1. hL< hR : P^.bal=+1, предыдущая несбалансированности в p уравновешивается.
2. hL= hR : P^.bal=0 вес склонился влево.
3. hL> hR : P^.bal=-1, необходима балансировка.
В третьем случае показатель сбалансированности корня левого поддерева (P^.bal) определяет, который из случаев (1 или 2 на рис. 3) имеет место. Если левое поддерево этого узла тоже выше правого, то мы имеем дело со случаем 1, иначе – со случаем 2. (В этом случае левое поддерево корня не может иметь показатель сбалансированности, равный 0.) Необходимые операции балансировки полностью заключаются в обмене значениями ссылок (указателей, «поинтеров»). Фактически, ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному «повороту» двух или трех узлов. Кроме «вращения» ссылок следует также изменить соответствующие показатели сбалансированности узлов. Подробно это показано в процедуре поиска, включения и балансировки (4).
Принцип работы алгоритма показан на рис. 5. Рассмотрим бинарное дерево (а), которое состоит только из двух узлов. Включение ключа 7 вначале дает несбалансированное дерево (т.е. линейный список). Его балансировка требует однократного правого (RR) поворота, давая в результате идеально сбалансированное дерево (b). Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным левым (LL) поворотом (d). Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5. Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (LR), результатом является дерево (e). теперь при следующем включении потерять сбалансированность может лишь узел 5. Действительно, включение узла 6 должно привести к четвертому виду балансировки, описанному в (4): двукратному повороту направо и налево (RL). Окончательное дерево показано на рис. 5 (f). С эффективностью алгоритма включения в сбалансированное дерево связаны следующие два особо интересных вопроса:
1. Если все n! Перестановок n включений появляются с одинаковой вероятностью, то какова ожидаемая высота формируемого сбалансированного дерева?
2. Какова вероятность, что включение приведет к балансировке?
Приведем пример процедуры вставки узла в дерево.
Procedure Search(X:Byte; Var Q:Ref; Var H:Boolean); Создание сбалансированного дерева
Var Q1,Q2:Ref; H=False
Begin
If Q=Nil Then Слова нет в дереве, включить его
Begin
New(Q);
H:=True;
With Q^ Do
Begin Непосредственная процедура инициализации вершины
Key:=X;
Count:=1;
Left:=Nil;
Right:=Nil;
Bal:=0
End
End
Else
If X<q^.key then="" Если="" вставляемая="" величина="" меньше="" вершины,="" рекурсивно="" входим="" опять="" в="" нее,="" считая="" корнем="" уже="" следующую="" вершину="" и="" будем="" сравнивать="" включаемый="" элемент="" с="" ней.<br="">Begin
Search(X,Q^.Left,H);
If H Then Выросла левая ветвь
Case Q^.Bal Of
1:
Begin
Q^.Bal:=0;
H:=False;
End;
0: Q^.Bal:=-1;
-1: Необходима балансировка
Begin
Q1:=Q^.Left;
If Q1^.Bal=-1 Then
Begin Однократный LL-поворот
Q^.Left:=Q1^.Right;
Q1^.Right:=Q;
Q^.Bal:=0;
Q:=Q1;
End
Else Двукратный LR-поворот
Begin
Q2:=Q1^.Right;
Q1^.Right:=Q2^.Left;
Q2^.Left:=Q1;
Q^.Left:=Q2^.Right;
Q2^.Right:=Q;
If Q2^.Bal= -1 Then Q^.Bal:=+1 Else Q^.Bal:=0;
If Q2^.Bal=+1 Then Q1^.Bal:=-1
Else Q1^.Bal:=0;
Q:=Q2;
End;
Q^.Bal:=0;
H:=False
End
End
End
Else If X>Q^.Key Then Симметричную операцию проводим, если включаемый элемент больше значения корня. Рекурсивно вызываем процедуру Search для правого поддерева рассматриваемой вершины. для правого поддерева рассматриваемой вершины.
Begin
Search(X,Q^.Right,H);
If H Then Выросла правая ветвь
Case Q^.Bal Of
-1:
Begin
Q^.Bal:=0;
H:=False;
End;
0:Q^.Bal:=+1;
1 : Begin Балансировка
Q1:=Q^.Right;
If Q1^.Bal=+1 Then
Begin Однократный RR-поворот
Q^.Right:=Q1^.Left;
Q1^.Left:=Q;
Q^.Bal:=0;
Q:=Q1;
End
Else Двукратный RL-поворот
Begin
Q2:=Q1^.Left;
Q1^.Left:=Q2^.Right;
Q2^.Right:=Q1;
Q^.Right:=Q2^.Left;
Q2^.Left:=Q;
If Q2^.Bal=+1 Then Q^.Bal:=-1
Else Q^.Bal:=0;
If Q2^.Bal=-1 Then Q1^.Bal:=+1
Else Q1^.bal:=0;
Q:=Q2;
End;
Q^.Bal:=0;
H:=False;
End;
End;
End
Else
Begin
Q^.Count:=Q^.Count+1;
H:=False;
End;
End; Конец процедуры вставки элемента
(4)
Математический анализ этого сложного алгоритма пока не произведен. Эмпирические проверки показывают, что ожидаемая высота сбалансированного дерева, которое строится в (4), равна h=log(n)+c, где с – малая константа (с~0,25). Это значит, что на практике АВЛ-сбалансированные деревья ведут себя так же, как идеально сбалансированные деревья, хотя с ними намного легче работать. Эмпирически можно также предположить, что в среднем балансировка необходима приблизительно один раз на каждые два включения. При этом однократный и двукратный повороты одинаково вероятны. Понятно, что пример на рис. 5 явно был тщательно подобран, чтобы показать как можно больше поворотов при минимальном количестве включений.
Из-за сложности операций балансировки считается, что сбалансированные деревья следует использовать лишь в том случае, когда поиск информации происходит значительно чаще, чем включение. Это, в частности, верно потому, что узлы таких деревьев поиска обычно для экономии памяти реализуются как плотно упакованные записи. «Скорость» изменения показателей сбалансированности, занимающих только по два разряда каждый, и обращения к ним часто является решающим фактором, определяющим эффективность операции перебалансировки. Эмпирические оценки говорят, что сбалансированные деревья теряют большую часть своей привлекательности, если нужна плотная упаковка записи. Но это уже относится к разделу хранения информации непосредственно на компьютере, а не к ее представлению, поэтому не будем рассматривать проблемы, связанные с размахом хранения динамической информации на носителе.
Рис. 5. Включение в сбалансированное дерево.
Удаление из сбалансированного дерева
Представляя структуру сбалансированных деревьев, можем предположить, что удаление в случае сбалансированных деревьев будет еще более сложным, чем включение. Это верно, хотя операция балансировки остается в основном такой же, что и при включении. В частности, балансировка состоит из однократного или двукратного поворота узла.
Удаление из сбалансированного дерева показано на рис.6. Простыми случаями являются удаления терминальных узлов и узлов с одним потомком. Если же узел, который нужно удалить, имеет два поддерева, то, как и в обычных деревьях, будем заменять его самым правым узлом левого поддерева. Как и в случае включения (4), добавляется булевский параметр-переменная h, означающий, что «высота поддерева уменьшилась». Вопрос о перебалансировке рассматривается только при h=true. Значение true присваивается h при нахождении и удалении узла или если сама балансировка уменьшает высоту поддерева. В программе (5) в виде процедур вводим две (симметричные) операции балансировки, поскольку обращение к ним встречается более чем в одной точке алгоритма исключения. Отметим, что BalanceL используется при уменьшении высоты левого поддерева, а BalanceR – при уменьшении высоты правого.
Рис. 6 иллюстрирует работу нашей процедуры. Из исходного сбалансированного дерева (а) последовательно исключаются вершины с ключами 4, 8, 6, 5, 2, 1 и 7 и получаются деревья (b) .. (h).
Исключение ключа 4 выглядит просто, поскольку он представляет собой терминальную вершину. Однако в результате получается несбалансированная вершина 3. Соответствующая операция балансировки требует единственного (LL) – поворота. Удаление вершины 8 проходит без балансировки «с минимальными потерями» – ее физически заменяем ее полем left. При исключении вершины 6 вновь требуется балансировка. В этот момент одиночным (RR) – поворотом балансируется правое поддерево вершины 7. Удаление корня дерева 5 проходит «по сценарию» - заменяем его правым элементом из левого поддерева; «запас прочности» баланса нашего дерева еще терпит такую операцию. Исключение вершины 2, хотя само по себе простое, поскольку вершина имеет лишь одного потомка, приводит к усложненному двукратному (RL) – повороту. И четвертый случай: безболезненно удалив вершину 1, проведем двукратный (LR) – поворот при изъятии вершины 7, вместо которой вначале помещался самый правый элемент ее левого поддерева, т.е. вершина с ключом 3.
Рис.6. Исключение из сбалансированного дерева.
Приведем пример элемента программы, отвечающий за удаление элемента из дерева.
Procedure Delete(X:Integer; Var Q:Ref; Var H:Boolean); Удаление узла сбалансированного дерева
Var P:Ref; Значение H в данном случае будет False
Procedure BalanceL(Var Q:Ref; Var H:Boolean);
Var Q1,Q2:Ref; Проводится при H=True, левая ветвь стала короче
B1,B2:-1..1;
Begin Помня, что H, т.е. левая ветвь стала короче
Case Q^.Bal Of Дальнейшие действия осуществляем, исходя из значения показателя сбалансированности для данной вершины – поле Bal
-1:Q^.Bal:=0;
0:
Begin
Q^.Bal:=1;
H:=False;
End;
1: Трубуется балансировка
Begin
Q1:=Q^.Right;
B1:=Q1^.Bal;
If B1>=0 Then Однократный RR-поворот
Begin
Q^.Right:=Q1^.Left;
Q^.Left:=Q;
If B1=0 Then
Begin
Q^.Bal:=1;
Q1^.Bal:=-1;
H:=False;
End
Else begin
q^.bal:=0; q1^.bal:=0;
q:=q1;
end;
end
else Двукратный RL-поворот Begin
Q2:=Q1^.Left;
B2:=Q2^.Bal;
Q1^.Left:=Q2^.Right; Q2^.Right:=Q1;
Q^.Right:=Q2^.Left;
Q2^.Left:=Q;
If B2=+1 Then Q^.Bal:=-1 Else Q^.Bal:=0;
If B2=-1 Then Q1^.Bal:=+1 Else Q1^.Bal:=0; Q:=Q2;
Q2^.Bal:=0;
End;
End;
End; Конец процедуры балансировки по L
End;
Procedure BalanceR (Var Q:Ref; Var H:Boolean); При реализации данной процедуры всегда
Var Q1,Q2:Ref; H=True, правая ветвь стала короче
B1,B2: -1..1;
Begin Будем помнить, что H, правая ветвь стала короче
Case Q^.Bal Of
1:Q^.Bal:=0; Дальнейшие действия осуществляем, исходя из значения показателя сбалансированности для данной вершины – поле Bal
0:
Begin
Q^.Bal:=-1;
H:=False;
End;
-1: В этом случае необходима балансировка
Begin
Q1:=Q^.Left;
B1:=Q1^.Bal;
If B1<=0 Then
Begin Однократный LL-поворот Q^.Left:=Q1^.Right;
Q1^.Right:=Q;
If B1=0 Then
Begin
Q^.Bal:=-1;
Q1^.Bal:=1;
H:=False;
End
Else
Begin
Q^.Bal:=0;
Q1^.Bal:=0;
End;
Q:=Q1;
End
Else Двукратный LR-поворот
Begin
Q2:=Q1^.Right;
B2:=Q2^.Bal;
Q1^.Right:=Q2^.Left;
Q2^.Left:=Q1;
Q^.Left:=Q2^.Right;
Q2^.Right:=Q;
If B2=-1 Then Q^.Bal:=+1 Else Q^.Bal:=0;
If B2=+1 Then Q1^.Bal:=-1 Else Q1^.Bal:=0;
Q:=Q2;
Q2^.Bal:=0;
End
End
End
End; Конец балансировки по R– процедуры balanceR
Procedure Del(Var R:Ref;Var H:Boolean); Это, что называется, «чистая» процедура «физического» удаления.
Будем помнить, что при вызове процедуры восстанавливается значение H=False, и в этом режиме происходит удаление вершины
Begin
If R^.Right<>Nil Then
Begin
Del(R^.Right,H);
If H Then BalanceR(R,H)
End
Else
Begin
P^.Key:=R^.Key;
P^.Count:=R^.Count;
R:=R^.Left;
H:=True;
End
End; Конец подпроцедуры удаления – процедуры Del
Begin
If Q=Nil Then Ключа в дереве нет
Begin
WriteLn ( 'Дерево пусто');
H:=False;
End
Else
If X<q^.key then="" В="" зависимости="" от="" соотношений="" значений="" вершин,="" входим="" рекурсивно="" в="" левое="" или="" правое="" поддерево="" вершины,="" с="" целью="" найти="" удаляемый="" элемент.="" Рекурсивная="" процедура="" будет="" считать="" эту="" вершину="" корнем="" дерева.<br="">Begin
Delete(X,Q^.Left,H);
If H Then BalanceL (Q,H);
End
Else
If X>Q^.Key Then
Begin
Delete(X, Q^.Right, H);
If H Then BalanceR(Q,H)
End
Else
Begin Удаление Q^
P:=Q;
If P^.Right=Nil Then
Begin
Q:=P^.Left;
H:=True;
End
Else
If P^.Left=Nil Then
Begin
Q:=P^.Right;
H:=True;
End
Else
Begin
Del(P^.Left,H);
If H Then BalanceL(Q,H);
End;
End
End; Конец большой процедуры удаления
(5)
К счастью, исключение любого элемента из любого сбалансированного дерева можно в самом худшем случае провести за O(log(n)) операций. Однако не следует упускать из виду существенное различие в проведении процедур включения и исключения. В то время как включение одного ключа может привести самое большое к одному повороту (двух или трех вершин), исключение может потребовать поворотов во всех вершинах вдоль пути поиска. Рассмотрим, например, исключение из дерева Фибоначчи самой правой вершины.
В этом случае исключение любой одной вершины приводит к уменьшению высоты дерева, и кроме того, исключение самой правой вершины требует максимального числа поворотов. Таким образом, мы имеем дело с самой неудачной вершиной и самым неудачным случаем сбалансированного дерева – достаточно редкая комбинация. А вообще, какова вероятность поворотов? Визуально наблюдаем, что на каждые два включения встречается один поворот, а при исключении поворот происходит даже в одном случае из пяти. Поэтому исключение из сбалансированного дерева почти столь же просто или столь же сложно, что и включение.
Заключение
Анализируя алгоритм реализации работы со сбалансированными деревьями, предложенный Н. Виртом, приходим к выводу, что это достаточно экономная структура хранения данных, а тем более для современных ЭВМ.
Но возникает вполне естественный, и к тому же интересный вопрос: а не упростится ли логика, если в каждом узле ввести адрес связи к родителю?
В приложении к этой работе приведен пример программной реализации принципа сбалансированных деревьев описанным выше методом. Рассмотрим же некоторые задачи, представляющие интерес при работе с данной структурой.
Задачи
Для самостоятельной работы можно придумать задачи, связанные с вставкой, удалением, сменой местами элементов по ключам или ветвям.
1. Проверить наличие заданного элемента в дереве.
2. Подсчет суммы элементов дерева.
3. Определение наибольшего (наименьшего) элемента в дереве.
4. Подсчет количества элементов в дереве.
5. Сравнение двух деревьев.
6. Определение высоты дерева.
7. Определить количество нечетных чисел.
8. Вычислить сумму элементов дерева, кратных 3.
9. Определить число вершин в дереве на каждом уровне.
10. Число вершин в правом и левом поддеревьях определенной вершины.
11. Построить дерево с 12 узлами, чтобы его высота была максимальной. В какой последовательности нужно вводить элементы, чтобы наша процедура сформировала это дерево?
Рассмотрим последний пример немного подробнее.
Рассмотрим такую последовательность включения элементов: 10, 5, 20, 30, 3, 6, 15, 2, 13, 25, 35, 40. Сразу сознаемся, что это подобранный пример. Составленный таким образом. Что включая элементы именно в такой последовательности, получим максимальную длины дерева с 12 элементами – 4. Этот факт не требует доказательства, так как элементы вставлялись постоянно вправо, но с тем расчетом, чтобы постоянно поддерживать балансировку во всех узлах дерева. Как и прежде. Длина правого и левого поддерева отличается на каждом этапе не более чем на 1.
А алгоритм формирования нужного нам дерева прост: нужно вводить его элементы построчно, так как оно выглядит у Вас на бумаге
Литература
1. Вирт Н., - Алгоритмы + структуры данных = программы, - М.: Мир, 1985.
2. Вир Н., Алгоритмы и структуры данных, - М., 1989.
3. Кондратьева С.Д., - Введение в структуры данных, - М.: Издательство МГТУ им. Баумана, 2000.
4. Окулов С.М., - Основы программирования. Часть 4: учебное пособие, - Киров, Издательство ВГПУ, 2001.
Приложение
Пример программного кода для реализации работы со структурой данных «Сбалансированные деревья» по схеме, предложенной в [1].
Program Example;
Uses CRT;
Const N=10;
Type Ref=^Item; Описываем поля вершин дерева
Item=Record
Key: Byte;
Count:Byte;
Left:Ref ;
Right:Ref ;
Bal:-1..1;
End;
Var Q,L,R:Ref; Используемые при работе переменные
X,Y,C,Xc:Byte;
J,K:Integer;
H:Boolean;
Ch:Char;
Level:Integer;
Procedure WriteTreel (Q:Ref ) ; Вывод дерева на экран
Var X,Y,S,T,B,ZeroX,ZeroY,Labl,Line,R:Integer;
Procedure Init;
Var Bin:Integer;
Begin
Bin:=1;
Repeat Bin:=Bin*2 Until (N Div Bin)=0;
Labl:=Round(Bin/2)*6;
Line:=1 ;
ZeroX:=Round((80-Labl-3)/2) ;
ZeroY:=5;
R:=Round(Labl/2);
End;
Procedure OutTree (Q:Ref; R,Line:Integer);
Var I:Integer;
Begin
X:=ZeroX+R;
Y:=ZeroY+Line;
GotoXY(X,Y);
Write (Q^.Key);
Delay(10);
Line:=Line+1;
B:=1;
If Q^.Left <> Nil Then
Begin
For I:=1 To Line Do B:=B*2;
S:=R-Round(Labl/B);
OutTree (Q^.Left,S,Line);
End;
If Q^.Right<>Nil Then
Begin
For I:=1 To Line Do B:=B*2;
T:=R+Round(Labl/B);
OutTree(Q^.Right,T,Line);
End;
End;
Begin
Init;
OutTree(Q,R,Line);
End;
Procedure Search(X:Byte; Var Q:Ref; Var H:Boolean); Создание сбалансированного дерева
Var Q1,Q2:Ref; H=False
Begin
If Q=Nil Then Слова нет в дереве, включить его
Begin
New(Q);
H:=True;
With Q^ Do
Begin Непосредственная процедура инициализации вершины
Key:=X;
Count:=1;
Left:=Nil;
Right:=Nil;
Bal:=0
End
End
Else
If X<q^.key then="" Если="" вставляемая="" величина="" меньше="" вершины,="" рекурсивно="" входим="" опять="" в="" нее,="" считая="" корнем="" уже="" следующую="" вершину="" и="" будем="" сравнивать="" включаемый="" элемент="" с="" ней.<br="">Begin
Search(X,Q^.Left,H);
If H Then Выросла левая ветвь
Case Q^.Bal Of
1:
Begin
Q^.Bal:=0;
H:=False;
End;
0: Q^.Bal:=-1;
-1: Необходима балансировка
Begin
Q1:=Q^.Left;
If Q1^.Bal=-1 Then
Begin Однократный LL-поворот
Q^.Left:=Q1^.Right;
Q1^.Right:=Q;
Q^.Bal:=0;
Q:=Q1;
End
Else Двукратный LR-поворот
Begin
Q2:=Q1^.Right;
Q1^.Right:=Q2^.Left;
Q2^.Left:=Q1;
Q^.Left:=Q2^.Right;
Q2^.Right:=Q;
If Q2^.Bal= -1 Then Q^.Bal:=+1 Else Q^.Bal:=0;
If Q2^.Bal=+1 Then Q1^.Bal:=-1
Else Q1^.Bal:=0;
Q:=Q2;
End;
Q^.Bal:=0;
H:=False
End
End
End
Else If X>Q^.Key Then Симметричную операцию проводим, если включаемый элемент больше значения корня. Рекурсивно вызываем процедуру Search для правого поддерева рассматриваемой вершины. для правого поддерева рассматриваемой вершины.
Begin
Search(X,Q^.Right,H);
If H Then Выросла правая ветвь
Case Q^.Bal Of
-1:
Begin
Q^.Bal:=0;
H:=False;
End;
0:Q^.Bal:=+1;
1 : Begin Балансировка
Q1:=Q^.Right;
If Q1^.Bal=+1 Then
Begin Однократный RR-поворот
Q^.Right:=Q1^.Left;
Q1^.Left:=Q;
Q^.Bal:=0;
Q:=Q1;
End
Else Двукратный RL-поворот
Begin
Q2:=Q1^.Left;
Q1^.Left:=Q2^.Right;
Q2^.Right:=Q1;
Q^.Right:=Q2^.Left;
Q2^.Left:=Q;
If Q2^.Bal=+1 Then Q^.Bal:=-1
Else Q^.Bal:=0;
If Q2^.Bal=-1 Then Q1^.Bal:=+1
Else Q1^.bal:=0;
Q:=Q2;
End;
Q^.Bal:=0;
H:=False;
End;
End;
End
Else
Begin
Q^.Count:=Q^.Count+1;
H:=False;
End;
End; Конец процедуры вставки элемента
Procedure Delete(X:Integer; Var Q:Ref; Var H:Boolean); Удаление узла сбалансированного дерева
Var P:Ref; Значение H в данном случае будет False
Procedure BalanceL(Var Q:Ref; Var H:Boolean);
Var Q1,Q2:Ref; Проводится при H=True, левая ветвь стала короче
B1,B2:-1..1;
Begin Помня, что H, т.е. левая ветвь стала короче
Case Q^.Bal Of Дальнейшие действия осуществляем, исходя из значения показателя сбалансированности для данной вершины – поле Bal
-1:Q^.Bal:=0;
0:
Begin
Q^.Bal:=1;
H:=False;
End;
1: Трубуется балансировка
Begin
Q1:=Q^.Right;
B1:=Q1^.Bal;
If B1>=0 Then Однократный RR-поворот
Begin
Q^.Right:=Q1^.Left;
Q^.Left:=Q;
If B1=0 Then
Begin
Q^.Bal:=1;
Q1^.Bal:=-1;
H:=False;
End
Else begin
q^.bal:=0; q1^.bal:=0;
q:=q1;
end;
end
else Двукратный RL-поворот Begin
Q2:=Q1^.Left;
B2:=Q2^.Bal;
Q1^.Left:=Q2^.Right; Q2^.Right:=Q1;
Q^.Right:=Q2^.Left;
Q2^.Left:=Q;
If B2=+1 Then Q^.Bal:=-1 Else Q^.Bal:=0;
If B2=-1 Then Q1^.Bal:=+1 Else Q1^.Bal:=0; Q:=Q2;
Q2^.Bal:=0;
End;
End;
End; Конец процедуры балансировки по L
End;
Procedure BalanceR (Var Q:Ref; Var H:Boolean); При реализации данной процедуры всегда
Var Q1,Q2:Ref; H=True, правая ветвь стала короче
B1,B2: -1..1;
Begin Будем помнить, что H, правая ветвь стала короче
Case Q^.Bal Of
1:Q^.Bal:=0; Дальнейшие действия осуществляем, исходя из значения показателя сбалансированности для данной вершины – поле Bal
0:
Begin
Q^.Bal:=-1;
H:=False;
End;
-1: В этом случае необходима балансировка
Begin
Q1:=Q^.Left;
B1:=Q1^.Bal;
If B1<=0 Then
Begin Однократный LL-поворот Q^.Left:=Q1^.Right;
Q1^.Right:=Q;
If B1=0 Then
Begin
Q^.Bal:=-1;
Q1^.Bal:=1;
H:=False;
End
Else
Begin
Q^.Bal:=0;
Q1^.Bal:=0;
End;
Q:=Q1;
End
Else Двукратный LR-поворот
Begin
Q2:=Q1^.Right;
B2:=Q2^.Bal;
Q1^.Right:=Q2^.Left;
Q2^.Left:=Q1;
Q^.Left:=Q2^.Right;
Q2^.Right:=Q;
If B2=-1 Then Q^.Bal:=+1 Else Q^.Bal:=0;
If B2=+1 Then Q1^.Bal:=-1 Else Q1^.Bal:=0;
Q:=Q2;
Q2^.Bal:=0;
End
End
End
End; Конец балансировки по R– процедуры balanceR
Procedure Del(Var R:Ref;Var H:Boolean); Это, что называется, «чистая» процедура «физического» удаления.
Будем помнить, что при вызове процедуры восстанавливается значение H=False, и в этом режиме происходит удаление вершины
Begin
If R^.Right<>Nil Then
Begin
Del(R^.Right,H);
If H Then BalanceR(R,H)
End
Else
Begin
P^.Key:=R^.Key;
P^.Count:=R^.Count;
R:=R^.Left;
H:=True;
End
End; Конец подпроцедуры удаления – процедуры Del
Begin
If Q=Nil Then Ключа в дереве нет
Begin
WriteLn ( 'Дерево пусто');
H:=False;
End
Else
If X<q^.key then="" В="" зависимости="" от="" соотношений="" значений="" вершин,="" входим="" рекурсивно="" в="" левое="" или="" правое="" поддерево="" вершины,="" с="" целью="" найти="" удаляемый="" элемент.="" Рекурсивная="" процедура="" будет="" считать="" эту="" вершину="" корнем="" дерева.<br="">Begin
Delete(X,Q^.Left,H);
If H Then BalanceL (Q,H);
End
Else
If X>Q^.Key Then
Begin
Delete(X, Q^.Right, H);
If H Then BalanceR(Q,H)
End
Else
Begin Удаление Q^
P:=Q;
If P^.Right=Nil Then
Begin
Q:=P^.Left;
H:=True;
End
Else
If P^.Left=Nil Then
Begin
Q:=P^.Right;
H:=True;
End
Else
Begin
Del(P^.Left,H);
If H Then BalanceL(Q,H);
End;
End
End; Конец большой процедуры удаления
Основная программа.
В комментариях не нуждается.
Begin
Repeat
ClrScr;
GotoXY(4,7);
WriteLn('Меню');
WriteLn;
WriteLn('1. Добавить элемент в дерево');
WriteLn('2. Вывести дерево на экран');
WriteLn('3. Удаление узла');
WriteLn('4. Выход');
GotoXY(1,17);
WriteLn('Нажмите нужную цифру');
Ch:=ReadKey;
Case Ch Of
'1':
Begin
СlrScr;
WriteLn('Вводите цифры, по окончании нажмите 0');
Repeat
ReadLn(C);
if c <> 0 then Search(C,Q,H);
Until C=0;
X:=255;
Level:=1;
End;
'2' :
Begin
ClrScr;
WriteTreel(Q);
ReadLn;
End;
'3' :
Begin
ClrScr;
C:=100;
WriteLn('Вводите удаляемые узлы, по окончанию нажмите 0: ') ;
While C<>0 Do
Begin
WriteLn('Введите удаляемый узел');
ReadLn(C);
if c <>0 then Delete(C,Q,H);
End;
X:=35;
Level:=12;
End;
End;
Until(Ch='4');
End.