Машинное представление деревьев в памяти ЭВМ.

Деревья можно представлять с помощью связных списков и масси-

вов (или последовательных списков).

Чаще всего используется связное представление деревьев, т.к.

оно очень сильно напоминает логическое. Связное хранение состоит

в том, что задается связь от отца к сыновьям. В бинарном дереве

имеется два указателя, поэтому удобно узел представить в виде

структуры:

 

┌──────┬──────┬──────┐ где LPTR - указатель на левое поддерево,

│ LPTR │ DATA │ RPTR │ RPTR - указатель на правое поддерево,

└──────┴──────┴──────┘ DATA - содержит информацию, связанную

с вершиной.

Рассмотрим машинное представление бинарного дерева, изобра-

женного на рис. 6.20.

┌─┬───┬─┐

┌───┼ │ A │ ┼───┐

│ └─┴───┴─┘ │

(A) ┌─┬─┴─┬─┐ ┌─┬─┴─┬─┐

/ ┌─┼ │ b │ │ ┌────┼ │ c │ ┼───┐

(b) (c) │ └─┴───┴─┘ │ └─┴───┴─┘ │

/ / ┌─┬─┴─┬─┐ ┌─┬─┴─┬─┐ ┌─┬─┴─┬─┐

(d) (e) (g) │ │ d │ │ │ │ e │ ┼──┐ │ │ g │ │

└─┴───┴─┘ └─┴───┴─┘ │ └─┴───┴─┘

(f) ┌─┬─┴─┬─┐

│ │ f │ │

Рис. 6.20. Логическое └─┴───┴─┘

представление дерева Рис. 6.21. Машинное связное представление

дерева представленного на рис.6.20

Рассмотрим последовательное представление деревьев. Оно

удобно и эффективно в случае, если древовидная структура в тече-

ние времени своего существования не подвергается значительным из-

менениям, за счет включения вершин, удаления вершин и т.д.

Выбор метода последовательного представления деревьев опре-

деляется также набором тех операций, которые должны быть выполне-

ны над древовидными структурами. (Пример статистической древовид-

ной структуры - пирамидальный метод сортировки). Простейший метод

представления дерева в виде последовательной структуры заключает-

ся во введении вектора FATHER, задающего отбор для всех его вер-

шин. Этот метод можно использовать также для представления леса.

Недостаток метода - он не отображает упорядочения вершин дерева.

Если в предыдущем примере поменять местами вершины 9 и 10, после-

довательное представление останется тем же.

a) (1) б) (1)

/ │ │

(2) (3) (4) (2)─(3)───────(4)

/ / / │ │ │

(5) (6) (7)(9) (10) (5) (6)─(7) (9)─(10)

│

(8) (8)

Рис. 6.21. Диаграммы дерева: а) исходное

б) перестройка в бинарное

Последовательное представление дерева, логическая диаграмма

которого дана на рис. 6.21 , задается следующим образом:

i 1 2 3 4 5 6 7 8 9 10

FATHER [i] 0 1 1 1 2 3 3 7 4 4 ,

где ветви определяются как {(FATHER[i],i)}, i = 2,3,...,10.

Вершины 2,3,4 являются\\овьями вершины 1, вершина 5 - сы-

ном вершины 2, вершины 6,7 - сыновьями вершины 3, вершина 8 имеет

отца вершина 7 и вершины 9 и 10 - сыновья вершины 4.

Числовые поля данных используются здесь, чтобы упростить

представление дерева. Корневая вершина не имеет отца, поэтому

вместо отца для нее задается нулевое значение.

Общее правило: если T обозначает индекс корневой вершины де-

рева, то FATHER[T] = 0.

Другой метод последовательного представления деревьев заклю-

чается в использовании физической смежности элементов машинной

памяти вместо одного из полей LPTR или RPTR, например, способ

опускания полей, т.е. чтобы вершины появлялись в нисходящем по-

рядке. Дерево ( рис.6.21б), можно описать как:

 

┌──────────┐ указатель

RPTR ┌─────┐│ ┌──┐ │ ┌───┐

│ ­│ │ ­ ­ │ ­

DATA 1 2 5 3 6 7 8 4 9 10 информация

TAG 1 1 1 1 1 листья

 

Рис. 6.22. Последовательное представление дерева методом

опускания полей

где RPTR,DATA и TAG представляют векторы. В данном методе указа-

тель LPTR не требуется, т.к. если бы он не был пуст, то указывал

бы на вершину, стоящую непосредственно справа от данной. Вектор

TAG - бинарный вектор, в котором единицы отмечают концевые верши-

ны исходного дерева. При таком представлении имеются значительные

потери памяти, т.к. свыше половины указателей RPTR оказываются

пустыми. Эти пустые места можно использовать путем установки ука-

зателя RPTR каждой данной вершины на вершину, которая следует не-

посредственно за поддеревом, расположенном под ней. В таком

представлении поле RPTR переименовывается в RANGE:

┌──────────────────────────────────┐

│ ┌─────────────┐ │

│ ┌──────┐│ ┌──────┐│┌─────┐ │

RANGE │ │ ┌──┐││ ┌──┐│ ┌──┐│││ ┌──┐│┌>│

│ │ │ ­­│ │ ­│ │ ­­­│ │ ­­│ ­

DATA 1 2 5 3 6 7 8 4 9 10

 

Рис. 6.23. Последовательное представление дерева с

размещением вершин в возрастающем порядке

В этом случае поле TAG не требуется поскольку концевой узел

определяется условием RANGE(P) = P + 1.

Третий метод состоит в представлении дерева общего вида на

основе его восходящего обхода. Такое представление состоит из

двух векторов: один вектор описывает все вершины дерева в восхо-

дящей последовательности, а второй - задает полустепени исхода

этих вершин (см. рис.6.24). Восходящий метод представления удобен

для вычисления функцией, заданных на определенных вершинах дерева

( например, использование таких функций для генерации объектного

кода по обратной польской записи некоторого выражения ).

( + )

/

( ) ( / )

/ /

() ( b )( c ) ( d )

│

( a )

Рис. 6.24. Последовательное представление

дерева на основе восходящего обхода

В заключении приведем два важных понятия.

Подобие бинарных деревьев - два дерева подобны, если они

имеют одинаковую структуру ( форму ).

Эквивалентные бинарные деревья - два дерева эквивалентные,

если они подобны, и если соответствующие вершины у них содержат

одинаковую информацию.