Д. Кнут - Искусство программирования том 1 (1119450), страница 89
Текст из файла (страница 89)
Если Р указывает на узел бинарного дерева, то Р« — адрес Рэ — адрес Р$ — адрес «Р — адрес ЗР— адрес 3Р— адрес узла-последователя ИОВЕ(Р) при обходе в прямом порядке; узла-последователя МОВЕ(Р) при обходе в симметричном порядке; узла-последователя ИОВЕ(Р) прн обходе в обратном порядке; узла-предшественника ИОВЕ(Р) при обходе в прямом порядке; узла-предшественника ИОВЕ(Р) при обходе в симметричном порядке; узна-предшественника МОВЕ(Р) при обходе в обратном порядке. (6) Если узел МОВЕ(Р) не имеет узлов-предшественников и узлов-последователей, то обычно используется обозначение ЕОС(Т), где Т вЂ” это внешний указатель на данное дерево.
Таким образом, получаем *(Р*) = («Р)« = Р, э(Ре) = (еР)э = Р и $(Р1) = (5Р)1 = Р. В качестве примера использования этих обозначений предположим, что 1МРО(Р) — это буква, изображенная в узле МОВЕ(Р) дерева (2). Тогда, если Р указывает на его корень, получим 1МРО(Р) = А, 1МРО(Р*) = В, 1МРО(рэ) = Е, 1МРО(йр) = В, 1МРООР) = С и Ри = «Р = 1.ОС(Т). Здесь у читателя может возникнуть чувство неуверенности в отношении правильности приведенных значений Р«, Ре и т. д. Однако по мере изучения дальнейшего материала они станут более понятными, в частности для этого полезно выполнить упр.
16, приведенное в конце раздела. Символ "Ек в обозначении "Рэ" представляет букву 8 в английском написании термина "симметричный порядок" (вушше(г!с огбег). Существует еще одицальтернативный вариант представления бинарных деревьев (2) в памяти компьютера, который отличается от предыдущего способа так же, как циклические списки отличаются от линейных однонаправленных списков. Обратите внимание на то, что в дереве (2) пустых связей содержится больше, чем всех остальных; и действительно, это верно для любого дерева, представленного с помощью обычного метода (см.
упр. 14). На самом деле вряд ли стоит из-за этого так неэкономно расходовать пространство памяти, Вместо этого можно было бы, например, хранить в каждом узле некий двухбитовый "признак" (араб) того, что узел содержит либо пустую, либо непустую связь (Л,1ИК (или й(.1ИК), либо обе пустые, либо обе непустые связи. В таком случае высвободившееся пространство в памяти, которое прежде использовалось для концевых связей, можно применять в других целях. Хитроумный способ экономного использования памяти предложен А. Дж. Перлисом и Ч.
Торнтоном, которые придумали метод прошипюго ((Ьгеааей) представления бинарного дерева. В этом методе концевые связи заменяются "нитями" (ФЬгеабэ) которые связаны с другими частями дерева для упрощения его обхода. Прошитое дерево, которое эквивалентно дереву (2), выглядит так: (7) Обычное представление ШИК(Р) = Л ы.1ик(Р) = () эА Л И1.1ИК(Р) = Л К~ТИК(Р) = Ц ф Л Прошитое представление (.ТАС(Р) = 1, ь1.1ИК(Р) = ЭР 1.ТАС(Р) = О, 1.1.1ИК(Р) = С БОТАС(Р) = 1, йй1ИК(Р) = Рэ АТАС(Р) = О, К1.1ИК(Р) = Ц Здесь пунктиром обозначены "нити", которые всегда направлены к более высокому узлу дерева. Каждмв узел теперь имеет две связи: одни узлы, например С, имеют две обычные связи с левым и правым поддеревьями, другие узлы, например Н,— две связи в виде нитей, а третьи в по одной связи каждого типа.
Особые нити, которые выходят из узлов 1) и,1, будут рассмотрены ниже. Они появляются в крайнем слева и крайнем справа узлах. Для представления прошитого бинарного дерева в памяти необходимо ввести обозначения, чтобы можно было отличить пунктирные и сплошные связи. Это может быть сделано, как предполагалось выше, с помощью двух дополнительных однобитовых полей в каждом узле, 1.ТАС и АТАС. Тогда прошитое представление можно определить, например, следующим образом. Произвольное и Произвольное А Рнс.
24. Общая ориентация левых и правых связей-нитей в прошитом бинарном дереве. Волнистые линии обозначают связи с другими частями дерева (нлн ведущие к ним нити). Согласно этому определению каждая новая связь-нить указывает непосредственно на узел-предшественник или узел-последователь конкретного узла в заданном симметричном порядке. На рнс. 24 показана общая ориентация связей-нитей в любом бинарном дереве. В некоторых алгоритмах гарантируется, что корень любого поддерева всегда располагается в ячейках памяти, которые находятся в памяти ниже других узлов этого поддерева.
В таком случае 1.ТАС (Р) будет равно 1 тогда и только тогда, когда 111МК(Р) < Р, поэтому поле 1.ТАС, как и поле КТАС, будет содержать избыточную информацию. Значительным преимуществом прошитых деревьев является то, что алгоритмы обхода для них существенно упрощаются. Например, с помощью приведенного ниже алгоритма можно вычислить Рь по заданному значению Р. Алгоритм 8 (Симметричный (центрированный) узел-последователь в прошитом бинарном дереве).
Если Р указывает на узел прошитого бинарного дерева, то данный алгоритм устанавливает Ц э- Рк Я1.(Ы.ХИК(Р) — это ннтв?1 Установить Ц +- К11МК(Р). Если КТАС(Р) = 1, прекра- тить выполнение алгоритма. 82.(Поиск слева.) Если СТАС(С) = О, установить С э- 11.1КК(Ц) и повторить этот шаг. В противном случае прекратить выполнение алгоритма. 1 ГЫМК(НЕАР) = Т, Н1.1МК(НЕАО) = НЕАР, БОТАС(НКАО) = О, НТАС(НЕАО) = О.
(Здесь НЕАО обозначает ЕОС(Т), т. е. адрес заголовка списка.) Пустое прошитое дерево удовлетворяет условиям ЕЫМК(НЕАР) = НЕАР, 1.ТАО(НЕАР) = 1. Дерево растет за счет вставки узлов слева от заголовка списка. (Эти начальные условия преимущественно продиктованы алгоритмом вычисления Ро, который рассматривается в упр. 17.) В соответствии с этими соглашениями прошитое представление бинарного дерева (1) для компьютера будет выглядеть так: Заголовок Обратите внимание на то, что для его выполнения не потребуется стек, который применялся в алгоритме Т. Действительно, с помощью обычного представления (2) невозможно найти РЭ столь.чсе эффективным путем, зная только адрес Р произвольно выбранного узла дерева. Поскольку в обычном представлении бинарного дерева нет направленных вверх связей, то нет и сведений о том, какие узлы расположены выше, если только не сохранять информацию о пути к данному узлу.
Стек в алгоритме Т используется как раз для хранения этой информации при отсутствии нитей. Алгоритм Б назван эффективным, хотя это свойство не всегда очевидно, поскольку шаг Б2 может выполняться достаточно много раз.. Может быть, вместо многократного повторения шага 52 для ускорения процесса следовало бы использовать стек, как в алгоритме Т? Для исследования этого вопроса выясним, сколько раз в среднем выполнялся шаг Б2, если Р указывает "произвольный" узел дерева, или, что то же самое, определим общее количество выполнений шага Б2, если алгоритм Ь повторно используется для обхода всего дерева. Выполняя этот анализ, полезно будет также познакомиться с программами, в которых реализованы алгоритмы 8 н Т.
Как обычно, при разработке алгоритмов следует учесть возможность их применения для пустых бинарных деревьев, и, если Т является указателем данного дерева, желательно, чтобы ЬОС(Т) о и ЕОС(Т) з были первы ни узлами в прямом и симметричном порядках соответственно. Для прошитых деревьев узел МОРЕ(ЕОС(Т)) удобно преобразовать в "заголовок списка" для дерева со следующими параметрами: После описания предварительных сведений можно приступать к созданию программ для компьютера М1Х, предназначенных для реализации алгоритмов Я и Т.
В приведенных ниже программах предполагается, что узлы бинарного дерева состоят иэ двух слов: В непрашитом дереве 1.ТАО и НТАО всегда будут равны и+", а концевые связи будут представлены нулем. В прошитом дереве знак и+и используется для меток, которые равны О, а знак "-" — для меток, которые равны 1. Обозначения ЕР1ИКТ и И.ТИКТ будут использоваться для полей ЕТАО-РР1ИК и НТАО-Н1.1ИК соответственно.
Два бита метки занимают знаковые ячейки слова в памяти компьютера М1Х, которые ни для чего другого все равно не используются, а потому они не занимают лишнего места в памяти. Аналогично в компьютере ММ1Х можно было бы ибесплатнои использовать младшие биты полей связи в качестве битов метки, поскольку указатель обычно принимает четные значения, а также потому что при адресации памяти в компьютере ММ1Х проще игнорировать именно младшие биты. В следующих двух программах выполняется обход бинарного дерева в симметричном (т. е, центрираванном) порядке с периодическими переходами к ячейке 'и'1Б1Т, в та время как индексный регистр 5 указывает на текуший узел. Программа Т. В этой реализации алгоритма Т стек находится в ячейках А + 1, А + 2, ..., А + МАХ; г16 является указателем стека и г15 =- Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
