Сбалансированные деревья
ОПРЕДЕЛЕНИЯ.
Одной из наиболее часто встречающихся задач является поиск необходимых данных. Существуют различные методы, отличающиеся друг от друга временем поиска, сложностью алгоритмов, размерами требуемой памяти. Обычно стремятся всячески сократить время, затрачиваемое на поиск необходимого элемента. Одним из самых быстрых методов является поиск по упорядоченному бинарному дереву. При удачной структуре дерева время поиска элементов не превышает в среднем log N. Но при неудачной структуре время поиска может значительно возрасти, достигая N\2. ( N - число элементов дерева).
Одним из методов, улучшающих время поиска в бинарном дереве является создание сбалансированных деревьев обладающих минимальным временем поиска.
Одно из определений сбалансированности было дано Адельсоном-Вельским и Ландисом:
Дерево является СБАЛАНСИРОВАННЫМ тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.
Поэтому деревья, удовлетворяющие этому условию, часто называют "АВЛ-деревьями" (по фамилиям их изобретателей).
Операции выполняемые над сбалансированным деревом: поиск, вставка, удаление элемента.
Обратимся к задаче поддержания структуры дерева таким образом, чтобы за время, не превышающее (log N), могла быть выполнена каждая из следующих операций:
- 1) вставить новый элемент;
- 2) удалить заданный элемент;
- 3) поиск заданного элемента.
С тем чтобы предупредить появление несбалансированного дерева, вводится для каждого узла (вершины) дерева показатель сбалансированности, который не может принимать одно из трех значений, левое - (L), правое - (R), сбалансированное - (B), в соответствии со следующими определениями:
левое - узел левоперевешивающий, если самый длинный путь по ее левому поддереву на единицу больше самого длинного пути по ее правому поддереву;
сбалансированное - узел называется сбалансированный, если равны наиболее длинные пути по обеим ее поддеревьям;
правое - узел правоперевешивающий, если самый длинный путь по ее правому поддереву на единицу больше самого длинного пути по ее левому поддереву;
В сбалансированном дереве каждый узел должен находится в одном из этих трех состояний. Если в дереве существует узел, для которого это условие несправедливо, такое дерево называется несбалансированным.
ОПЕРАЦИЯ ВСТАВКИ ВЕРШИНЫ В СБАЛАНСИРОВАННОЕ ДЕРЕВО.
Предполагается, что новая вершина вставляется на уровне листьев, или терминальных вершин (как левое или правое поддерево). При такой вставке показатели сбалансированности могут изменится только у тех вершин, которые лежат на пути между корнем дерева и вновь вставляемым листом.
Алгоритм включения и балансировки полностью определяется способом хранения информации о сбалансированности дерева. Определение типа узла имеет вид:
TYPE ref=^node; { указатель } node=record key:integer; { ключ узла } left,right:ref; { указатели на ветви } bal:-1..+1; { флаг сбалансированности } end;
Процесс включения узла состоит из последовательности таких трех этапов:
- 1. Следовать по пути поиска, (по ключу), пока не будет найден ключ или окажется,что ключа нет в дереве.
- 2. Включить новый узел и определить новый показатель сбалансированности.
- 3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла.
На каждом шаге должна передаваться информация о том, увеличилась ли высота поддерева (в которое произведено включение). Поэтому можно ввести в список параметров переменную h, означающую "высота поддерева увеличилась".
Необходимые операции балансировки полностью заключаются в обмене значениями ссылок. Фактически ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному "повороту" двух или трех узлов.
ПРИНЦИП РАБОТЫ АЛГОРИТМА.
Рассмотрим бинарное дерево представленное на рис. 6.28 (а), которое состоит только из двух узлов. Включение ключа 7 дает вначале несбалансированное дерево (т.е. линейный список). Его балансировка требует однократного правого (RR) поворота, давая в результате идеально сбалансированное дерево (b). Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4.
Это поддерево балансируется однократным левым (LL) поворотом (d). Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5.
Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (LR); результатом является дерево (e). Теперь при следующем включении потерять сбалансированность может лишь узел 5. Действительно, включение узла 6 должно привести к четвертому виду балансировки: двукратному повороту направо и налево (RL). Окончательное дерево показано на рис.6.35 (а-f).
Рис. 6.35 Последовательное включение узлов в сбалансированное дерево.
АЛГОРИТМ Insert_&_Balanse включения узла в сбалансированное дерево.
Дано: сбалансированное бинарное дерево с корнем ROOT.
Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).
Заданы переменные: ключ - х, информация - INF.
Алгоритм вставляет в дерево новый элемент, сохраняя сбалансированность дерева. Если элемент уже присутствует в дереве, то выводится соответствующее сообщение.
Переменная h используется как флаг, указывающий на то, что было произведено включение элемента. P - текущий указатель при перемещении по дереву, p1 и p2 - вспомогательные указатели. Count - счетчик вставленных элементов.
_Начало . Insert_&_Balanse: 1. Поиск места для вставки: _Если . x < KEY(p) _то .: _если . p=nil _то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 3; _иначе .: p=LPTR(p) и перейти к п. 1; повторный вызов Insert_&_Balanse; _Если . x > KEY(p) _то .: _если . p=nil _то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 5; _иначе .: p=RPTR(p) и перейти к п. 1; повторный вызов Insert_&_Balanse; 2. Совпадение: Напечатать "Элемент уже вставлен" и _конец .. 3. Изменение показателей сбалансированности: (производилась вставка в левое поддерево) _если . BAL(p)=1 _то .: BAL(p)=0; h=false; { перевеш.-> сбалансир.} перейти к п. 7 _если . BAL(p)=0 _то . BAL(p)=-1; { перевеш.-> критическ.} перейти к п. 7 4. Балансировка при возрастании левого поддерева: _если .
p=ROOT _то . ROOT=LPTR(p); { перенос корневой вершины } p1=LPTR(); { вводим дополнительный указатель } _если . BAL(p1)=-1 _то .: { однокр. LL-поворот } LPTR(p)=RPTR(p1); RPTR(p1)=p; BAL(p)=0; p=p1; перейти к п. 7 _иначе .: { двукратн. LR-поворот } _если . p1=ROOT _то . ROOT=RPTR(p1); { перенос корневой вершины } p2:=RPTR(p1); RPTR(p1)=LPTR(p2); LPTR(p1)=p1; LPTR(p)=RPTR(p2); RPTR(p2)=p; (изменение показателей сбалансированности ) _если . BAL(p2)=-1 _то . BAL(p)=1 _иначе . BAL(p)=0; _если . BAL(p2)=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0; p=p2; BAL(p)=0; h=false; перейти к п. 7; 5. Изменение показателей сбалансированности: (производилась вставка в правое поддерево) _если . BAL(p)=-1 _то .: BAL(p)=0; h=false; { перевеш.-> сбалансир.} перейти к п. 7 _если . BAL(p)=0 _то BAL(p)=1; { перевеш.-> критическ.} перейти к п. 7 6. Балансировка при возрастании правого поддерева: _если . p=ROOT _то . ROOT=RPTR(p); { перенос корневой вершины } p1=RPTR(p); { вводим дополнительный указатель } _если . BAL(p1)=1 _то .: { однокр. RR-поворот } RPTR(p)=LPTR(p1); LPTR(p1)=p; BAL(p)=0; p=p1; перейти к п. 7 _иначе .: { двукратн. LR-поворот } _если . p1=ROOT _то . ROOT=LPTR(p1); { перенос корневой вершины } p2:=LPTR(p1); LPTR(p1)=RPTR(p2); RPTR(p1)=p1; RPTR(p)=LPTR(p2); LPTR(p2)=p; (изменение показателей сбалансированности ) _если . BAL(p2)=1 _то . BAL(p)=-1 _иначе . BAL(p)=0; _если . BAL(p2)=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0; p=p2; BAL(p)=0; h=false; 7. Выход. (Т.к. процедура осуществляет рекурсивный вызов самой себя в п.3, то здесь производится возврат в место предыдущего вызова. Последний выход осуществляется в вызывающую программу). _Конец . Insert_&_Balanse. 8. Алгоритм процедуры ВСТАВИТЬ_ЭЛЕМЕНТ: _Начало .: LPTR(p)=nil; RPT(p)=nil; BAL=0; { обнуление указателей } DATA=INF; KEY=x; { занесение информации } h=true; { установка флага вставки элемента } _если . count=0 { это первый элемент ? } _то . ROOT=p; count=count+1; _Конец ..
Описание работы:
Производится последовательный рекурсивный вызов процедурой самой себя. При нахождении места для вставки к дереву добавляется новый элемент с помощью процедуры ВСТАВИТЬ_ЭЛЕМЕНТ.
ТЕКСТ ПРОЦЕДУРЫ Insert_&_Balanse.
Процедура выполняет действия по вставка элемента в бинарное дерево с последующей балансировкой в соответствии с приведенным выше алгоритмом.
{=====Программный пример 6.18=========} Procedure Insert_&_Balanse (x:integer; var p,root:ref; var h:boolean); { x=KEY, p=p, root=ROOT, h=h } var p1,p2:ref; {h=false} Begin if p=nil then Create(x,p,h) {слова нет в дереве,включить его} else if x=p^.key then begin gotoXY(35,3); write('Ключ найден!'); readln; exit; end; if x < p^.key then begin Insert_&_Balanse(x,p^.left,root,h); if h then {выросла левая ветвь} case p^.bal of 1: begin p^.bal:=0; h:=false; end; 0: p^.bal:=-1; -1: begin {балансировка} if p=root then root:=p^.left; p1:=p^.left; {смена указателя на вершину} if p1^.bal=-1 then begin {однократный LL-поворот} p^.left:=p1^.right; p1^.right:=p; p^.bal:=0; p:=p1; end else begin {2-кратный LR-поворот} if p1=root then root:=p1^.right; p2:=p1^.right; p1^.right:=p2^.left; p2^.left:=p1; p^.left:=p2^.right; p2^.right:=p; if p2^.bal=-1 then p^.bal:=+1 else p^.bal:=0; if p2^.bal=+1 then p1^.bal:=-1 else p1^.bal:=0; p:=p2; end; p^.bal:=0; h:=false; end; end;{case} end { h then} else if x > p^.key then begin Insert_&_Balanse(x,p^.right,root,h); if h then {выросла правая ветвь} case p^.bal of -1: begin p^.bal:=0; h:=false; end; 0: p^.bal:=+1; 1: begin {балансировка} if p=root then root:=p^.right; p1:=p^.right; {смена указателя на вершину} if p1^.BAL=+1 then begin {однократный RR-поворот} p^.right:=p1^.left; p1^.left:=p; p^.BAL:=0; p:=p1; end else begin {2-кратный RL-поворот} if p1=root then root:=p1^.left; p2:=p1^.left; p1^.left:=p2^.right; p2^.right:=p1; p^.right:=p2^.left; p2^.left:=p; if p2^.BAL=+1 then p^.BAL:=-1 else p^.BAL:=0; if p2^.BAL=-1 then p1^.BAL:=+1 else p1^.BAL:=0; p:=p2; end; p^.BAL:=0; h:=false; end; { begin 3 } end;{ case } end; {then } End {Search};
ТЕКСТ ПРОЦЕДУРЫ ДОБАВЛЕНИЯ ЭЛЕМЕНТА.
Процедура создает новый элемент, заполняет его информационные поля и обнуляет указатели. При создании первого элемента он автоматически становится корнем дерева.
Procedure Create (x:integer; var p:ref; var h:boolean); { создание нового элемента } Begin NEW(p); h:=true; with p^ do begin key:=x; left:=nil; right:=nil; BAL:=0; end; if count=0 then root:=p; count:=count+1; End;
ОПЕРАЦИЯ УДАЛЕНИЯ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА.
Удаление элемента из сбалансированного дерева является еще более сложной операцией чем включение, так как может удаляться не только какой-либо из листьев, но и любой узел (в том числе и корень). Поэтому при удалении необходимо правильно изменить структуру связей между элементами, а затем произвести балансировку полученного дерева.
В результате удаления какого-либо узла могут возникнуть ситуации аналогичные тем, что возникают при добавлении элемента:
- 1. Вершина была лево- или правоперевешивающей, а теперь стала сбалансированной.
- 2. Вершина была сбалансированной, а стала лево- или правоперевешивающей.
- 3. Вершина была перевешивающей, а вставка новой вершины в перевешивающее поддерево создала несбалансированное поддерево - привело к появлению критической вершины. Необходимо провести балансировку.
В общем процесс удаления элемента состоит из следующих этапов:
- 1. Следовать по дереву, пока не будет найден удаляемый элемент.
- 2. Удалить найденный элемент, не разрушив структуры связей между элементами.
- 3. Произвести балансировку полученного дерева и откорректировать показатели сбалансированности.
На каждом шаге должна передаваться информация о том, уменьшилась ли высота поддерева (из которого произведено удаление). Поэтому мы введем в список параметров переменную h, означающую "высота поддерева уменьшилась".
Простыми случаями являются удаление терминальных узлов и узлов с одним потомком. Если же узел, который надо удалить имеет два поддерева, мы будем заменять его самым правым узлом левого поддерева.
Для балансировки дерева после удаления используем две (симметричные) операции балансировки: Balance_R используется, когда уменьшается высота правого поддерева, а Balance_L - левого поддерева.
Процедуры балансировки используют те же способы (LL- LR- RL- и RR-повороты), что и в процедуре вставки элемента.
ПРИМЕР УДАЛЕНИЯ РАЗЛИЧНЫХ УЗЛОВ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА.
Узел, который необходимо удалить, обозначен двойной рамкой. Если задано сбалансированное дерево (рис.6.35. a), то последовательное удаление узлов с ключами 4,8,6,5,2,1 и 7 дает деревья (рис.6.35 b...h).
Удаление ключа 4 само по себе просто, т.к. он представляет собой терминальный узел. Однако при этом появляется несбалансированность в узле 3. Его балансировка требует однократного левого поворота налево. Балансировка вновь становится необходимой после удаления узла 6. На этот раз правое поддерево корня балансируется однократным поворотом направо.
Удаление узла 2, хотя само по себе просто, так как он имеет только одного потомка, вызывает сложный двукратный поворот направо и налево.
И четвертый случай: двукратный поворот налево и направо вызывается удалением узла 7, который прежде заменяется самым правым элементом левого поддерева, т.е. узлом с ключом 3.
Рис.6.36 а..h Удаление узлов из сбалансированого дерева.
Удаление элемента из сбалансированного дерева удобнее разбить на 4 отдельных процедуры:
- 1. Delete - осуществляет рекурсивный поиск по дереву удаляемого элемента, вызывает процедуры удаления и балансировки.
- 2. Del - осуществляет собственно удаление элемента и вызов при необходимости процедуры балансировки.
- 3. Balance_L и Balance_R - производят балансировку и коррекцию показателей сбалансированности после удаления элемента из левого (правого) поддерева.
АЛГОРИТМ ПРОЦЕДУРЫ Delete.
Дано: сбалансированное бинарное дерево с корнем ROOT. Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).
Задан: ключ - х, информация - INF.
Алгоритм находит удаляемый элемент и вызывает процедуры удаления и последующей балансировки бинарного дерева. Если элемент отсутствует в дереве, выдается соответствующее сообщение.
Переменная h используется как флаг, указывающий на то, что было произведено удаление элемента.
P - текущий указатель при перемещении по дереву, q - вспомогательный указатель.
_Начало . Delete 1. Поиск удаляемого элемента _Если . x < KEY(p) _то .: p=LPTR(p); Вызов Delete; _если . h=true _то . Вызов Balance_L; перейти к п.5 _Если . x > KEY(p) _то .: p=RPTR(p); Вызов Delete; _если . h=true _то . вызов Balance_R; перейти к п.5 _Если . p=nil _то .: напечатать "Ключа в дереве нет!"; _конец .; 2. Удаление элемента : (если все предыдущие условия не выполнены, то указатель указывает на элемент, подлежащий удалению). Удаляется элемент с одним поддеревом. q=p; { вводим вспомогательный указатель } _если . RPTR(q)=nil _то .: p=LPTR(q); h=true; перейти к п.4; _если . LPTR(q)=nil _то .: p=RPTR(q); h=true; перейти к п.4; 3. Удаление элемента с двумя поддеревьями: q=LPTR(q); _если . h=true _то .: вызов Balance_L; перейти к п.4 4. Напечатать "Узел удален из дерева". 5. Выход. _Конец . Delete;
ОПИСАНИЕ РАБОТЫ АЛГОРИТМА:
АЛГОРИТМ ПРОЦЕДУРЫ Del.
Дано: указатель - r на элемент дерева с двумя поддеревьями.
Алгоритм производит удаление этого элемента, с сохранением связей с нижележащими элементами, и вызов процедуры балансировки.
Используется вспомогательный указатель q, описанный в процедуре Delete.
_Начало . Del. 1. Поиск последнего элемента в правом поддереве _Если . RPTR(r) <> nil { элемент не найден } _то .: r=RPTR(r); вызов процедуры Del; _если .
h=true _то . вызов процедуры Balance_R; перейти к п.2; _иначе .: KEY(q)=KEY(r); r=RPTR(r); h=true; 2. Выход. _Конец . Del;
ОПИСАНИЕ РАБОТЫ:
АЛГОРИТМ ПРОЦЕДУРЫ Balance_L.
Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента.
Задан: указатель p на место удаленного элемента.
Алгоритм производит балансировку бинарного дерева и корректировку показателей сбалансированности.
P1 и P2 - вспомогательные указатели, b1 и b2 - вспомогательные показатели сбалансированности.
_Начало . Balance_L: 1. Корректировка показателей сбалансированности: _Если . BAL(p)=-1 _то .: BAL(p)=0; { перевеш. -> сбалансир. } _конец _Если . BAL(p)=0 _то .: BAL(p)=1; h=false; { сбалансир. -> перевеш. } _конец p1=RPTR(p); b1=BAL(p1); { BAL(p)=1 - критическая. } 2. Однократный RR-поворот : _Если . b1 >= 0 _то .: _Если . p=ROOT _то . ROOT=RPTR(p); _ .{ перенос корня } RPTR(p)=LPTR(p1); LPTR(P1)=p; { корректировка показателей сбалансированности } _если . b1=0 _то .: BAL(p)=1; BAL(p1)=-1; h=false; _иначе .: BAL(p)=0; BAL(p1)=0; p=p1; _конец 2. Двукратный RL-поворот : _если . b1 < 0 _если . p1=ROOT _то . ROOT=RPTR(p); { перенос корня } p2=LPTR(p1); b2=BAL(p2); LPTR(p1)=RPTR(p2); RPTR(p2)=p1; RPTR(p)=LPTR(p2); LPTR(p2)=p; { корректировка показателей сбалансированности } _если . b2=1 _то . BAL(p)=-1 _иначе . BAL(p)=0; _если . b2=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0; p=p2; BAL(p2)=0; _конец _Конец . Balance_L;
ОПИСАНИЕ РАБОТЫ АЛГОРИТМА:
АЛГОРИТМ ПРОЦЕДУРЫ Balance_R.
Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента.
Алгоритм, входные данные и вспомогательные переменные аналогичны алгоритму Balance_L, изменены на противоположные только условия выбора и направления указателей.
_Начало . Balance_R: 1. Корректировка показателей сбалансированности: _Если . BAL(p)=1 _то .: BAL(p)=0; { перевеш. -> сбалансированная. } _конец _Если . BAL(p)=0 _то .: BAL(p)=-1; h=false; { сбалансир. -> перевешивающая. } _конец p1=LPTR(p); b1=BAL(p1); { BAL(p)=1 - критическая. } 2. Однократный LL-поворот : _если . b1 0 _если . p1=ROOT _то . ROOT=LPTR(p); { перенос корня } p2=RPTR(p1); b2=BAL(p2); RPTR(p1)=LPTR(p2); LPTR(p2)=p1; LPTR(p)=RPTR(p2); RPTR(p2)=p; { корректировка показателей сбалансированности } _если . b2=-1 _то . BAL(p)=1 _иначе . BAL(p)=0; _если . b2=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0; p=p2; BAL(p2)=0; _конец _Конец . Balance_R;
Метод работы аналогичен алгоритму Balance_L.
ТЕКСТЫ ПРОЦЕДУР Delete 1, 0 Del 1, 0Balance_L и Balance_R.
Так как процедуры Del, Balance_L и Balance_R используются только процедурой Delete, то их можно выполнить вложенными в Delete.
{=====Программный пример 6.20 ========} Procedure Delete (x:integer; var p,root:ref; var h:boolean); var q:ref; {h:false} procedure Balance_L ( var p:ref; var h:boolean); {уменьшается высота левого поддерева} var p1,p2:ref; b1,b2:-1..+1; begin { h-true, левая ветвь стала короче } case p^.BAL of -1: p^.BAL:=0; 0: begin p^.BAL:=+1; h:=false; end; 1: begin {балансировка} p1:=p^.right; b1:=p1^.BAL; if b1 >= 0 then begin { однократный RR-поворот } if p=root then root:=p^.right; p^.right:=p1^.left; p1^.left:=p; if b1 = 0 then begin p^.BAL:=+1; p1^.BAL:=-1; h:=false; end else begin p^.BAL:=0; p1^.BAL:=0; end; p:=p1; end else begin { 2-кратный RL-поворот } if p1=root then root:=p1^.right; p2:=p1^.left; b2:=p2^.BAL; p1^.left:=p2^.right; p2^.right:=p1; p^.right:=p2^.left; p2^.left:=p; if b2=+1 then p^.BAL:=-1 else p^.BAL:=0; if b2=-1 then p1^.BAL:=+1 else p1^.BAL:=0; p:=p2; p2^.BAL:=0; end; end; { begin 3 } end; { case } end; {Balance_L} procedure Balance_R (var p:ref; var h:boolean); { уменьшается высота правого поддерева } var p1,p2:ref; b1,b2:-1..+1; begin { h-true, правая ветвь стала короче } case p^.BAL of 1: p^.BAL:=0; 0: begin p^.BAL:=-1; h:=false; end; -1: begin { балансировка } p1:=p^.left; b1:=p1^.BAL; if b1 nil then begin Del(r^.right,h); if h then Balance_R(r,h); end else begin q^.key:=r^.key; r:=r^.left; _ .h:=true; end; end;{Del} Begin {Delete} if p=nil then begin TextColor(white); GotoXY(а,b+2); write ('Ключа в дереве нет'); h:=false; end else if x < p^.key then begin Delete(x,p^.left,root,h); if h then Balance_L(p,h); end else if x > p^.key then begin Delete(x,p^.right,root,h); if h then Balance_R(p,h); end else begin { удаление p^ } q:=p; if q^.right=nil then begin p:=q^.left; h:=true; end else if q^.left=nil then begin p:=q^.right; h:=true; end else begin Del(q^.left,h); if h then Balance_L(p,h); end; GotoXY(а,b); writeln(' Узел с ключом ',x,' удален из дерева.'); end; End{Delete};
ПОИСК ЭЛЕМЕНТА.
Поиск элемента в сбалансированном дереве уже применялся в операциях вставки и удаления элементов. Поэтому необходимо отдельно рассмотреть эту операцию.
Пусть дано некоторое бинарное дерево, в котором каждый левый элемент меньше вышележащего, а правый - больше.
Для нахождения элемента с заданным ключом начинаем поиск с корневого элемента, сравнивая его ключ с искомым. Если искомый ключ меньше, то продолжаем поиск по левому поддереву (так как его элемент меньше текущего), а если ключ больше - то по правому (его элемент больше). Сравнивая аналогичным образом искомый ключ с ключом текущего элемента мы будем последовательно спускаться по дереву до тех пор, пока ключи искомого и текущего элемента не совпадут - элемент найден. Если мы дошли до уровня листьев (ниже элементов уже нет), а элемент не найден, значит он отсутствует в дереве.
Этот алгоритм пригоден для поиска в любых бинарных деревьях, но при работе со сбалансированными деревьями время поиска элемента минимально.
АЛГОРИТМ Search.
Дано: ключ - X.
Алгоритм производит рекурсивный обход сбалансированного дерева и находит элемент с заданным ключом, либо сообщает об отсутствии такого элемента.
1. Поиск элемента: _Если . x < key(p) _то .: _если . p=nil _то .: напечатать "Элемент отсутствует" и _конец .. _иначе .: p=LPTR(p) и вызвать процедуру Search; _Если . x > key(p) _то .: _если . p=nil _то .: напечатать "Элемент отсутствует" и _конец .. _иначе .: p=RPTR(p) и вызвать процедуру Search; 2. Совпадение: Напечатать "Элемент найден"; Произвести операции обработки элемента и _конец ..
ТЕКСТ ПРОЦЕДУРЫ Search.
{=====Программный пример 6.21 ===========} Procedure Search (x:integer; var p:ref); begin if x > p^.key then if p=nil then writeln('Элемент на найден') else Search(x,p^.right); if x < p^.key then if p=nil then writeln('Элемент на найден') else Search(x,p^.left); writeln('элемент найден'); { Здесь - процедура обработки элемента } end;
Так как операция поиска применяется в процедуре вставки элемента в сбалансированное дерево, то нет особого смысла выделять эту операцию в отдельную процедуру.
Проще предусмотреть, что при отсутствии элемента производится его включение, а если элемент уже есть - то производятся необходимые действия над элементом.
На первый взгляд работа со сбалансированными бинарными деревьями требует лишних затрат времени на дополнительные операции по поддержанию необходимой структуры дерева и усложнение алгоритмов.
Но на самом деле затраты на балансировку легко компенсируются минимальным временем поиска элементов при вставке, удалении и обработке элементов, по сравнению с другими методами хранения. В то же время четкая структура расположения элементов не усложняет, а наоборот - упрощает алгоритмы работы с такими деревьями.
ОПИСАНИЕ ПРОГРАММЫ РАБОТЫ СО СБАЛАНСИРОВАННЫМИ ДЕРЕВЬЯМИ.
1. Процедура NOTE.
В процессе работы пользователя с программой MAVERIC выводит подсказку в нижней части экрана. Подсказка содержит коды клавиш,определяющих режим работы программы.
2. Процедура CREATE.
Создает новый узел дерева,в том числе и корень; записывает ключ дерева и обнуляет указатели узла на его ветви. Включает счетчик узлов и определяет корень дерева,путем установки на него указателя ROOT. Указатель ROOT устанавливается только в случае,если счетчик узлов дерева равен 0.
3. Процедура SEARCH.
Входным элементом для процедуры SEARCH является определяемый пользователем ключ для поиска или создания нового узла. Новый ключ сравнивается с ключом предыдущего узла.Если узла с таким ключом нет в дереве,то вызывается процедура CREATE.
В зависимости от того, больше или меньше ключ нового узла ключа узла предыдущего выбирается вид включения нового узла в дерево - справа или слева. На каждом этапе работы процедуры проверяется флаг "h" определяющий,увеличилась ли высота поддерева; а также проверяется поле "p^.bal" определяющее способ балансировки.
Процедура SEARCH является рекурсивной процедурой,т.е. она вызывает сама себя.При первом проходе процедура SEARCH обращается к корню дерева,затем проходит по всему дереву,последовательно вызывая ветви корня,затем ветви ветвей и так далее.
В случае,если необходима балансировка, процедура SEARCH производит так называемые "повороты" ветвей дерева,путем переопределения указателей.Если балансировка затрагивает корень дерева, процедура переопределяет корень,меняя указатель ROOT,а затем производит балансировку.
4. Процедура DELETE.
Процедура DELETE удаляет ключ из дерева и,если необходимо,производит балансировку.Входным параметром является определяемый пользователем ключ. Процедура DELETE имеет три одпроцедуры: balance_R,balance_L и Del.Подпроцедуры balance_R и balance_L являются симметричными и выполняют балансировку при уменьшении высоты правого или левого поддеревьев соответственно.
Если узла с заданным пользователем ключом нет в дереве,то выводится соответствующее сообщение.Если данный ключ меньше ключа предыдущего узла,то происходит рекурсивный вызов процедуры Delete и обход дерева по левой ветви.Если возникает необходимость балансировки,то вызывается подпроцедура balance_L.Если заданный пользователем ключ больше ключа предыдущего узла,то производится обход дерева по правой ветви и в случае необходимости балансировки вызывается подпроцедура balance_R.
Если подпроцедуры балансировки затрагивают корень дерева,то меняется указатель на корень дерева - ROOT.Эта операция заложена в обоих подпроцедурах balance_R и balance_L.
При обнаружении узла с заданным пользователем ключом подпроцедура Del производит операцию удаления данного узла.
5. Процедура OUTTREE.
Рекурсивная процедура OutTree выводит изображение дерева на монитор. Входными параметрами является указатель на корень дерева ROOT и переменная F определяющая,является ли текущий узел корнем или правой или левой ветвью.
После каждой операции над деревом процедура OutTree выводит изображение дерева заново,предварительно очистив экран.
6. Основная программа.
Программа Maveric работает в текстовом режиме,для чего в начале инициализируется модуль CRT. Основная программа выводит заставку и ожидает нажатия одной из определенных в программе клавиш.
При помощи процедуры Note внизу экрана выводится подсказка со списком определенных клавиш и соответствующих им операций.При нажатии клавиши B вызывается процедура Create,при нажатии клавиши S вызывается процедура Search,при нажатии D - процедура Delete.Программа работает в диалоговом режиме.
Режим работы с пользователем прекращается при нажатии клавиши ESC.
{======Программный пример 6.22 ====== } {$T-} Program Maveric; USES CRT; label L1,L2,L3,L4; TYPE ref=^node; { указатель на узел } node=record key:integer; { ключ узла } left,right:ref; { указатели на ветви } bal:-1..+1; { флаг сбалансированности } end; VAR root, { указатель на корень дерева } p:ref; { новое дерево } x:integer; { ключ узла } h:boolean; { true-высота поддерева увеличилась } n:char; { клавиша подсказки } Ta,Tb, { координаты начала вывода дерева } a,b:integer; { координаты вывода подсказки } count:byte; { счетчик узлов дерева } Procedure Note; { процедура вывода подсказки } Begin TextBackground (white); GotoXY(5,25); textcolor(black); write('B-новое дерево S-поиск по ключу '); write (' D-удаление по ключу Esc-выход'); End; Procedure Create (x:integer; var p:ref; var h:boolean); { создание нового дерева } Begin NEW(p); h:=true; with p^ do begin key:=x; left:=nil; right:=nil; bal:=0; end; if count=0 then root:=p; count:=count+1; End; Procedure Search(x:integer; var p,root:ref; var h:boolean); var p1,p2:ref; {h=false} Begin if p=nil then Create(x,p,h) {слова нет в дереве,включить его} else if x < p^.key then begin Search(x,p^.left,root,h); if h then {выросла левая ветвь} case p^.bal of 1: begin p^.bal:=0; h:=false; end; 0: p^.bal:=-1; -1: begin {балансировка} if p=root then root:=p^.left; {смена указателя на вершину} p1:=p^.left; if p1^.bal=-1 then begin {однократный LL-поворот} p^.left:=p1^.right; p1^.right:=p; p^.bal:=0; p:=p1; end else begin {2-х кратный LR-поворот} if p1=root then root:=p1^.right; p2:=p1^.right; p1^.right:=p2^.left; p2^.left:=p1; p^.left:=p2^.right; p2^.right:=p; if p2^.bal=-1 then p^.bal:=+1 else p^.bal:=0; if p2^.bal=+1 then p1^.bal:=-1 else p1^.bal:=0; p:=p2; end; p^.bal:=0; h:=false; end; end; end else if x > p^.key then begin Search(x,p^.right,root,h); if h then {выросла правая ветвь} case p^.bal of -1: begin p^.bal:=0; h:=false; end; 0: p^.bal:=+1; 1: begin {балансировка} if p=root then root:=p^.right; {смена указателя на вершину} p1:=p^.right; if p1^.bal=+1 then begin {однократный RR-поворот} p^.right:=p1^.left; p1^.left:=p; p^.bal:=0; p:=p1; end else begin {2-х кратный RL-поворот} if p1=root then root:=p1^.left; p2:=p1^.left; p1^.left:=p2^.right; p2^.right:=p1; p^.right:=p2^.left; p2^.left:=p; if p2^.bal=+1 then p^.bal:=-1 else p^.bal:=0; if p2^.bal=-1 then p1^.bal:=+1 else p1^.bal:=0; p:=p2; end; p^.bal:=0; h:=false; end; end; end; End {Search}; Procedure Delete (x:integer; var p,root:ref; var h:boolean); var q:ref; {h:false} procedure balance_L ( var p:ref; var h:boolean); {уменьшается высота левого поддерева} var p1,p2:ref; b1,b2:-1..+1; begin {h-true,левая ветвь стала короче} case p^.bal of -1: p^.bal:=0; 0: begin p^.bal:=+1; h:=false; end; 1: begin {балансировка} p1:=p^.right; b1:=p1^.bal; if b1 >= 0 then begin {однократный RR-поворот} if p=root then root:=p^.left; p^.right:=p1^.left; p1^.left:=p; if b1 = 0 then begin p^.bal:=+1; p1^.bal:=-1; h:=false; end else begin p^.bal:=0; p1^.bal:=0; end; p:=p1; end else begin {2-х кратный RL-поворот} if p1=root then root:=p1^.left; p2:=p1^.left; b2:=p2^.bal; p1^.left:=p2^.right; p2^.right:=p1; p^.right:=p2^.left; p2^.left:=p; if b2=+1 then p^.bal:=-1 else p^.bal:=0; if b2=-1 then p1^.bal:=+1 else p1^.bal:=0; p:=p2; p2^.bal:=0; end; end; end; end; {balance_L} procedure balance_R (var p:ref; var h:boolean); {уменьшается высота правого поддерева} var p1,p2:ref; b1,b2:-1..+1; begin {h-true,правая ветвь стала короче} case p^.bal of 1: p^.bal:=0; 0: begin p^.bal:=-1; h:=false; end; -1: begin {балансировка} p1:=p^.left; b1:=p1^.bal; if b1 nil then begin Del(r^.right,h); if h then balance_R(r,h); end else begin q^.key:=r^.key; r:=r^.left; h:=true; end; end;{Del} Begin {Delete} if p=nil then begin TextColor(white); GotoXY(a,b+2); write ('Ключа в дереве нет'); h:=false; end else if x < p^.key then begin Delete(x,p^.left,root,h); if h then balance_L(p,h); end else if x > p^.key then begin Delete(x,p^.right,root,h); if h then balance_R(p,h); end else begin {удаление p^} q:=p; if q^.right=nil then begin p:=q^.left; h:=true; end else if q^.left=nil then begin p:=q^.right; h:=true; end else begin Del(q^.left,h); if h then balance_L(p,h); end; {dispose(q);} GotoXY(a,b); writeln('Узел с ключом ',x,' удален из дерева.'); end; End{Delete}; Procedure OutTree(pr:ref;f:byte); Begin Tb:=Tb+2; If f=1 then Ta:=Ta-2; if f=2 then Ta:=Ta+8; if pr<>nil then begin GotoXY(TA,TB); case f of 0: Writeln('[',pr^.key,']'); 1: Writeln('[',pr^.key,']/'); 2: Writeln('\[',pr^.key,']'); end; OutTree(pr^.left,1); OutTree(pr^.right,2); end; Tb:=Tb-2; Ta:=Ta-2; End; {OutTree} BEGIN {main program} L4: count:=0; a:=25; b:=5; TextBackground(black); ClrScr; TextBackground (red); gotoxy(a,b); textcolor(white); writeln(' WELCOME TO THE LAND '); gotoxy(a,b+1); WRITE(' OF BALANCED TREES '); while n <> #27 do begin note; n:=readkey; case n of #66: goto L1; {'B'} #68: goto L3; {'D'} #83: goto L2; {'S'} #98: begin {'b'} L1: clrscr; TextBackground (green); gotoxy(a,b); writeln ('Введите ключ для нового дерева'); gotoxy(a+32,b); read(x); Create(x,p,h); end; #115: begin {'s'} L2: ClrScr; TextBackground (blue); gotoxy(a,b); TextColor(white); writeln('Введите ключ для поиска и включения'); gotoxy(a+40,b); read(x); Search(x,p,root,h); Ta:=26; Tb:=10; OutTree(root,0); end; #100: begin {'d'} L3: ClrScr; TextBackground (yellow); gotoxy(a,b); TextColor(black); writeln('Введите ключ для удаления узла'); gotoxy(a+32,b); read(x); Delete(x,p,root,h); Ta:=26; Tb:=10; OutTree(root,0); end; end; end; Dispose(p); ClrScr; TextBackground (red); GotoXY(a,b); TextColor(white); writeln('Are you sure? Yes/No'); GotoXY (a+23,b); n:=readkey; if (n=#78) or (n=#110) then goto L4; END. {main program}
| Каталог | Индекс раздела |
| Назад | Оглавление | Вперед |
