Главная Промышленная автоматика.

рева до удаляемого листа. Эту информацию можно получить путем рекурсивного применения алгоритма удаления, вызываемого для каждого узла, составляющего путь, который начинается от корня дерева. Возникающие при этом ситуации учтены при написании программы (см. далее), реализующей оператор DELETE. □

Типы данных для 2-3 деревьев

Ограничимся представлением (посредством 2-3 деревьев) множеств элементов, чьи ключи являются действительными числами. Природа других полей, которые вместе с полем key (ключ) составляют запись об элементе, пока не определена и здесь нас не интересует; общий тип записи обозначим как elementtype.

При написании программ на языке Pascal родители листьев должны быть записями, содержащими два поля действительных чисел (ключи наименьщих элементов во втором и в третьем поддеревьях) и три поля указателей на элементы. Родители этих узлов являются записями, состоящими из двух полей действительных чисел и трех полей указателей на родителей листьев. Таким образом, разные уровни 2-3 дерева имеют разные типы данных (указатели на элементы или указатели на узлы). Эта ситуация вызывает затруднения при программировании на языке Pascal операторов, выполняемых над 2-3 деревьями. К счастью, язык Pascal имеет механизм, вариант структуры record (запись), который позволяет обращаться с узлами 2-3 дерева, имеющими разный тип данных . В листинге 5.8 приведено объявление типов данных для узлов 2-3 дерева, а также для типа данных SET (Множество), представляющего 2-3 дерево, в виде указателя на корень этого дерева.

Листинг 5.8. Объявление типов данных узлов 2-3 дерева type

elementtype = record key: real;

{ объявление других полей, если необходимо }

end;

nodetype = (leaf. Interior);

{ объявление типа узла, содержащее поля leaf (лист) и interior (внутренний узел) } twothreenode = record

case kind: nodetype of

leaf: (element: elementtype) ;

interior:(firstchild, secondchild, thirdchild:

ttwothreenode; lowofsecond, lowofthird: real)

end;

SET = ttwothreenode;

Реализация оператора INSERT

Детали реализации операторов для 2-3 деревьев несколько запутанны, но принципы просты. Поэтому подробно мы опищем только оператор вставки. Реализации операторов удаления, проверки на принадлежность множеству и других подобны реализации оператора INSERT, а оператор нахождения минимального элемента выполняется просто спуском по самому левому пути дерева. Оператор INSERT реализован как основная программа, вызывающая корень дерева и процедуру insertl, которая рекурсивно вызывается для узлов дерева. Для определенности мы предполагаем, что 2-3 дерево не является пустым деревом и содержит более одного узла. Последние

В данном случае все равно каждый узел будет занимать пространство, равное пространству, занимаемому самым "большим" типом данных. Поэтому язык Pascal - не лучший язык для практической реализации 2-3 деревьев.



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

Функция insertl должна возвращать как указатель на новый узел, если он будет создан, так и ключ наименьшего элемента, находящегося ниже нового узла. В языке Pascal механизм создания такой функции достаточно сложен, поэтому мы объявили insert 1 как процедуру, которая присваивает значения параметрам pnew и low при создании нового узла. В листинге 5.9 показан эскиз этой процедуры, а ее полный код приведен в листинге 5.10.

Листинг 5.9. Процедура вставки в 2-3 дерево

procedure insertl ( node: ttwothreenode; x: elementtype;

{ элемент x должен быть вставлен в поддерево с корнем node ] var pnew: ttwothreenode; { указатель на новый элемент } var low; real); { наименьший элемент в поддереве с корнем,

на который указывает pnew ]

begin

pnew:= nil;

if node является листом then begin

if X не является элементом, содержа1цимся в node then begin создание нового узла, указанного pnew; сделать х элементом, содержащимся в новом узле; Jow;= х.кеу

.end

else begin { node является внутренним узлом } выбрать W - сына узла node; insertl(w, X, рЬаск, lowback); if рЬаск о nil then begin

вставка указателя рЬаск среди детей узла node,

расположенных справа от w, if node имеет 4-х сыновей then begin

создание нового узла, указанного pnew;

создание нового узла для 3-го и 4-го сыновей node;

задание значений полям Jowofsecond и lowofthird

для узла node и нового узла; задание поло low наименьшего ключа среди детей нового узла

end; { insertl }

Листинг 5.10. Полный код процедуры insertt

procedure insertl ( node: ttwothreenode; x: elementtype; var pnew: Ttwothreenode; var low: real ); var

pback: ttwothreenode; lowback: real;

child: 1..3; { указывает на следающего "обрабатываемого"

сына node (ср. с w в листинге 5.9) } w: ttwothreenode; { указатель на сына } begin

pnew:- nil;



if nodet.kind = leaf then begin

if nodet. element. key <> x.key then begin

{ создание нового листа, содержащего х и

"возврат" этого листа } newipnew, leaf) ;

i f nodet. el emen t. key < x. key then { запись x в новый узел }

begin pnewt. element: = x; low:= x.key end else begin

pnewt. element: = nodet. element; nodet. eJement:=x/ low:= pnew\.element.key

else beghi { node является внутренним узлом } { выбор следующего сына node } if x.key < nodet. lowof second then

begin child:= 1; w:= nodet. firstchild end else if (nodet. thirdchild = nil) or

(x.Jcey< nodet. lowof second) then begm { X BO втором поддереве } child:= 2;

w:= nodet.secondchild

else begin { x в третьем поддереве } child:= 3;

w: = nodet.thirdchild

end;

insertl(w, x, pback, lowback) ; if pback <> nil then

{ надо вставить нового сына node } if nodet. thirdchild = nil then

{ node имеет только двух сыновей } If child - 2 then begin

nodet.thirdchild:- pback; nodet.lowofthird:= lowback

else begin { child = 1 }

nodet. thirdchild: = nodet .secondchild; nodet.lowofthird: = nodet. lowofsecond; nodet. secondchild: = pback; nodet.lowofsecond:= lowback

end"

else begin { node уже имеет трех сыновей } newipnew, interior);

If child = 3 then begin

[pback к 3-й сын становятся сьшовьями нового узла) pnewt.firstchild:=nodeT. thirdchild; pnewt.secondchild:= pback; pnewt. thirdchild: = nil; pnehft. lowof second: = lowback;

{ lowof third для pnevj неопределен } low:= nodet. lowofthird;





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 [50] 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0018