Поиск по дереву с включением

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

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

Прежде всего рассмотрим случай постоянно растущего, но никогда не убывающего дерева. Хорошим примером этого является задача построения частотного словаря, которая уже разбиралась, когда речь шла о связанных списках. Вернемся к ней снова. В этой задаче задана последовательность слов н нужно установить число появлений каждого слова. Это означает, что, начиная с пустого дерева, каждое слово ищется в дереве. Если оно найдено, увеличивается его счетчик появлений, если нет в дерево вставляется новое слово с .начальным значением счетчика, равным 1. Мы называем эту задачу поиском по дереву с включением.

Предполагаются следующие описания типов type ref word, word record key integer 2.8 count integer left, right ref end Считая, кроме того, что у нас есть исходный файл ключей f, а переменная root указывает на корень дерева поиска, мы можем записать программу следующие образом resetf while -eoff do 2.9 begin readf, x searchx, root end Определение пути поиска здесь вновь очевидно. Но сели он приводит в тупик, т. е. к пустому поддереву, обозначен- Рис. 10. Включение в упорядоченное бинарное дерево. ному ссылочным значением nil, то данное слово нужно вставить в дерево на место пустого поддерева.

Рассмотрим, на пример, бинарное дерево, показанное на рис. 10, и включение в него слова Paul. Результат показан пунктирными линиями на том же рисунке. Целиком работа алгоритма приведена в программе 2.1. Процесс поиска представлен в виде рекурсивной процедуры. Отметим, что ее параметр р передастся как параметр-переменная, а не как параметр-значение.

Это существенно, поскольку в случае включения переменной должно присваиваться некоторое новое значение ссылке, которая перед этим имела значение nil. Для входной последовательности, состоящей из 21 числа, которая обрабатывалась с помощью программы 1.1, построившей дерево на рис. 7, программа 2.1 строит бинарное дерево поиска, показанное на рис. 11. Рис. 11. Дерево поиска, построенное с помощью программы 2.1. Использование барьера вновь несколько упрощает задачу, что показано в 2.10. Понятно, что в начале программы переменная root должна инициироваться ссылкой на барьер, а не значением nil, и перед каждым поиском очередного слова искомое значение х должно присваиваться нолю ключа в барьере procedure searchx integer var p ref begin if x p .key then searcltx, p .left elseif x p .key then searchx, p .right elseit p s then p .count p .count 1 elsebegin включение newp 2.10 with p do begin key x left s right s count 1 end end end. program treesearchinput, output поиск с включением по двоичному дереву type ref word word record key integer count integer left, right ref end var root ref k integer procedure printtreew ref l integer var i integer begin if w nil then with w do begin printtreeleft, l1 for i 1 to i do write writelnkey printtreeright, l1 end end procedure searchx 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 searchx, p.left else if x p.key then searchx, p.right else p.count p.count 1 end search begin root nil while - eof input do begin readk searchk, root end printtreeroot,0 end Программa 2.1. Поиск с включениями.

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

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

В программе 2.1 он запоминается автоматически при использовании параметра-переменной.

Чтобы правильно привязать включаемую компоненту, мы должны иметь ссылку на ее предка и знать, включается она в качестве правого или левого поддерева. Для этого вводятся две переменные р2 и d для направления procedure searchx 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 p1 p1.right d 1 end else d 0 end if d 0 then p1.count p1.count 1 else begin включение newp1 with p1 do begin key x left nil right nil count 1 end if d 0 then p2 left p1 else p2.right p1 end end. 2.11 Как и в случае поиска с включением по списку, используются две ссылки pi и р2, такие, что в процессе поиска р2 всегда указывает на предикат pl. Чтобы удовлетворить этому условию в начале поиска, вводится вспомогательный фиктивный элемент, на который указывает root. Начало действительного дерева поиска обозначается ссылкой root.right.

Поэтому программа должна начинаться операторами newroot root.right nil вместо начального присваивания root nil Хотя задача этого алгоритма поиск, его можно применить и для сортировки. В самом деле, он очень напоминает метод сортировки включением, а поскольку вместо массива используется дерево, пропадает необходимость перемещения компонента выше места включения.

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

Но необходимо принять некоторые меры предосторожности. Разумеется, при появлении одинаковых ключей, теперь надо поступать иначе. Если в случае х р .key алгоритм работает так же, как и в случае х р.key, то он представляет метод устойчивой сортировки, т. е. элементы с одинаковыми ключами появляются в той же последовательности при обычном обходе дерева, что и в процессе их включения в дерево.

Вообще говоря, имеются лучшие способы сортировки, но в задачах, где требуется и поиск, и сортировка, алгоритм поиска по дереву с включением весьма рекомендуется. Он действительно очень часто применяется в трансляторах и программах работы с банками данных для организации объектов, которые нужно хранить и искать в памяти. Подходящий пример построение таблицы перекрестных ссылок для заданного текста. Исследуем эту задачу подробно. Наша цель написать программу, которая читая текст f и печатая его с добавлением последовательных номеров строк собирает все слова этого текста, сохраняя при этом номера строк, в которых они встречались.

Когда этот просмотр закончится, нужно построить таблицу, содержащую все собранные слова в алфавитном порядке, со списками соответствующих строк. Очевидно, что дерево поиска называемое также лексикографическим деревом лучше всего подходит для представления слов, встречающихся в тексте. Теперь каждый узел не только содержит слово в качестве значения ключа, но одновременно представляет собой начало списка номеров строк. Каждую запись номера строки мы будем называть отметкой.

Следовательно, в этом примере мы встречаем и деревья, и линейные списки. Программа состоит из двух основных частей см. программу 2.2 фазы чтения текста и построения дерева и фазы печати таблицы. Ясно что последняя является частным случаем процедуры обхода дерева, где посещение каждого узла предполагает печать, значения ключа слова и проход по связанному с ним списку номеров строк отметок.

Кроме того, полезно привести еще некоторые пояснения, относящиеся к программе 2.2 1. Словом считается любая последовательность букв и цифр, начинающаяся с буквы. program crossreff, output построение таблицы перекрестных ссылок с использованием двоичного дерева const c1 10 длина слова с2 8 количество слов в строке с3 6 количество цифр в числе с4 9999 максимальный номер строки type alfa packed array 1 c1 of char wordref word itemref item word record key alfa first, last itemref left, right wordref end item packed record lno 0 c4 next itemref end var root wordref k, kl integer n integer номер текущей строки id alfa f text a array 1 c1 of char procedure search var wl wordref var w wordref x itemref begin w wl if w nil then begin neww newx, 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 searchw.left else if id w.key then searchw.right else begin newx x.lno n x.next nil w.last.next x w.last x end end search procedure printtreew wordref procedure printwordwword var l integer x itemref begin write, w.key x w.first I 0 repeat if l c2 then begin writlen l 0 write cll end l l1 writex.lnoсЗ x х.next until x nil writeln end printword begin if w nil then begin printtreew .left printwordw printtreew.right end end printtree begin root nil n 0 k1 cl pageoutput resetf while - eoff do begin if n c4 then n 0 n nl writenсЗ следующая строка write while eolnf do begin просмотр непустой строки if f in a z then begin k 0 repeat if k cl then begin k k1 ak f end writef getf until -f in a z,0 9 if k k1 then k1 k else repeat ak1 k1 k1-1 until k1 k pack a, l,id searchroot end else begin проверка на кавычку или комментарий if f then repeat writef getf until f else if f then repeat writef getf until f writef getf end end writeln getf end pageoutput printtreeroot end Программа 2.2. Построение таблицы перекрестных ссылок. 2. В качестве ключа хранятся только первые с1 символов. Таким образом, два слова, у которых первые с1 символов не различаются, считаются одинаковыми. 3. Эти с1 символов упаковываются в массив id типа alfa. Если достаточно мало, во многих вычислительных машинах такие упакованные массивы могут сравниваться с помощью одной команды. 4. Переменная k1 это индекс, который, используется в следующем инвариантном условии, касающемся буфера символов а аi для i k1 1 cl. Это означает, что слова, состоящие из менее чем с1 символов, дополняются соответствующим количеством пробелов. 5. Желательно, чтобы номера строк в таблице перекрестных ссылок печатались в возрастающем порядке.

Поэтому список отметок должен формироваться в. том же. порядке, в каком они печатаются.

Это требование предполагает использование в каждом слове-узле двух ссылок, из которых одна указывает на первый, а вторая на последний элемент списка отметок. 6. Сканер строится таким образом, что слова в кавычках и внутри комментариев не включаются в таблицу перекрестных ссылок при этом предполагается, что кавычки и комментарии не переходят через концы строк.

В табл. 1.2 показан результат обработки некоторого текста программы. 2.3. Удаление из дерева.

Теперь мы переходим к задаче, обратной включению, а именно удалению.

Нам нужно построить алгоритм для удаления узла с ключом х из дерева с упорядоченными ключами. К сожалению, удаление элемента обычно не так просто, как включение.

Таблица 2.1. Пример распечатки, полученной в результате работы программы 2.2. 1. PROGRAM PERMUTE OUTPUT 2. CONST N 4 3. VAR IINTEGER 4. AARRAY1 N OF INTEGER 5. 6. PROCEDURE PRINT 7. VAR IINTEGER 8. BEGIN FOR I1 TO N DO WRITE AI3 9. WRITELN 10. END PRINT 11. 12. PROCEDURE PERM KINTEGR 13. VAR I,XINTEGER 14. BEGIN 15. IF K1 THEN PRINT ELSE 16. BEGIN PERM K-1 17. FOR I1 TO K-1 DO 18. BEGIN XAIAK AKX 19. PERM K-1 20. XAI AI AK AKX 21. END 22. END 23. END PERM 24. 25. BEGIN 26. FOR I1 TO N DO AI 1 27. PERMN 28. END. ARRAY 4 A 4 8 18 18 18 20 20 20 20 26 BEGIN 8 14 16 18 25 CONST 2 DO 8 17 26 ELSE 15 EMD 10 21 22 23 28 FOR 8 17 26 IF 15 INTEGER 3 4 8 12 13 I 3 7 8 8 13 17 18 18 20 20 26 26 26 K 12 15 16 17 18 18 19 20 20 N 2 4 8 26 27 OF 4 OUTPUT 1 PERMUTE 1 PERM 12 16 19 27 PRINT 6 15 PROCEDURE 6 12 PROGRAM 1 THEN 15 TO 8 17 26 VAR 3 17 13 WRITELN 9 WRITE 8 X 13 18 18 20 20 Оно просто в случае, когда удаляемый элемент является терминальным узлом или имеет одного потомка.

Рис. 12. Удаление из дерева.

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

В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. Ясно, что такие элементы не могут иметь более одного потомка. Подробно это показано в рекурсивной процедуре, называемой delete 2.12. Она различает три случая 1. Компоненты с ключом, равным х, нет. 2. Компонента с ключом х имеет не более одного потомка. 3. Компонента с ключом х имеет двух потомков. procedure delete x integer var pref var q ref procedure del var r ref begin if r.right nil then del r.right else begin q.key r.key q.count r.count q r r r.left end end begin delete 2.12 if p nil then writeln word is not in tree else if x p.key then deletex, p.left else if x p.key then deletex, p.right else begin delete p q p if q.right nil then p q.left else if q.left nil then p q.right else del q.left disposeq end end delete Вспомогательная рекурсивная процедура del вызывается только в 3-м случае. Она спускается вдоль самой правой ветви левого поддерева удаляемого узла q и затем заменяет существенную информацию ключ и счетчик в q соответствующими значениями самой правой компоненты r этого левого поддерева, после чего от r можно освободиться.

Процедуру disposeq можно рассматривать как обратную процедуре newq. Последняя занимает память для новой компоненты, а первая может применяться для указания вычислительной системе, что память, которую занимает q, можно освободить и потом вновь использовать некоторый вид чистки памяти.

Для иллюстрации работы процедуры 2.12 мы отсылаем читателя к рис. 12. Задано начальное дерево а, из которого последовательно удаляются узлы с ключами 13, 15, 5, 10. Полученные деревья показаны на рис. 12 b е. 3.