Древовидные структуры

30 Содержание: 1. Исследовательская часть ……………………………………….2 1.1. Основные понятия и определения ……………………..2 2. Конструкторская часть ………………………………………..1 5 2.1. Основные операции с бинарными деревьями …….1 5 2.2. Поиск по дереву с включением ……………………...1 9 2.3. Удаление из дерева ………………………………………3 0 3. Технологическая часть……………………………………….. 35 Список литературы 1. Исследовательская часть. Древовидные структуры 1.1. Основные понятия и определения. П оследовательности и списки можно опре делить следующим образом: любая последовательность (спи сок) с базовым типом Т — это либо: 1) пустая последовательность (список); либо 2) конкатенация (цепочка) из элемента типа Т и последова тельности с базовым типом Т. Здесь для определения принципов структурирования (сле дования или итерации) используется рекурсия. Следование и итерация встречается настолько часто, что их обычно счи тают фундаментальными «образами» как структур данных, так и «управления» в программах. Однако всегда следует помн ить, что с помощью рекурсии их только можно опреде лять, по рекурсии можно эффективно использо в ать для определения более сложных структур. Хоро шо известным примером служат деревья. Пусть дре вовидная структура определяется следующим образом: дре во ви д ная структура с базовым типом Т — это либо: 1 ) путая структура; либо 2) узел типа Т, с которым связано конечное число древовид ных структур с базовым ти по м Т, называемых подде ревьями. Из сходства рекурсивных определений последовательно стей и древовидных структур видно, что последовательность (список) есть древовидная структура, у которой каждый узел имеет не более одного «поддерева». Поэтому последователь ность (список) называется также вырожденным деревом. Существует несколько способов изображения древовидной структуры. Например, пусть базовый тип Т есть множество букв; такая древовидная структура разными способами изо бражена на рис. 1. Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны. С помощью графа можно наглядно представить разветвляющиеся связи, которые по понятным причинам привели к общеупотребитель ному термину «дерево». Однако довольно странно, что де ревья принято рисовать перевернутыми или — если кто-то предпочитает иначе выразить этот факт — изображать корни дерева. Но последняя формулировка вводит в заблуждение, так как верхний узел (А) обычно называют корнем. Хотя мы сознаем, что в природе деревья представляют собой не сколько более сложные образования, чем наши абстракции, в дальнейшем древовидные структуры будем называть просто деревьями. Упорядоченное дерево — это дерево, у которого ветви каж дого узла упорядоче ны . Следовательно, два упорядочен ных дерева на рис. 2 — это особые, отличные друг от друга деревья. Узел у, который находится непосредственно под узлом х, называется (непосредственным) потомком х; если х находится на уровне i , то говорят, что у — на уровне i + 1. Наоборот, узел х называется (непосредственным) предком y . Считается, что корень дерева расположен на уровне 1. Макси мальный уровень какого-либо э лемента дерева называет cz его глубиной или высотой. Если элемент не имеет потомков, он называется терми нальным элементам или листом, а элемент, не являющ ийся терминальным, называется внутренним узлом. Число ( не по средственных) потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степе нь де рева. Число ветвей, или ребер, которые нужно пройти, чт обы продвинуться от корня к узлу х, называется длиной пути к х . Корень имеет длину пути 1, его непосредственные потом к и — длину пути 2 и т. д. Вообще, узел на уровне i имеет дли ну пути i . Длина пути дерева определяется как сумма дли н пу тей всех его узлов. Она также называется длиной вн ут рен него пути. ( a ) ( A ( B ( D ( I ), E ( J , K , L )), C ( F ( O ), G ( M , N ) , H ( P )))) ( b ) ( c ) ( d ) Рис. 1. Представления древовидной структуры: (а) вложенные множества; ( b ) вложенные скобки; (с) ломаная последовательность; ( d ) граф. Например, длина внутреннего пути дерева, изобра женного на рис. 1 . , равна 52. Очевидно, что средняя длина пути P I есть ( 1.1 ) где n i - число узлов на уровне i . Для того чтобы определить, что называется длиной в нешнего пути, мы будем дополнят дерево специальным узлом каждый раз, когда в нем в с тре чается нулевое поддерево. П ри этом мы считаем, что все узлы должны иметь одну и ту же степень — степень дерева. Следо вательно, подобное расшире ние дерева предполагает запол нение Рис. 2 . Два различных бинарных дерева. пустых ветвей, разум еется, при этом специальные узлы не имеют дальнейших потомков. Дерево на рис. 1 , допол ненное специальными узлами, показано на рис. 3 , где спе циальные узлы изображены квадратиками. Рис. 3 . Тернарное дерево со специальными узлами. Длина внешнего пути теперь определяется как сумма дл ин путей всех специальных узлов. Если число специальных узлов на уровне i есть . m i , , то средняя длина внешнего пути P E равна ( 1.2 ) У дерева, приведенного на рис. 3 , длина внешнего пути равна 153. Число специальных узлов m , которые нужно добавить к дереву степени d , непосредственно зависит от числа п ис ходных узлов. Заметим, что на каждый узел указывает ровно одна ветвь. Следовательно, в расширенном поддереве имеется m + п ветвей. С другой стороны, из каждого исходного узла выходят d ветвей, а из специальных узлов — ни одной. По этому всего имеется dn +1 ветвей (1 дает ветвь, указываю щую на корень). Из этих двух формул мы получаем следую щее равенство между числом т специальных узлов и п исход ных узлов: dn + 1 = т + п, или m = ( d — l ) n 1 . ( 1.3 ) Максимальное число узлов в дереве заданной высоты h достигается в случае, когда все узлы имеют d поддеревьев, кроме узлов уровня h , не имеющих ни одного. Тогда в дереве степени d первый уровень содержит 1 узел (корень), уровень 2 содержит d его потомков, уровень 3 содержит d 2 потомков d узлов уровня 2 и т. д. Это дает следующую величину: ( 1.4 ) в ка честве максимального числа узлов для дерева с высотой h и степенью d . При d = 2 мы получаем ( 1.5 ) Упорядоченные деревья степени 2 играют особо важную роль. Они называются бинарными деревьями. Мы определяем упорядоченное бинарное дерево как конечное множество эле ментов (узлов), каждый из которых либо пуст, либо состоит из корня (узла), связанного с двумя различными бинарными деревьями, называемыми левым и правым поддеревом корня. В следующих пунктах этого раздела мы будем рассматривать исключительно бинарные деревья и поэтому будем употреб лять слово «дерево», имея в виду «упорядоченное бинарное дерево». Деревья, имеющие степень больше 2, называются сильно ветвящимися деревьями ( multiway trees ) . Знакомыми примерами бинарных деревьев являются фа мильное (генеалогическое) дерево с отцом и матерью человека в качестве его потомков (!), история теннисного турнира, где узлом является каждая игра, определяемая ее победителем, а поддеревьями — две предыдущие игры соперников; арифме тическое выражение с двухместными операциями, где каждая операция представляет собой ветвящийся узел с операндами в качестве поддеревьев (см. рис. 4 ). Теперь мы обратимся к проблеме представления деревьев. Ясно, что изображение таких рекурсивных структур (точнее, рекурсивно определенных. — Прим. ред.) с разветвлениями предполагает использование ссылок. Очевидно, что не имеет смысла описывать переменные с фиксированной древовидной структурой, вместо этого узлы определяются как переменные Рис. 4. Выражение (а+ b / c )*( d — e * f ), представленное в виде дерева. с фиксированной структурой, т. е. фиксированного типа, где степень дерева определяет число компонент-ссылок, указы вающих на поддеревья данного узла. Ясно, что ссылка на пус тое поддерево обозначается через nil . Следовательно, дерево на рис. 4 состоит из компонент ов такого типа: type node = record op: char; left , right : ^ node ( 1.6 ) end и может строиться, как показано на рис. 5 . Ясно, что существуют способы представления абстракт ной древовидной структуры в терминах других типов данных, например таких, как м ассив. Это — общепринятый способ во всех языках, где нет средств динамического размещения ком понент ов и указания их с помощью ссылок. В этом случае де р ево на рис. 4 можно представить переменной-массивом, описанной как t: аггау [1. .11] of record op: char; left , right : integer ( 1.7 ) end и со значениями компонент ов , приведенными в табл. 1 .1 . Хотя подразумевается, что массив t представляет абстракт ную структуру дерева, мы будем называть его все же не дере вом, а массивом согласно явному определению. Мы не будем обсуждать другие возможные представления деревьев в си стемах, где отсутствует динамическое распределение памяти, Рис. 5 . Дерево, представленное как структура данных. поскольку мы считаем, что системы программирования и язы ки, имеющие это свойство, являются или станут широко рас пространенными. Таблица 1 .1 . Дерево, представленное с помощью массива * 2 3 + 6 4 — 9 5 1 7 8 * 10 11 а 0 0 Ь 0 0 с 0 0 d 0 0 е 0 0 / 0 0 1 2 3 4 5 6 7 8 9 10 11 Прежде чем обсуждать, ка к лучше использовать деревья и как выполнять операции с деревьями, мы покажем на при мере , как программа может строить дерево. Предположим, что нужно сформировать дере в о, содержащее узлы типа, опи санного в ( 1.6 ), а значениям узлов будут п чисел, прочи танных из входного файла. Для усложнения задачи потре буем построить дерево с п узлами и минимальной высотой. Чтобы достичь минимальной высоты при данном числе узлов, нужно располагать максимально возможное число уз лов на всех уровнях, кроме самого нижнего. Это можно сде лать оч е н ь просто, если распределять все поступающие узлы Рис. 6 . Идеально сбалансированные деревья. поро в ну слева и справа от каждого узла. В результате по строенное дерево при данном n имеет вид, как показано на рис. 6 для п = 1 …, 7. Правило равномерного распределения при известном числе узлов п лучше всего формулируется с помощью рекурсии: 1. Взять один узел в качестве ко р н я. 2. Построить левое поддерево с nl = n div 2 узлами тем же способом. 3. Построить правое поддерево с п r = п— nl — 1 узлами тем же способом. Это правило описано реку рсивн ой процедурой tree , вхо дящей в програм му 1 .1 , которая читает входной файл и строит идеально сбалансированное дерево. Мы получаем такое опре деление : program bui l dtree ( input , output ); type ref = ^ node ; n о de = record к ey : integer ; left , right : ref end ; Var n : integer ; root: ref; function tree (n: integer); ref; var newnode: ref; x , nl , nr : integer ; begin построение идеально сбалансированного дерева с n узлами if n = 0 then tree:= nil else begin nl := n div 2; nr := n— nl— 1; r e ad(x); new ( newnode); with newnode ^ do begin key := x; left:= tree(nl); right := tree(nr) end ; tree := newnode end end tree ; procedure printree(t:ref; h: integer); var i: integer; begin печать дерева t со сдвигом h if t <> nil then with t ^ do begin printtree(left, h+1); for i:= 1 to h do write(' '); writeln(key); printtree(right, h+l) end end printtree ; begin первое целое число есть число узлов read(n) ; root := tree(n); printtree(root,0) end . Программа 1 .1 . Построение идеально сбалансированного дерева . Дерево идеально сбалансировано, если для каждого его узла количества узлов в левом и правом поддереве раз личаются не более чем на 1. Предположим, например, что и меются следующие входные данные для дерева с 21 узлом: 21 8 9 11 15 19 20 21 7 3 2 15 6 4 13 14 10 12 17 16 18 Тогда программа 1 .1 строит идеально сбалансированное де рево, показанное на рис. 7 . Рис. 7 . Дере в о, построенное с помощью программы 1.1 . Отметим простоту и ясность этой программы, достигнутые благодаря использованию рекурсивных процедур. Очевидно, что рекурсивные алгоритмы особенно уместны, когда про грамма должна обрабатывать данные, структура которых определена рекурсивно. Это вновь отражается в процедуре printtree , которая печатает полученное дерево: пустое дерево не печатается для поддерева уровня L , а вначале печатается его левое поддерево, затем узел, который выделяется предше ствующими L пробелами, и, наконец, печатается его правое поддерево. Преимущество рекурсивного алгоритма особенно наглядно по сравнению с его нерекурсивной формулировкой. Читателю предлагается проявить с вою изобретательность и написать нерекурсивную программу, строящую такие же деревья, прежде чем смотреть на ( 1.8 ). Эта программа приведена без дальнейших комментариев и может служить упражнением для читателя. Ему предлагается выяснить, как и почему она работает. program buildtree ( input , output ); type ref = ^ node; node = record key: integer; left, right: ref end ; Var i,n,nl,nr,x: integer; root,p,q,r,dmy: ref; s: array [1.. 30] of стек record n: integer; rf; ref end ; begin первое целое число есть число узлов read(n); new(root); new(dmy); фиктивный элемент i:= 1; s[1].n := n; s[1].rf : = root; repeat n := s[i].n; r:= s[i] .rf; i:= i— 1; из стека if n = 0 then r ^ .right := nil else begin p := dmy; (1.8) repeat nl:= n div 2; nr:= n— nl— 1; read(x); new q); q ^ .key := x; i :=i+1; s[i].n := nr; s[i].rf:= q; в стек n := nl; p ^ .left := q; p := q until n =0; q ^ .left := nil; r ^ .right := dmy ^ .left end until I = 0; printtree (root ^ .right,0) end . 2. Конструкторская часть. 2.1. Основные операции с бинарными деревьями . Имеется много задач, которые можно выполнять на древо видной структуре; распространенная задача — выполнение заданной операции Р с каждым элементом дерева. Здесь Р рассматривается как параметр более общей задачи посеще ния в сех узлов, или, как это обычно называют, обхода дерева. Если рассматривать эту задачу как единый последова тельный процесс, то отдельные узлы посещаются в некотором определенном порядке и могут считаться расположенными лине йно. В самом деле, описание мног их алгоритмов суще ственно упрощается, если можно говорить о переходе к сле дующему элементу дерева, имея в виду некоторое упоря дочение. Существуют три принципа упорядочения, которые есте ственно вытекают из структуры деревьев. Так же как и саму древовидную структуру, их удобно выразить с помощью ре курсии. Обращаясь к бинарному дереву на рис. 8 , где R обозначает корень, а А и В — левое и правое поддеревья, мы можем определить такие три упорядочения: 1. Сверху вниз: R , А, В (посетить корень до поддеревьев); 2. Слева направо: A, R, В 3. Снизу вверх: А, В, R (посетить корень после подде ревьев) Обходя дерево на рис. 4 и выписывая символы, находя щиеся в узлах, в том порядке, в котором они встречаются, мы получаем следующие последовательности: 1. Сверху вниз: * + a/b c — d * ef 2. Слева на право a + b / c * d — e * f 3. Снизу вверх: abc/ + def * — * Мы узнаем три формы записи выражений: обход сверху вниз дает префиксную запись, обх о д снизу вверх — постфикс ную запись, Рис. 8 . Б инарное дерево. а обход слева направо дает привычную инфикс ную запись, хотя и без скобок, необходимых для определения порядка выполнения операций. Теперь выразим эти три метода обхода как три конкрет ные программы с явным параметром t , означающим дерево, с которым они имеют дело, и неявным параметром Р, озна чающим операцию, которую нужно выполнить с каждым уз лом. Введем следующие определения : type ref = ^ node node = record … ( 2. 1 ) left,right: ref end Эти три метода легко сформулировать в виде рекурсивных процедур; они вновь служат примером того, что действия с рекурсивно определенными структурами данных лучше всего описываются рекурсивными алгоритмами. p rocedure preorder (t : ref); begin if t <> nil then begin P(t); preorder(t ^ .left); ( 2.2 ) preorder(t ^ .right) end end procedure postorder(t: ref); begin if t <> nil then begin posorder(t ^ . left); postorder (t ^ .right); ( 2.3 ) P ( t) en d end procedure inorder(t: ref); begin if t <> nil then begin wordcr ( t ^ . le ft) ; P ( t ); ( 2.4 ) I norder ( t ^ . right ) end end . Отметим , что ссылка t передается как параметр - значение . Это отражает тот факт, что здесь существенна сама ссылка (указание) на рассматриваемое поддерево, а не переменная, значение которой есть эта ссылка и которая могла бы изме нить значение, если бы t передавался как параметр-пере менная. Пример подпрограммы, осуществляющей обход дерева,— это подпрограмма печати дерева с соответствующим сдвигом, выделяющим каждый уровень узлов (см. программу 1 .1 ). Бинарные деревья часто используются для представления множеств данных, элементы которых ищутся по уникальному, толь ко им присущему ключу. Если дерево организовано таким об разом, что для каждого узла t i все ключи в левом подде реве , меньше ключа t i , а ключи в правом поддереве больше клю ча t i , то это дерево называется деревом поиска. В дереве по иска можно найти место каждого ключа, двигаясь начиная от корня и переходя на левое или правое поддерево каждого уз ла в зависимости от значения его ключа. Как мы видели, п элементов можно организовать в бинарное дерево с высотой не более чем log п. Поэтому для поиска среди п элементов может потребоваться не более log n сравнений, если дерево идеально сбалансировано. Очевидно, что дерево — намного более подходящая форма организации такого множества дан ных, чем линейный список, который рассматривался в преды дущем разделе. 30 S Рис. 9 . Дерево поиска с барьером. Так как этот поиск проходит по единственному пути от корня к искомому узлу, его можно запрограммировать с по мощью итерации ( 2.6 ): function loc(x: integer; t : ref): ref; var found: boolean; begin found := false; while ( t <> . nil) Л - found do begin ( 2.6 ) if t ^ .key — x then found := true els e if t ^ .key > x then t := t ^ .left else t := ^ .right end ; loc := t end . Функция loc x , t ) имеет значение nil , если в дереве с кор нем t не найдено ключа со значением х. Так же как в случае по иска по списку, сложность усло в и я окончания цикла за ст авляет искать лучшее решение. При поиске по списку .конце его помещается барьер. Этот прием можно применить в случае поиска по дер еву. Использование ссылок позво л яет связать все терминальные узлы дерева с одним и тем же барьером . Полученная структура — это уже не просто дерево, а скорее, дерево, все листья, которого прицеплены внизу к одному якорю (см. рис. 9 ). Барьер можно также считать общ им представлением всех внешних (специальных) узлов, кот орыми дополняется исходное дерево (см. рис. 3 ). По лу ченная в результате упрощенная процедура поиска описана ниже: function loc(x : integer; t: ref) : ref; begin s ^ .key := x; барьер ( 2.7 ) while t ^ .key <> x do if x < t ^ .key then t : = t ^ .left else t := t ^ . right; loc := t e nd . Отметим, что если в дереве с корнем t не найдено ключа со значением х, то в этом случае loc ( x , t ) принимает значе ние s , т. е. ссылки на барьер. Ссылка на s просто принимает н а себя роль ссылки nil . 2.2. Поиск по дереву с включением . Возможности техники динамического размещения пере м е нных с доступом к ним через ссылки вряд ли полностью проявляются в тех примерах, где по строенная структура данн ых остается неизменной. Более подходящими примерами слу жат задачи, в которых сама структура дерева изменяется, т . е. дерево растет и/или уменьшается во время выполнения программы. Это также .случай, когда другие представления данных, такие, как массив, не подходят и когда дерево с эле ментами, связанными ссылками, как раз и есть подходящая структура. Прежде всего рассмотрим случай постоянно растуще го, н о никогда не убывающего дерева. Хорошим примером этого является задача построения частотного словаря, которая уже разбиралась, когда речь шла о связанных списках. Вернемся к ней снова. В этой задаче задана последовательность слов н нужно установить число появлений каждого слова. Это оз начает, что, начиная с пустого дерева, каждое слово ищется в дереве. Если оно найдено, увеличивается его счетчик появле ний, если нет — в дерево вставляется новое слово (с .началь ным значением счетчика, равным 1). Мы называем э ту задачу поиском по дереву с включением. Предполагаются следующие описания типов : type ref = ^ word', word= record key : integer; ( 2.8 ) count: integer; left, right: ref end Считая, кроме того, что у нас есть исходный файл ключей f , а переменная root указывает на корень дерева поиска, мы можем записать программу следующие образом: reset(f); while -eof(f) do ( 2.9 ) begin read(f,x); search(x,root) end Определение пути поис ка здесь вновь очевидно. Но сели он приводит в «тупик», т. е. к пустому поддереву, обозначен- Рис. 10 . Включение в у порядоченное бинарное дерево. ному ссылочным значением nil , то данное слово нужно вста вить в дер ев о н а мест о пустого под де рева. Рассмотрим, на пример, бинарное дерево, показанное на рис. 10 , и включе ние в него слова " Paul ". Результат показан пунктирными ли ниями на том же рисунке. Целиком работа алгоритма приведена в программе 2. 1 . Процесс поиска представлен в виде рекурсивной про цедуры. Отметим , что е е параметр р передастся как параметр-пере менная, а не как параметр-значение. Это существенно, по скольку в случае включения переменной должно присваи ваться некоторое новое значение ссылке, которая перед этим имела значение nil . Для входной последовательности, состоя щей из 21 числа, которая обрабатывалась с помощью про граммы 1 .1 , построившей дерево на рис. 7 , программа 2. 1 строит бинарное дерево поиска, показанное н а рис. 11 . Рис . 11 . Д е ре во поиска, построенное с пом ощ ью программы 2. 1 . Использование барьера вновь несколько упрощает задачу, что показано в ( 2.10 ). Понятно, что в начале программы пе ременная root должна инициироваться ссылкой на барьер, а не значением nil , и п е р е д каждым поиском очередного слова искомое значение х должно присваиваться нолю ключа в барьере procedure se arch(x: integer; var p: ref); begin if x < p ^ .key then searclt(x,p ^ . left) else if x > p ^ .key t hen search(x,p ^ .right) else it p <> s then p ^ .count : = p ^ .count + 1 else begin включение n e w(p); ( 2.10 ) with p ^ do begin key := x; left := s; right := s; count := 1 en d end end . program treesearch ( input , output ); поиск с включением по двоич ному дереву type ref = ^ word; word = record key: integer; count: integer; left, right: ref; end ; var root: ref; k: integer; procedure printtree(w: ref; l : integer); var i: integer; begin if w <> nil then with w ^ do begin printtree(left, l +1); for i := 1 to i do write(' '); writeln(key); printtree(right, l +1) end end ; procedure search(x: integer; var p: ref); begin if p = nil then begin слова нет в дереве; включить его new (p); with p ^ do begin key := х ; count := 1; left := nil; right := nil end end else if x < p ^ . key then search(x, p ^ .left) else if x > p ^ .key then sear c h(x, p ^ .right) else p ^ .count := p ^ .cou nt + 1 end search ; begin root : = nil; while - eof (input) do begin read(k); sear ch( k, root) end ; printtree ( root ,0) end Программ a 2. 1 . Поиск с включениями. Еще раз, теперь уже последний, построим альтернативную версию этой программы, отказавшись от использования ре курсии. Но сейчас избежать рекурсии не та к просто, как в случае б ез включения, так как для того, чтобы производить включение, нужно помнить пройденный путь по крайней мере на один шаг назад. В программе 2. 1 он запоминается автома тически при использовании параметра-переменной. Чтобы правильно привязать включаемую компоненту, мы должны иметь ссылку на ее предка и знать, включается она в качестве правого или левого поддерева. Для этого вводятся две переменные: р2 и d (для направления): procedure search ( x: integer; root: ref); var p1, p2: ref; d: integer; begin p2 := root; p1 := p2 ^ .right; d := 1; while ( р 1 <> nil) Л (d <> 0) do begin p2 := p1; if x < p1 ^ .key then begin p1 := p1 ^ .left; d := - 1 end else if x > p1 ^ .key then begin p 1 := p 1 ^ .right; d : = 1 end else d := 0 end ; i f d = 0 then p 1 ^ . count : p 1 ^ .co un t + 1 else begin включение new(p 1 ); with p 1 ^ do begin key := x ; left := nil; right : = nil; count : = 1 end ; if d < 0 then p 2 ^ . .left := p 1 else p2 ^ .right := p 1 end end . ( 2.11 ) Как и в случае поиска с включением по списку, используются две с с ылки pi и р2, такие, что в процессе поиска р2 всегда указывает на предикат pl ^ . Чтобы удовлетвори т ь этому усло вию в начале поиска, вводится вспомогательный фиктивный элемент, н а который указывает root . Начало действительного дерева поиска обозначается ссылкой root ^ . right . Поэтому про грамма должна начинаться операторами new ( root ); root ^ . right : = nil вместо начального присваивания root := nil Хотя задача этого алгоритма — поиск, его можно приме нить и для сортировки. В самом деле, он очень напоминает метод сортировки включением, а поскольку вместо массива используется дерево, пропадает необходимость перемещения компонент а выше места включения. Сортировку с помощью дерева можно запрограммировать почти столь же эффек тивно, как и лучшие методы сортировки массивов. Но не о бхо димо принять некоторые меры предосторожности. Разумеется, при появлении одинаковых ключей, теперь надо поступать иначе. Если в случае х = р ' . key алгоритм работает так же, как и в случае х > р ^ . key , то он представляет метод устой чивой сортировки, т. е. элементы с одинаковыми ключами появляются в той же последов ат ельности при обычном обходе дерева, что и в процессе их включения в дерево. Вообще говоря, имеются лучшие способы сортировки, но в задачах, где требуется и поиск, и сортировка, алгоритм поиска по дереву с включением весьма рекомендуется. Он действительно очень часто применяется в трансляторах и про граммах работы с банками данных для организации объектов, которые нужно хранить и искать в памяти. Подходящий при мер — построение таблицы перекрестных ссылок для задан ного текста. Исследуем эту задачу подробно. Наша цель — написать программу, которая (читая текст f и печатая его с добавлением последовательных номеров строк) собирает все слова этого текста, сохраняя при этом номера строк, в которых они встречались. Когда этот про смотр закончится, нужно по с троить таблицу, содержащую все собранные слова в алфави тно м порядке, со списками соответствующих строк. Очевидно, что дерево по иска (называемое также лексико графическим деревом) лучше всего подходит для представ ления слов, встречающихся в т ексте. Теперь каждый узел не только содержит слово в качестве значения ключа, но одно временно представляет собой начало списка номеров строк. Каждую запись номера строки мы будем называть отметкой. Следовательно, в этом примере мы встречаем и деревья, и ли нейные списки. Программа состоит из двух основных частей (см. программу 2. 2 ): фазы чт ен ия текста и построения дерева и фазы печати таблицы. Ясн о что последняя является част ным случаем процедуры обх од а дерева, где посещение каж дого узла предполагает печа т ь, значения ключа слова и про ход по связанному с ним списку номеров строк (отметок). Кроме того, полезно привести еще некоторые пояснения, от носящиеся к программе 2. 2 : 1. Словом считается любая последовательность букв и цифр, начинающаяся с буквы. program crossref ( f , output ); построение таблицы перекрестных ссылок с использованием двоичного дерева const c 1 = 10; длина слова с2 = 8; количество слов в строке с 3 = 6; количество цифр в числе с 4 = 9999; максимальный номер строки type alfa packed array [1 . . c 1 ] of char; wordref = ^ word; itemref = ^ item; word = record k ey: alfa; first, last: itemref; left, right: wordref end ; item = packed record ln o: 0 . . c4; next: itemref end ; var root: wordref; k,kl: integer; n : integer ; номер текущей строки id: alfa; f : text; a: array [ 1 .. c 1] o f char; procedure search (var w l: wordref); var w: wordref; x: itemref; begin w : = wl; if w = nil then begin n ew(w); new(x), with w ^ do begiu key := id; left := nil; right := nil; first := x; last := x end ; x ^ .lno :— n; x ^ .next : = nil; w1 : = w end else if id < it w ^ .key then search(w ^ .left) else if id > w ^ .key then search (w ^ .right) else begin new(x); x ^ .lno: = n; x ^ .next : = nil; w ^ .last ^ .next : = x; w ^ .last := x end end search ; procedure printtree(w: wordref); procedure printword(w:word); var l: integer; x: itemref; begin write (' ', w.key); x := w.first; I := 0; repeat if l = c2 then begin writlen; l := 0; write(' ':cl+l) end ; l:= l+1; write(x ^ .lno: сЗ ); x:= х ^ .next until x = nil; writeln end printword ; begin if w <> nil then begin printtree(w ^ .left); printword(w ^ ); printtree(w ^ .right) end end printtree ; begin root := nil; n:= 0; k1:= cl; page (output); reset(f); while - eof(f) do begin if n = c4 then n:= 0; n := n + l ; write ( n :сЗ); следующая строка write (' '); while — e oln( f ) do begin просмотр непустой строки if f ^ in ['a' .. ' z '] then begin k := 0; repeat if k < cl then begin k : = k +1; a[k] := f ^ ; end ; write(f ^ ); get(f) until - ( f ^ in ['a'.. 'z' ,'0 '. .'9 ']); if k