В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 66
Текст из файла (страница 66)
Обработка каждого из них производится точно так же, как и обработка всего исходногодерева. Это обстоятельство позволяет дать рекурсивное описание рассмотренной функции, что предлагается сделать читателю самостоятельно,Длительность операций поиска (число вершин, которые надо перебратьдля этой цели) зависит от структуры дерева. Действительно, дерево можетбыть вырождено в однонаправленный список (иметь единственнуюветвь) — такое дерево может возникнуть, если записи поступали в таблицу19*291в порядке возрастания (убывания) их ключей, например:ччч15В этом случае время поиска будет такое же, к а к и в однонаправленномсписке, т.е.
в среднем придется перебрать N/2 вершин.Наибольший эффект использования дерева достигается в том случае,когда дерево "сбалансировано", т.е. когда все его вершины — к р о м е конечных — имеют к а к левого, так и правого преемника, В этом случае поискосуществляется так же быстро, к а к и при дихотомии, т.е. для поиска придется перебрать не более log 2 N вершин.Существуют различные и не очень сложные алгоритмы, с помощью которых можно произвести "балансировку" дерева — после обработки дерева по такому алгоритму у максимально возможного числа вершин появятся две ветви.
Другими словами, дерево перестраивается таким образом,что оно становится максимально ветвистым и низким. Более подробно этивопросы рассмотрены в книге Н. Вирта "Алгоритмы + структуры данных = программы". М„ Мир, 1985.Включение записи в дерево. Ради краткости изложения мы не будемрассматривать случай замены записи, а будем исходить из того, что в таблице нет записи с тем же ключом, что и у включаемой записи.Для включения новой записи в таблицу прежде всего нужно найти в дереве ту его вершину, к которой можно "подвесить" (присоединить) новуювершину, соответствующую включаемой записи.
Алгоритм поиска нужнойвершины, вообще говоря, тот же самый, что и при поиске вершины с заданн ы м ключом. Эта вершина будет найдена в тот момент, когда в качествеочередной ссылки, определяющей ветвь дерева, в которой надо продолжить поиск, окажется ссылка nil. Однако непосредственно использоватьдля наших целей описанную выше функцию ПОИСКВДЕР нельзя, потомучто по окончании вычисления ее значения не фиксируется та вершина, изкоторой была выбрана ссылка nil. Поэтому модифицируем описание функции поиска так, чтобы в качестве ее побочного эффекта фиксироваласьссылка на вершину, в которой был найден заданный ключ (в случае успешного поиска), или ссылка на вершину, после обработки которой поискпрекращен (в случае неуспешного поиска).•function ПОИСК < {ключ: У к: integer; var {в дереве)- d,{результат:> Рез: укзв): boolean;var p,q:yK3B;b: boolean;begin{подготовка к циклу>b:=false; p:=d;if d£nil then292repeatq:=p;if p t.
Ключ=к then {запись найдена) b:=trueel sebegin {запоминание оёраб.вершины) q:=p;if к<р+.Ключ then р:=р*.Лев else р=р!.Правenduntil b or <p=nil>;ПОИСК:=b; Pe3:=qendПри наличии в программе такого описания функции, процедура включениязаписи в таблицу, представленную в виде двоичного дерева, описываетсядостаточно просто:procedure ВТАБЯ ({ключ) k: integer;{в дерево) var d: укзв;{запись) гес: текст);var r,s: укзв;t: укт;beginif not ПОИСК(k,d,г) thenbegin {занесение в таблицу текста записи)new(t); 11:=гее;{формирование новой вершины в дереве)new(s); 5+.Ключ:=к; st.Ссылка:=t;st.Лев:=ni1;st.Прав:=ni1;if d=nil then {если дерево пусто, то созданноезвено сделать вершиной дерева) d:=selse {подсоединить новую вершину к дереву)if к<г+.Ключ then г+.Лев:=& else г+.Прав:=зendend;Удаление записи из дерева. Сейчас мы приступаем к описанию операцииудаления из двоичного дерева звена с заданным ключом.
Непосредственноеудаление записи (для чего достаточно удалить из дерева соответствующуюей вершину) реализуется очень просто, если эта вершина является конечной("листом" дерева) или из нее выходит только одна ветвь — для этого достаточно скорректировать соответствующую ссылку у вершины предшественника (на приводимой ниже схеме удаляемая вершина заштрихована):1293Основная трудность состоит в удалении вершины, из которой выходятдве ветви, поскольку в удаляемую вершину входит одна стрелка, а выходит две..
В этом случае нужно найти подходящее звено дерева, котороеможно было бы вставить на место удаляемого, причем это подходящеезвено должно просто перемещаться. Такое звено всегда существует: этолибо самый правый элемент левого поддерева (для достижения этого звена необходимо перейти в следующую вершину по левой ветви, а затем переходить в очередные вершины только по правой ветви до тех пор, покаочередная такая ссылка не будет равна nil), либо самый левый элементправого поддерева (для достижения этого звена необходимо перейтив следующую вершину по правой ветви, а затем переходить в очередныевершины только по левой ветви до тех пор, пока очередная такая ссылкане будет равна nil).
Очевидно, что такие подходящие звенья могут иметьне более одной ветви. Ниже схематично изображено исключение издвоичного дерева вершины с ключом 50, из которой выходят две стрелки.УX/5/3 0100ЧюоX^X335 0х120130„ж^55X3 5Ч/603 5\\33Вид дерева до удаления элементас ключом 50ЧЧ130Ч60Вид дерева после удаления элементас ключом 50Итак, процедура исключения из двоичного дерева звена с заданным ключом должна различать три случая:1) звена с заданным ключом в дереве нет;2) звено с заданным ключом имеет не более одной ветви;3) звено с заданным ключом имеет две ветви.Ниже мы приводим описание процедуры исключения вершины с заданнымключом, автором которого является Н, Вирт (еще раз напомним, что в описаниях процедур и функций используются введенные ранее в употреблениеописания типов значений):procedure УДА/1ДР({из дерева} var d: укзв;Сзвена с ключом}k:integer);var q: укзв;procedure УД(уаг г: укзв);begin i-f r + .npae=nil thenbegin qt.Ключ:=rt.Ключ;q:=r;г:=гКЛевendelse УД(rt,Прав)end;294qt.Ссылка:=rt.Ссылка;begin {удаление элемента с ключом к из дерева d>if d=nil then {первый случай процедуры исключения)writeln( "Элемент_с заданным_ключом_в_дереве_не_найден ' )else {поиск элемента с заданным ключом)if k<d+.Ключ then УДАЛДР<d+.Лев,k>elseif k>dt.Ключ then УДАЛДР(dt.Прав,k) elsebegin {элемент найден, необходимо его удалить)q:=d;{второй случай процедуры удаления)if qt.npaB=nil then d ^ q t - Л е в elseif qt.fleB=nil then d:=qt.npaB else{третий случай процедуры удаления)yA(q+.Лев)endend;Вспомогательная рекурсивная процедура с именем УД вызывается лишьв третьем случае процедуры исключения.
Она "спускается" до самого правого звена левого поддерева удаляемого элемента q t , а затем заменяет значения полей Ключ и Ссылка в qt соответствующими значениями полейКлюч и Ссылка звена r t . После этого звено, на которое указывает г, можноисключить (это делается оператором присваивания г: = г ! . Л е в ) . Заметим,что можно освободиться и от памяти, занимаемой удаленным звеном,используя стандартную процедуру dispose.
Эту модификацию приведенноговыше описания процедуры УДАЛДР мы предлагаем сделать читателю самостоятельно в качестве упражнения.П р и м е р 14.3. Во внешнем файле input задана информация о студентахфакультета университета. Причем сведения о каждом студенте включаютв себя: фамилию, номер группы, оценки, полученные в последнюю сессиюДля определенности положим, что фамилия состоит не более чем изN = 10 букв, группа задается целым числом из диапазона 100., 699, числоэкзаменов М равно 3, оценка по каждому предмету лежит в диапазоне от 2до 5.
Таким образом, сведения о каждом студенте задаются пятеркой:фамилия (последовательность литер), номер группы (целое число), трицелых числа, определяющие оценки студента, Предположим, что эти сведения каким-либо образом были подготовлены заранее и заданы во внешнем файле с именем Студ.Требуется:— представить исходную информацию в виде двоичного дерева, в вершинах которого содержатся сведения об отдельных студентах, причем фамилия является ключом;— напечатать фамилии студентов, сдавших все экзамены на 5;— напечатать фамилии тех студентов, которые получили по всем тремэкзаменам неудовлетворительные оценки.Схема алгоритма построения двоичного дерева в случае, когда ключамиявляются целые числа, подробно описывалась в начале раздела о двоичныхдеревьях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
