Лекции по информатике (984119), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

При этом относительное горизонтальное расположение переставляемых вершин остается без изменений. Мы просто передергиваем ветки поддеревьев как нитки к куклам- марионеткам, «пе перекрещивая пальцы>. Схема алгоритма вклк>чсния в сбалансированное дерево такова: 1. поиск элемента в дереве (неудачный!); 2, включение новой вершины и определение результируюгцего показателя сбалансированности: 3, отход по пути поиска с проверкой показателя сбалансированности для каждой проходимой вершины, балансируя в необходимых случаях соответствующие почдеревья.

Программа включения в сбалансированное дерево приведена в (54]. Проиллюстрируем принцип работы алгоритма: (с) (а) (е) Когда в дереве две вершины (а), включение вершины 7 вначале приводит к дисбалансу правосторонпему линейному списку. Действуя вышерассмотренным случаем 1 (несбалансированность с края), восстановим баланс (Ь).

Последующие включения вершин 2 и 1 снова приводят к случаю 1 несбалансированному справа поддереву с корнем 4 (с). Балансируем, получаем (с1). Последующая вставка элемента с ключом 3 наругпает баланс в корневой вершине со значением 5. Балансировка должна проходить по второму сценарию (случай 2). Результат — дерево (е). При лк>бом следующем включении баланс может быть нарушен лишь в вершине 5. Добавление вершины 6 опять приводит к случаю 2 и к дереву (1). Лвторами идеи была получена оценка, ожидаемой высоты сбалансированного дерева 6 =!опз н 4 г:, где константа с — 0.25, а значит и времени поиска. АИ -сбалансированные деревья ведут себя также.

как сбалансированные„однако затраты на их поддержку. намного меньше. Экспериментальные данные подтверждают. что на два включения приходится одна балансировка. Сложность балансировки оправдана тогда, когда поиск данных происходит значительно чаще, чем вставка. 5.11.3.2 Исключение из сбалансированного дерева Вспоминая, что исключение из дерева сложнее включения, следовало бы того же ожидать и от АУ1-дерева. Процедура слелует схеме включения элемента.

Удаление терминальной или однодстной вершины задача в одно дсйствис. Двудетныс вершины обрабатываются так же, как и раньше: они заменяются на самую пра,вую всршипу ее левого полдерева. Мы ограничимся липп иллюстрацией процесса удаления. (е) 295 Исклнгсенис лсобого элемента из сбалансированного дерева оценивается 0(1од Х). 5.11.3.3 Деревья оптимального поиска Заканчивая рассмотрение деревьев поиска, нельзя пе упомянуть еще об одном способе их усовершенствования. Если а рпогс' или из статистики известны вероятности появления аргументов поиска,, то можно сообразно им реорганизовыва,ть деревья поиска„поднимая к корню более вероятные ключи.

Цена вопроса 0(Хэ). Ху и 'Гаккерохс. Уолкером и Готлибом ~54, 63) были получены более качественныс алгоритмы; затраты памяти 0(Х) вместо 0(Жэ) и затраты на оптимизацию структуры всего лишь 0(М 1оа Ж). 5.11.4 Физическое представление. Отображение на массив. Сплошное предсталленис деревьев удобно пояснить на примере турнирного дерева с фиксированной структурой.

Считая, что участники турнира, образуют полные пары нужной кратности, введем жесткое размещение элементов дерева в массиве. В первом элементе массива разместим корень дерева, во 2-ом и 3-см его левого и правого потомков. Далее поместим пары потомков потомков и т. д. Сыновья элемента дерева с индексом 1 хранятс'.я в элементах массива с индексами 21 и 21 4 1. Согласно данной схеме размещения, у-ый элемент г-ого уровня имеет индекс 2* ' ~ 1 — 1.

Этот метод весьма, экономичен по памяти, пропадан~т только слова, отведенные отсутствунвциги верспинаьс дерева; надо только суметь пометить их как неиспользуемые. Ввиду систематической и легко вычислимой структуры дерева, память на связывание элементов дерева не расходуется. Сложностные оценки для операций поиска, вставки и удаления элемента, в турнирное дерево сплошного представления пропорциональны 01'у). Заметим, что сплошное турнирное представление дерс.ва дает нам еще один обход-- поуровневый„но он не имеет замечательных свойств, которыми ооладают основные методы. Основным неудобством сплошного гсредставления дерева является высокая цена вставки и удаления элементов.

Не мал и перерасход памяти на пустые элементы [44]. Как всегдгч за ликвидацией этих недостатков мы обратимся к динамическим структурам. Для деревьев можно использовать рекурсивные ссылочные представления, которые были разработаны для списков, но с той лишь разницей, что указатели вперед и назад по линейной структуре теперь направляются к левому и к правому поддеревьям соответственно. Тип для вершины дерева, конечно же, фиксирован, но имеет двойное рекурсивное разветвление ~72~: Суре р пос1е; Суре пос1е гесогс1 ор: сЬаг; 1,г:р епс1; Цепное представление рассмотренного нами дерева выражения было рассмотрено выше.

296 5.11.4.1 Прошивка деревьев В представлении бинарного дерева содержатся два указателя -- па левое и правое полдеревья (обозначим их 1 и г, соответственно). У листьев дерева оба эти указателя пустые. Поскольку в бинарном дереве, как правило, около половины узлов являются лист|.ями (если не рассматривать вырожденные случаи), то такое представление оказывается неэкопомичным с точки зрения расхода памяти [44]. В прошит|.|х бинарных деревьях вместо пустых указателей используются специальные связи-пити и каждый указатель в узле дерева до|юлняется однобитовым признаком 1|ад и г1пд, <.оответственно (63). Признак определяет, содержится ли в соответствующем указателе обычная ссылка на поддерево или в нем содержится связь-нить. Связь-нить в поле 1 указывает на узел предпюственник в обратиом порядке обхода, (1пог|1сг), а связь-нить в поле г указывает на узел преемник данного узла в обратном порядке обхода.

Введение признаков Иад и Над не приводит к сколько-нибудь значительному увеличении> затрат памяти, зато упрощает алгоритм обхода деревьев, так как для прошитых деревьев можно выполнить нерекдрсивный обход без использования ппека. Заметим, что у самого левого при концевом обходе узла левая связь-нить пустая; аналогично пуста правая связь-нить у самого правого при концевом обходе узла, Таким образом, прошивка, деревьев — это еще один (нестсковый!) метод борьбы с рекурсией, остави|ийся с тех времен, когда она считалась чересчур расточительной.

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

Техника итераторов в этом случае очень удобна, в частности, можно ис|юльзовать те же алгоритмы, что и для обработки списка, поскольку функциональность итераторов совпадает. Среди прошитых деревьев важный класс составляют правопрошитые деревья, т. е. прошитые бинарные деревья, у которых используется только правая связь-нить, а в поле 1 содержится либо обычный указатель, либо пустой указатель. Поле Иад в таком случае не используется. На рисунке, приведешюм ниже, обы шые ссылки нарисованы сплошной линией, связи-нити штриховой линией с соответствующих сторон узлов.

Пустые связи- нити для самого левого и самого правого узлов изображены |птриховыми линиями, не ведущими ни к какому из узлов дерева. Они символизируют начало и конец обратного обхода линеаризованного прошивкой дерева. 297 'Гакой способ предсгаьчения дереьа удобен для арифметических выражений. Однако в силу того, что оба операнда арифметических операций «равноправны» и подчинены нс один другому, а операции, бинарно/ дерево для выражений не разворачивается на 45', поэтому все оратья изобра,жал>тся на одном уровне. П1>авопропн>тое дерево для выражения показано ниже.

Отметим, что связь-нить от мла/цпсг<> из братьев ведет к отпу. Правопрошитое дерево такого вида легко позволяет представлять и н-арньн операции в обычных деревьях. Еще раз подчеркнем, что на рисунке для всех узлов корни их правых поддеревьев изображены справа на одном уровне с узлами.

Прошивку деревьв» придумали Перлис и Торнтон в 1960 г. /1итателям, интересующимся алгоритмами обхода деревьев, рекомендуем монографию ~63~. 5.12 Графы Графом называют некоторое подмножество декартова произведения двух множеств. Часто берутся не разные множества, а одно и то же множество, т. е. граф рассматривается как подмножество декартова произведения множества па себя. В математическом смысле граф означает то же, что и отношение. На бумаге (топологически) граф изображается как множество точек (называемых вершинами), соединенных линиями (называемыми ребрами). Каждая пара вершин соединяется не более чем одним ребром.

Характеристики

Список файлов лекций