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