Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 40
Текст из файла (страница 40)
Так же как в случае поиска по списку, сложность условия окончания цикла за- и элементов можно организовать а бинарное дерево с высотой не более чем !одп. Поэтому для поиска среди и элементов может потребоваться не более !они сравнений, если дерево идеально сбалансировано. Очевидно, что дерево — намного более подходясцая форма органиэации такого множества дачных, чем линейный список, который рассматривался в предыдугцем разделе. 233 4,4.
Древовидные структуры ставляст искать лучшее решение. При поиске по списку в конце его помещается барьер. Зтот прием можно применить и в случае поиска по дереву. Использование ссылок позволяет связать все терминальные узлы дерева с одним н тем же барьером. Полученная структура — это уже не просто дерево, а скорее, дерево, все листья которого прицеплены внизу к одному якорю (см. рис. 4.25), Барьер можно также считать общим представлением всех внешних (специальных) узлвв, которыми дополняется исходное дерево (см.
рпс. 4.!9). Полученная в результате упрощенная процедура поиска описана неже: йшсбвп 1рс(х; 1лгейег; тс ген). ''гв1," Ьеа!и в1,1сеу:= х; (барьер) тгп!!е 11.кеу Ф х Пе !1 х < 1).)сеу !!теп 1:= 1!.1ей е)ве 1; = г~,г1361! 1ос;= 1 епй Отметим, что если в дереве с корнем 1 не найдено ключа со значением х, то в этом случае 1ос(х,1) принимает значение з, т. е. ссылки на барьер.
Ссылка на з просто принимает ни себя роль ссылки и!!. 4 4.3. Поиск по дереву с вкисочеиием Возможности техники динамического размещения переменных с доступом к ннм черсз ссылки вряд ли полностью проявляются в тех примерах, где,построенная, структура данных остается неизменной, Более подходящими примерами служат задачи, в которых сама структура дерева изменяется, т. е. дерево растет н/илн уменьшается во время выполнения программы.
Зто также .случай, когда другие представления данных, такие, как массив, не подходят п когда дерево с элементами, связанными ссылками, как раз и есть подходящая структура. Прежде всего рассмотрим случай постошщо растущего, по нцкогда не убывающего дерева. Хоропшм примером этого является задача построения частотного словаря, которая уже разбиралась, когда речь шла о связанных списках. Вернемся к ней снова. В этой задаче задана последовательность слов и нужно установить число появлений каждого слова.
Зто означает, что, начиная с пустого дерева, каждое слово ищется в дереве. Если оно найдено, увеличивается его счетчик появлений, если иет — в дерево вставляется новое слово (с начальным значением счетчика, равным !). Мы называем эту. задачу 4. Динамические информационные структуры поиском по дереву с включением. Предполагаются следующие описания типов: 4уре гег' * ')урогс(; гд = ° гй йеу: тпгеуег; свинг: Ыеяег; )ег'сй гуййг: гер" еий (4.48) Считая, нроме того, что у нас есть исходный файл ключеи Г„ и переменная гоог' указывает на корень дерева поиска, мы можем записать программу следующим образом: гекеу(г'); нИе чеоЩ) йо Ьеййч геад(г', х); ееагсй(х,гоог) епй Определение пути поиска здесь вновь очевидно. Но если он приводит в «тупик», т.
е. к пустому поддереву, обозначен- Рне, 4.26. Включение в упорядоченное бинарное дерево. ному ссылочным значением пП, то данное слово нужно вставить в дерево на место пустого поддерева. Рассмотрим, на. пример, бинарное дерево, показанное на рнс. 4.26, и включение в него слова «Рап(». Результат показан пунктирными линиями на том же рнсупке.
Целиком работа алгоритма приведена в программе 4.4. Процесс поисна представлен в виде рекурсивной процедуры. 4.4. Древоввдиагв стрркгиры Отметим, что ее параметр р передается как параметр-переменная, а не как параметр-значение. Это существенно, по. скольку в случае включения персменног1 должно присваиваться некоторое новое значение ссылке, которая перед зтим имела значение п11.
Для входной последовательности, состоящей пз 21 числа, которая обрабатывалась с помощью программы 4.3, построившей дерево на рис. 4.23, программа 4,4 строит бинарное дерево поиска, показанное на рис, 4.27. Рис 427. Дерево поиска, построенное с помощью программы 4,4. Использование барьера вновь несколько упрощает задачу, что показано в 14.50). Понятно, что в начале программы переменная гоо1 должна инипинроваться ссылкой на барьер, а не значением и11, и перед каждым поиском очередного слова искомое значение х должно присваиваться нолю ключа в барьере.
ртосейпге веагсй(х: 1пгсясг; таг р; ге/'); Ьейщ арй х < р).гссу 4Ьеп веагсй1х,р)Ле~~) е)ае ы х ) р1,ксу ььеп веагсй(х,Я.па)и) е)зе 1а р Ф в 1Ьеп р~.юипг:= р~.соипГ + 1 Е)ЗЕ Ьей1п 1включение1 пои(р); (4.50) иНЬ р7 Йо Ьеящ йсу:= х; 1е~г' ."= 'в; ггяй|:= д1 соилт:= 1 епй епй гзе Е. динамические инутормационные структуры ш1; щ(тг;- п11 Программа 4.4. Поиск с включениями. ргопгатп ггееееагсд(!при!,оигри!)! ( поиск с включением по двоичному дереву» гуре ге~ »магд; хогг! = гееогд !сеу: !пгегег; сони!: !псекег; !е!гт г!кдг: ге1; ° д; гаг гоог: ге!; !с: ~пгеуег; угоеедпгерг!пгггее(и: ге~; 1: !пгекег)! гаг т': !псегег; Ьеа1в11 и ,-ь, в(1 йев МЬв» до Ьеи1п рг!аггее(!е)г, !+ 1); Гог г .'= 1 Фо ! Йо ит!ге(' '),' пг!ге!пфеу); рг(псггее(г!кдг, !+1) епд евй 1 гвоеедвге геагсд(х: !пгекег; гаг р: геД; Ьеп(в Ыр = п11 йев Ьеп»п (слова нет в дереве; включить ееа» пеи (р); ' вИЬ р» до Ьеп(в !сеу:= х; осип!:= 1; !е»г;= евд , свд е1ае И х < р1.!геу 1Ьеп геагсЬ(х, р».!е)!) е1ае 11 х > р».!сеу йеп геагс(т(х, р»'.щдг) е»ео р»',саин!: — — р1.соип! + 1 епд (геагсЬ); Ьеп(в гонг:= в11; вЬ11е — ео!'(!при!) до Ьеп(п геат((!с) ! геагсд((с, гоо!) епа; рг!и!ггее(гор!, 0) епд 4.4.
Древовидные структуры Еще раз, теперь уже последний, построим альтернативну.о версию этой программы, отказавшись от использования рекурсии. Но сейчас избеэкать рекурсии не так просто, как в случае без включения, так как для того, чтобы производить включение, нужно помнить пройденный путь по крайней мере иа один шаг назад.
В программе 4.4 ои запоминается автоматически при использовании параметра-переменной. Чтобы правильно привязать включаемую компоненту, мы должны иметь ссылку на ее предка и знать, включается она в качестве правого или левого поддерева. Для этого вводятся две переменные: р2 и с( (для направления): ртосейоте беатой(зч тгттееег,' гоо!, 'гет); тат р1.р', тет„' с1; !п(ееег; Ьепе р2:= гом; р1:=- р2',.гтк!тт; т1:=-. 1; пЫ1е (р1ФпИ) Л (с(~О) йо Ьеп!п р2:=- р1; !т ее < р1!.Ьет !Ьеп Ьей!п р1:=- р!'.!е)т; с1:=- — 1 епй е1зе К х = р1;.кеу тЬеп Ьей!и р1:.= р1 .гте!тт; т);=- 1 епй е!зо с(:=- О епй," И' т! =.
О !Ьеп у1.;,соттттт: — — р1т1,еоиттт -';- 1 е1ве Ьея!и (включение! пете(р1); и!1Ь рГ йо Ьеп!в кеу:=.- х; !е)с;=- пИ: гтк!тг: —.= пй; оопп!:= 2 евй; !1 й < О тЬеп р2'.!еге;= р1 е1ве р2, ифйт:=- р1 епй епй (4.5! ) Как и в слу тае поиска с включением по списку, используются две ссылки р! и р2, такие, что в процессе поиска р2 всегда указывает на преднкат р!1. Чтобы удовлетворить этому условикт в начале поиска, вводится вспомогательный фиктивный элемент, на который указывает гоой Начало действительного дерева поиска обозначается ссылкой гоо1~.г!Ий, Поэтому программа должна начинаться операторами песо(гоо!); гоо!!.г!ИИ:= п11 вместо начального присваивания гоп!:= п11 4. Динамические инфорчационнме структуры Хотя задача этого алгоритма — поиск, его можно применить и для сортировки. В самом деле, он очень напоминает метод сортировки включением, а поскольку вместо массива используется дерево, пропадает необходимость перемешенпя компонент выше места включения.
Сортировку с помощью дерева можно запрограммировать почти столь же эффективно, как и лучшие методы сортировки массивов. Но небходимо принять некоторые меры предосторожности. Разумеется, при появлении одинаковых ключей, теперь надо поступать иначе. Если в слу.~ае х = р(.йеу алгоритм работает так же, как и в случае х ) р('.ней, то он прсдставляст метод устойчивой сортировки, т. е, элементы с одинаковыми клюгами появляются в той же последовательности при обычном обходе дерева, что и в процессе их включения в дерево. Вообше говоря, имеются лучшие способы сортировки, но в задачах, где требуется и поиск, и сортировка, алгоритм поиска по дереву с включением весьма рекомендуется. Он действительно очень часто применяется в трансляторах н программах работы с банками данных для организации объектов, которые нужно хранить и искать в памяти.
Подходяший прцмср — построение таблицы перекрестных ссылок для заданного текста. Исследуем эту задачу подробно. 11аша цель — написать программу, которая (читая текст г и печатая его с добавлением последовательных номеров строк) собирает все слова этого текста, сохраняя при этом номера строк, в которых онн встречались. Когда этот просмотр закончится, нужно построить таблицу, содержащую все собранные словз в алфавитном порядке, со списками соответству1он1нх строк. О ~евпдно, что дерево поиска (называемое также лексико- графическим деревом) лучше всего подходит для представления слов, встречаюгцихся в тексте.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
