Докажите, что Т может быть вставлено в дерево Г, если (i) Т имеет только один узел или (ii) оба дерева Т тлТ имеЛэт более одного узла и либо Т С 1{Т), либо Г С г{Т), или (/(Г) С 1(Т) и г(Г) С г(Т)). Справедливо ли обратное утверждение?

2.3.3. Другие представления деревьев

Кро-ме описанного в предыдущем разделе метода, основанного на указателях LLINK-RLINK (левый ребенок - правый брат (или сестра)), существует много других способов представления древовидных структур. Как обычно, наиболее подходящий способ в значительной мере зависит от типа операций, выполняемых над этими деревьями. В данном разделе рассматривается несколько методов представления деревьев, которые на практике доказали свою целесообразность.

Сначала рассмотрим методы последовательного распределения памяти. Как и в случае линейных списков, этот способ распределения наиболее удобен для компактного представления древовидной структуры, размер и форма которой во время выполнения программы не претерпевает значительных динамических изменений. Существует множество ситуаций, в которых для организации ссылок внутри программы необходимо использовать именно постоянные таблицы данных с древовидной структурой. А необходимая форма этих деревьев в памяти компьютера зависит от способа доступа к данным из этой таблицы.

Наиболее популярный тип последовательного представления деревьев (и лесов) соответствует устранению полей LLINK и использованию вместо них метода последовательной адресации. Рассмотрим, например, следующий лес. который уже упоминался в предыдущем разделе:

{AiB,CiK)),D{E{H),F{J),G)). (1)

Схематически его можно представить так:

(а) (д) (л)->(д

(в) (с) (е) Ф ig) и @->© (е)-Xf)-Xg) . (2)

к) @ О) @

При использовании последовательного представления в прямом порядке {preorder sequential representation) узлы располагаются в прямом порядке с полями INFO, RLINK и LTAG в каждом узле:

RLINK

INFO

LTAG

r~F=-1

A В С К D

I-*г

E Н F

Здесь непустые связи RLINK обозначены стрелками, а LTAG = 1 (для концевых узлов) - символом "J". Связи LLINK не нужны, поскольку они либо пусты, либо указывают на следющнй объект последовательности. Читателю будет полезно сравнить (1) с (3).

Это представление обладает сразу несколькими интересными свойствами. Во-первых, все поддеревья узла располагаются сразу за самим узлом, а потому все

поддеревья внутри исходного леса находятся в последовательных блоках. [Сравните это с представлением на основе "вложенных скобок" в (1) и на рис. 20, (Ь).] Во-вторых, обратите внимание на то, что стрелки связей RLINK на схеме (3) никогда не пересекаются. Это справедливо и в общем случае, так как в бинарном дереве все узлы, находящиеся между X и RLINK (X), при прямом порядке обхода располагаются в левом поддереве X, а потому из этой части дерева не выходят никакие стрелки. В-третьих, можно заметить, что поле LTAG, которое указывает, будет ли узел концевым, является лишним, так как символ "J" располагается только в конце леса и только перед каждой направленной вниз стрелкой.

Действительно, из этих замечаний следет, что даже.поле RLINK также почти излишне и на самом деле для представления такой структуры необходимы поля RTAG и LTAG. Следовательно, схему (3) можно получить на основе меньшего объема данных:

RTAG INFO LTAG

А В С К

При считывании представления (4) слева направо узлы с полями RTAG ф "]" соответствуют непустым значениям RLINK. Тогда для восстановления связей RLINK нужно каждый раз после прохождения узла с полем LTAG = "J" проводить связь к текущему узлу от ближайшего предшествующего узла с невосстановленной связью RLINK. (Например, после прохождения узла В с LTAG = "J" связь к текущему узлу С следует проводить от узла В. затем после прохождения узла К связь к текущему узлу D необходимо проводить от узла А (поскольку связь RLINK в узле В уже восстановлена) и т. д. -Прим. перев.) Следовательно, ячейки с невосстановленными, т. е. ненулевыми, значениями связей RLINK можно хранить в стеке. Таким образом, снова доказана теорема 2.3.1 А.

Тот факт, что поля RLINK и LTAG являются избыточными в представлении (3), не имеет большого значения, за исключением случая, когда нужно полностью вьшолнить последовательный обход всего дерева, поскольку для получения недостающей информации потребуются дополнительные вычисления. Значит, чаще всего нужны все данные представления (3). Однако очевидно, что при этом значительная часть памяти расходуется очень неэкономно, например в рассмотренном здесь частном примере леса больше половины полей RLINK равны А. Для более эффективного использования памяти можно прибегнуть к следующим двум распространенным способам.

1) В поле RLINK каждого узла указать адрес, следующий за всеми узлами поддерева данного узла. Это поле часто называется "SCOPE" (т. е. область действия), а не RLINK, поскольку оно обозначает правую границу "влияния" (на наследников) каждого узла. Теперь вместо схемы (3) получим другую схему, в которой стрелки также не пересекаются:

SCOPE INFO

ABCKDEHFJGi

Более того, LTAG(X) = "J" характеризуется условием SCOPE(X) = ХЧ-с, где с - количество слов в узле. Пример использования понятия SCOPE приводится в упр. 2.4 12.

2) Уменьшить размер каждого узла, удалив поле RLINK, и добавить особые "узлы связи" непосредственно перед узлами, которые прежде содержали непустые связи RLINK:

I I + I I-*1-* ,

INFO *A*BCKD*EH*FJG. (6)

LTAG J J J J

Здесь символ "*" обозначает такие особые узлы связи, в которых поля INFO каким-то образом характеризуют их, как связи, направления которых указаны стрелками. Если поля INFO и RLINK в схеме (3) занимают приблизительно одинаковый объем памяти, то переход к схеме (6), в общем, позволяет сэкономить место в памяти, так как количество узлов "*" всегда меньше количества других узлов (т. е. тех узлов, которые пе являются особыми узлами связи "*"). В некоторой степени представление (6) аналогично после товательности команд в одноадресном компьютере, подобном компьютеру MIX с узлами "*", которые соответствуют командам условного перехода.

Другой вид последовательного распределения, аналогичного (3), может быть получен за счет удаления полей RLINK. а не полей LLINK. В этом случае узлы леса могут быть перечислены в новом порядке, который назьшается фамильным порядком {family order), поскольку члены каждой "семьи" распопагаются рядом. Фамильный порядок для любого леса может быть получен рекурсивно так, как показано ниже.

Посетить корень первого дерева.

Совершить обход остальных деревьев (в фамильном порядке).

Совершить обход поддеревьев корня первого дерева (в факпшьном порядке).

(Сравните этот способ с определениями прямого и обратного порядков из предыдущего раздела. Фамильный порядок идентичен инверсивному обратному порядку обхода соответствующего бинарного дерева )

Последовательное представление фамильного порядка {family order sequential representation) деревьев (2) выглядит так:

LLINK INFO RTAG

INFO ADEFGJHBCK-

В этом случае поля RTAG служат для разделения се.мей. При фамильном порядке сначала перечисляются корни всех деревьев в лесу, а зате.м - отдельные семьи. Причем каждый раз выбор семей начинается с ближайшего перечисленного узла, семья которого еще не перечислялась. Из этого следует, что стрелки LLINK никогда не пересекаются, а другие свойства представления прямого порядка переносятся аналогичным образом.

Можно было бы не использовать фамильный порядок, а просто перечислить узлы слева направо, последовательно уровень за уровнем. Такой способ назьшается порядком уровней (level order) [см С. Salton, САСМ 5 (1962). 103-114]. Последовательное представление порядка уровней {level order sequential representation) для (2)