AOP_Tom1 (1021736), страница 99
Текст из файла (страница 99)
Это справедливо и в общем случае, так как в бинарном дереве все узлы, находящиеся между Х и КЕ1йК(Х), при прямом порядке обхода располагаются в левом поддереве Х, а потому из этой части дерева не выходят никакие стрелки. В-третьих, можно заметить, что поле БОТАС, которое указывает, будет ли узел концевым, является лишним, так как символ ")" располагается только в конце леса и только перед каждой направленной вниз стрелкой. Действительно, из этих замечаний следует, что даже. поле КЕ1МК также почти излишне и на самом деле для представления такой структуры необходимы поля АТАС и БОТАС. Следовательно, схему (3) можно получить на основе меньшего объема данных: 1ИРО А В С К 1) Е Й Р' ,) С (4) БОТАС ! ! ! ! ! При считывании представления (4) слева направо узлы с полями АТАС ф ")" соответствуют непустым значениям Ы.1МК.
Тогда для восстановления связей КЕ1ИК нужно каждый раз после прохождения узла с полем БОТАС = ")" проводить связь к текущему узлу от ближайшего предшествующего узла с невосстаиовленной связью КЕ1ИК. (Например, после прохождения узла В с БОТАС = ")" связь к текущему узлу С следует проводить от узла В. затем после прохождения узла К связь к текущему узлу П необходимо проводить от узла А (поскольку связь Ы.1МК в узле В уже восстановлена) и т, д, — Прим.
нерее.) Следовательно, ячейки с невосстаиовленными, т. е. ненулевыми, значениями связей ЕЕ1ИК можно хранить в стеке. Таким образом, снова доказана теорема 2.3.1А. Тот факт, что поля ЕЕ1ЯК и ЕТАС являются избыточными в представлении (3), не имеет большого значения, за исключением случая, когда нужно полностью выполнить последовательный обход всего дерева, поскольку для получения недостающей информации потребуются дополнительные вычисления.
Значит, чаще всего нужны все данные представления (3). Однако очевидно, что при этом значительная часть памяти расходуется очень неэкономно, например в рассмотренном здесь частном примере леса больше половины полей КЬ1пК равны Л. Для более эффективного использования памяти можно прибегнуть к следующим двум распространенным способам.
1) В поле КЕ1КК каждого узла указать адрес., следующий за всеми узлами поддерева данного узла. Это поле часто называется "ЕСОРЕ" (т. е. область действия), а не Ы.1КК, поскольку оно обозначает правую границу "влияния" (на наследников) каждого узла. Теперь вместо схемы (3) получим другую схему, в которой стрелки также ие пересекаются: нсоп (5) 1МРОАВСКРЕНГУС Более того, 1.ТАС(Х) = ")" характеризуется условием ЯСОРЕ(Х) = Х+ с, где с — количество слов в узле. Пример использования понятия ЯСОРЕ приводится в упр. 2.4 12. 2) Уменьшить размер каждого узла, удалив поле КЮ1МК, и добавить особые "узлы связи' непосредственно перед узлами, которые прежде содержали непустые связи КО1МК: 1нн ) В с )) л л я г 1 а. )6) 1.ТАС Здесь символ "*" обозначает такие особые узлы связи, в которых поля 1МРО какимто образом характеризуют их, как связи, направления которых указаны стрелками, Если поля 1МгО и Н11МК в схеме (3) занимают приблизительно одинаковый объем памяти, то переход к схеме (6), в общем, позволяет сэкономить место в памяти, так как количество узлов "*" всегда меньше количества других узлов (т.
е. тех узлов, которые пе являются особыми узлами связи "*"). В некоторой степени представление (6) аналогично последовательности команд в одноадресном компьютере, подобном компьютеру И1Х с узлами "*", которые соответствуют командам условного перехода. Другой вид последовательного распределения, аналогичного (3), может быть получен за счет удаления полей КО1МК. а не полей ОО1МК.
В этом случае узлы леса могут быть перечислены в новом порядке, который называется фамильным порядком (7ат)!у вгдег), поскольку члены каждой 'семьи" располагаются рядом. Фамильный порядок для любого леса может быть получен рекурсивно так, как показано ниже. Посетить корень первого дерева. Совершить обход остальных деревьев (в фамильном порядке).
Совершить обход поддеревьев корня первого дерева (в фамильном порядке). (Сравните этот способ с определениями прямо~о и обратного порядков из предыдущего раздела. Фамильный порядок идентичен инверсивному обратному порядку обхода соответствующего бинарного дерева ) Последовательное представление фамильного порядка (уат)!у вп!ег ге)7иеппа! гергегепгайап) деревьев (2) выглядит так: 1.1.1МК 1МРО НТАС А )~~Е Р' а д и В С К' (7) В этом случае поля НТАС служат для разделения семей. При фамильном порядке сначала перечисляются корин всех деревьев в лесу, а затем — отдельные семьи.
Причем каждый раз выбор семей начинается с ближайшего перечисленного узла, семья которого еще не перечислялась. Из этого следует, что стрелки 11.1МК никогда не пересекаются, а другие свойства представления прямого порядка переяосятся аналогичным образом. Можно было бы не использовать фамильный порядок, а просто перечислить узлы слева направо, последовательно уровень за уровнем. Такой способ называется порядком уровней (1езе! огдег) [см С. район, САСАА 5 (1962). 103-114).
Последовав)вльное т)редставление порядка уровней (!све! огдег ведиеппа! гергегеп!а!)оп) для (2) выглядит так; 001НК 1НРО А Р„В С Е Р' 6 К Н д Оно подобно представлению (7), но семьи выбраны в порядке "первым вошел — первым вышел", а не в порядке "последним вошел — первым вышел". Представления деревьев в виде (7) или (8) могут рассматриваться как естественный аналог для деревьев последовательного представления линейных списков. Читатель легко сообразит, как можно создать алгоритм обхода и анализа деревьев, которые показаны выше, в последовательном представлении, поскольку информация из полей ЕЬ1НК и ЕЬ1НК позволяет рассматривать эти структуры как полностью связанную древовидную структуру.
Еще один метод, который называется обраглнмм порядком со сшепенлми (ровГогдег ил1Ь дедгеев)„несколько отличается от описанных выше методов. В случае его непользования узлы перечисляются в обратном порядке и вместо связей для каждою узла уквзываетгя его степень: ОЕОКЕЕ О О 1 2 О 1НРО В К С А Н Доказательство достаточности этих сведений структуры приводится в упр 2.3.2 — 10. Такой "снизу вверх" (Ьоггош-пр) значений функций, показано в следующем алгоритме. 1 О 1 О 3 Е,7 г'СР (9) для характеристики древовидной порядок очень удобен для оценки заданных в узлах дерева так, как Алгоритм Р (Оценка функции, локально определенной в узлах дерева). Пусть |— такая функция узлов дерева,что значение 1 в узле х зависит только от х и значений 7 для детей узлах.
Данный алгоритм позволяет с помощью вспомогательного стека оценить у в каждом узле непустого леса. Е1. [Инициализация,] Установить стек пустым, а Р пусть указывает на первый узел леса в обратном порядке. Е2.[Оценка 1.] Установить д < — ОЕОЕЕЕ(Р). (При первой попытке выполнения этого шага значение д будет равно нулю.
Вообще, по достижении данного шага верхними злементамн д стека по направлению сверху вниз будут элементы 1(ха),, т(х~), где хы ..., хв — дети узла НООЕ(Р) слева направо.) Оценить 1(НООЕ(Р)), используя значения стека 1(хв),, 1(х~). ГЗ.
[Обновление стека.) Удалить из стека верхние д элементов, а затем разместить значение 1[НООЕ(Р)) в верхней части стека. Е4.[Продвижение.] Если Р— последний узел в обратном порядке обхода, то прекратить выполнение алгоритма. (Тогда стек будет содержать следующие элементы по направлению сверху вниз: 7[корень(Т )), ..., 1[корень(Т~)), где Т,, ..., Т вЂ дерев данного леса.) В противном случае установить Р равным его последователю в обратном порядке [в представлении (9) это значит, что просто Р +- Р + с ) и вернуться к шагу Е2. $ Справедливость алгоритма Е доказывается методом индукции по размеру обрабатываемого дерева (см.
упр. 16). Этот алгоритм удивительно похож на процедуру дифференцирования из яредыдущего раздела (алгоритм 2.3.2Р), которая вычисляет функцию почти такого же типа (см. упр. 3). Та же идея используется во многих программах-интерпретаторах в связи с оценкой арифметических выражений, заданных в постфиксной системе обозначений. Обсуждение этого вопроса будет продолжено в главе 8 (см. также упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
