Структуры данных и алгоритмы (1021739), страница 41
Текст из файла (страница 41)
Родителиэтих узлов являются записями, состоящими из двух полей действительных чисел итрех полей указателей на родителей листьев. Таким образом, разные уровни 2-3 дерева имеют разные типы данных (указатели на элементы или указатели на узлы).Эта ситуация вызывает затруднения при программировании на языке Pascal операторов, выполняемых над 2-3 деревьями. К счастью, язык Pascal имеет механизм, вариант структуры record (запись), который позволяет обращаться с узлами 2-3 дерева,имеющими разный тип данных . В листинге 5.8 приведено объявление типов данныхдля узлов 2-3 дерева, а также для типа данных SET (Множество), представляющего2-3 дерево, в виде указателя на корень этого дерева.Листинг 5.8. Объявление типов данных узлов 2-3 дереваtypeelementtype = recordkey: real;{ объявление других полей, если необходимо }end;nodetype = (leaf, interior);l объявление типа узла, содержащее поля leaf (лист) иinterior (внутренний узел) }twothreenode = recordcase kind: nodetype ofleaf": (element: elementtype) ;interior:(firstchild, secondchild, thirdchild:Ttwothreenode;lowofsecond, lowofthird: real)end;SET = ttwothreenode;Реализация оператора INSERTДетали реализации операторов для 2-3 деревьев несколько запутанны, но принципы просты.
Поэтому подробно мы опишем только оператор вставки. Реализацииоператоров удаления, проверки на принадлежность множеству и других подобныреализации оператора INSERT, а оператор нахождения минимального элемента выполняется просто спуском по самому левому пути дерева. Оператор INSERT реализован как основная программа, вызывающая корень дерева и процедуру insertl, которая рекурсивно вызывается для узлов дерева.
Для определенности мы предполагаем,что 2-3 дерево не является пустым деревом и содержит более одного узла. Последние1В данном случае все равно каждый узел будет занимать пространство, равное пространству, занимаемому самым "большим" типом данных. Поэтому язык Pascal — не лучший языкдля практической реализации 2-3 деревьев.162ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВдва случая, когда дерево пустое или содержит только один узел, реализуются простой последовательностью шагов, которые читатель может написать самостоятельно.Функция insert! должна возвращать как указатель на новый узел, если он будетсоздан, так и ключ наименьшего элемента, находящегося ниже нового узла.
В языкеPascal механизм создания такой функции достаточно сложен, поэтому мы объявилиinsert! как процедуру, которая присваивает значения параметрам pnew и low присоздании нового узла. В листинге 5.9 показан эскиз этой процедуры, а ее полный кодприведен в листинге 5.10.Листинг 5.9. Процедура вставки в 2-3 дерево-':."..'...-..''..'•.'--.•'...'.......-'..---•--.-;.'•....•:'•.••..'•"•--.-••'.'--•'- ' • • ' ' ' . .' • ' - • . •. . - • • : • . ' • • •procedure insertl ( node: Ttwothreenode; x: elementtype;{ элемент х должен быть вставлен в поддерево с корнем node }var pnew: ttwothreenode; { указатель на новый элемент }var low: real); { наименьший элемент в поддереве с корнем,на который указывает pnew }beginpnew:= nil;if node является листом then beginif x не является элементом, содержащимся в node then beginсоздание нового узла, указанного pnew;сделать х элементом, содержащимся в новом узле;low:= x.keyendendelse begin { node является внутренним узлом }выбрать w — сына узла node;insertl(w, x, pback, lowback);if pback <> nil then beginвставка указателя pback среди детей узла node,расположенных справа от w,if node имеет 4-х сыновей then beginсоздание нового узла, указанного pnew;создание нового узла для 3-го и 4-го сыновей node;задание значений полям lowofsecond и lowofthirdдля узла node и нового узла;задание полю low наименьшего ключасреди детей нового узлаendendendend; { insertl }Листинг 5.10.
Полный код процедуры/nserflprocedure insertl ( node: ttwothreenode;x: elementtype;var pnew: Ttwothreenode; var low: real );varpback: ttwothreenode;lowback: real;child: 1..3; { указывает на следующего "обрабатываемого"сына node (ср. с w в листинге 5.9) }w: ttwothreenode; { указатель на сына }beginpnew:= nil;5.4. РЕАЛИЗАЦИЯ МНОЖЕСТВ ПОСРЕДСТВОМ СБАЛАНСИРОВАННЫХ...163if node?.kind = leaf then beginif nodeT.element.key <> x.key then begin{ создание нового листа, содержащего х и"возврат" этого листа }new(pnew, leaf);if nodeT.element.key < x.key then{ запись х в новый узел }begin pnewT.element:= x; low.= x.key endelse beginpnewT.element:= nodeT.
element;node'l. element := x;low:= pnewl.element.keyendendendelse begin { node является внутренним узлом }{ выбор следующего сына node }if x.key < nodet.lowofsecond thenbegin child:= 1; w:= nodet.firstchild endelse if(nodeT.thirdchild = nil) or(x.key < nodet.lowofsecond) then begin{ х во втором поддереве }child:= 2;w:= nodeT.secondchildendelse begin { х в третьем поддереве }child:= 3;w.= nodet.thirdchildend;insertKw, x, pback, lowback) ;if pback <> nil then{ надо вставить нового сына node }if nodet.thirdchild = nil then{ node имеет только двух сыновей }if child - 2 then beginnodeT.thirdchild:= pback;nodeT. lowofthird:= lowbackendelse begin { child = 1 }nodeT.thirdchild:= nodeT .secondchild;nodeT.lowofthird:= nodeT. lowofsecond;nodeT.secondchild:= pback;nodeT.lonrofsecond:= lowback,endelse begin { node уже имеет трех сыновей }new(pnew, interior);if child = 3 then begin{pback и 3-й сын становятся сыновьями нового узла}pnewT.firstchild:= nodeT.
thirdchild;pnewT.secondchild:= pback;pnewl. thirdchild: = nil ,pnet/Г. lowof second: = lowback;{ lowDfthird для pnew неопределен }low:= nodeT.lowofthird;164ГЛАВА 5. СПЕЦИАЛЬНЬШ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВnodeT.thirdchild:= nilendelse begin{child < 2; перемещение 3-го сына node к pnew}pnewt.secondchild:= nodet. thirdchild;pnew\.lowofsecond:=nodet.lowofthird;pnewt.thirdchild:= nil;nodeT.thirdchild:= nilend;if child = 2 then begin(pback становится 1-м сыном pnew }pnewf.firstchild:= pback;low:= lowbackend;if child = 1 then begin{ 2-й сын node перемещается к pnew,pback становится 2-м сыном node }pnewt.firstchild:= nodet.secondchild;low:= nodet - lowofsecond;nodet.secondcnild:= pback;nodet.
lowofsecond: = lowbackendendendend; { inserfcl }Теперь можно написать процедуру INSERT, которая вызывает insert 1. Еслиinsertl "возвращает" новый узел, тогда INSERT должна создать новый корень дерева.Код процедуры INSERT представлен в листинге 5.11. Здесь мы считаем, что типSET — это тип Ttwothreenode, т.е. указатель на корень 2-3 дерева, чьи листья содержат элементы исходного множества.Листинг 5.11. Оператор INSERT для множеств, представленных посредством2-3 деревьевprocedure INSERT ( x: elementtype; var S: SET ) ;varpback: ttwothreenode; {указатель на узел, возвращенный insertl}lowback: real; {наименьшее (low) значение в поддереве pback}saves: SET; { для временного хранения копии указателя S }begin{ здесь надо вставить процедуру проверки, которая выясняет,. является ли S пустым деревом или имеет только один узел,и Осуществляет для этих ситуаций вставку }insertl(S, x, pback, lowback);if pback <> nil then begin{ создание нового корня, на его сыновей указывают S и pback }saveS:= S;new(S);St.firstchild:= saveS;st.secondcni1d:= pback;ST.lowofsecond:= lowback;St.thirdchild:- nil;endend,- { INSERT )5.4.
РЕАЛИЗАЦИЯ МНОЖЕСТВ ПОСРЕДСТВОМ СБАЛАНСИРОВАННЫХ...165Реализация оператора DELETEСделаем набросок функции deletel, которая по заданному указателю на узел nodeи элементу л: удаляет лист, являющийся потомком узла node и содержащий значениех, если, конечно, такой лист существует1. Если после удаления узел node имееттолько одного сына, то функция deletel возвращает значение true, а если узел nodeимеет двух или трех сыновей, то возвращает значение false. Эскиз этой функции показан в следующем листинге.Листинг 5.12. Рекурсивная процедура удаленияfunction deletel ( node: ttwothreenode; x: elementtype ): boolean;varonlyone: boolean;.{ содержит значение, возвращаемое по вызову deletel }begindeletel := false/if сыновья node являются листьями then beginif x принадлежит этим листьям then beginудаление х;смещение сыновей node, которые были справа от х,на одну позицию влево;if node имеет только одного сына thendeletel:= trueendendelse begin { node находится на втором уровне или выше }определяется, какой сын узла node можетиметь среди своих потомков х;onlyone:= deletel(w, x); { в зависимости от ситуации wобозначает nodeT.firstchild, nodet.secondchild илиnodet.
thirdchild }if onlyone then begin { просмотр сыновей node }if w — первый сын node thenif у — 2-й сын node, имеющий 3-х сыновей then1-й сын у делается 2-м сыном w;else begin { у имеет двух сыновей }сын w делается 1-м сыном у;удаление w из множества сыновей узла node;if node имеет только одного сына thendeletel:= trueend;if w — второй сын node thenif у — 1-й сын node, имеющий 3-х сыновей then3-й сын у делается 1-м сыном welse { у имеет двух сыновей }if существует z — 3-й сын node,имеющий 3-х сыновей then1-й сын z делается 2-м сыном welse begin{ у node нет сыновей, имеющих трех детей }сын w делается 3-м сыном у;1Полезным вариантом такой функции была бы функция, которая только по ключевомузначению удаляла все элементы с этим ключом.166ГЛАВА 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
