Прошитые бинарные деревья

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

Эффективность прохождения дерева рекурсивными и нерекурсивными алгоритмами может быть увеличена, если использовать пустые указатели на отсутствующие поддеревья для хранения в них адресов узлов преемников, которые надо посетить при заданном порядке прохождения бинарного дерева. Такой указатель называется нитью. Его следует отличать от указателей в дереве, которые используются с левым и правым поддеревьями. Операция, заменяющая пустые указатели на нити, называется прошивка. Она может выполняться по-разному. Если нити заменяют пустые указатели в узлах с пустыми правыми поддеревьями, при просмотре в симметричном порядке, то бинарное дерево называется симметрично прошитым справа. Похожим образом может быть определено бинарное дерево, симметрично прошитое слева: дерево, в котором каждый пустой левый указатель изменен так, что он содержит нить – связь к предшественнику данного узла при просмотре в симметричном порядке. Симметрично прошитое бинарное дерево – это то, которое симметрично прошито слева и справа. Однако левая прошивочная нить не дает тех преимуществ, что правая прошивочная нить. На рис. 6.1 показано дерево, симметрично прошитое справа. На нем пунктирными линиями обозначены прошивочные нити.

Рис. 6.1 – Симметрично прошитое справа бинарное дерево

Также используются бинарные деревья, прямо прошитые справа и слева. В них пустые правые и левые указатели узлов заменены соответственно на их преемников и предшественников при прямом порядке просмотра. Прошитые деревья эффективно проходятся без использования стека.

Поскольку нужно каким-то образом отличать обычную связь от прошивочной нити, каждому узлу добавляется два однобитовых (логических) поля тэга: ltag и rtag. Если значение тэга true, соответствующее поле связи является обычной связью, в случае значения false – прошивочной нитью.

В этой связи узел обычного бинарного дерева представляется структурой

Type ptr = ^node;

node = record

info: integer; {Информационное поле}

left, right: pt; {Указатели на левое и правое поддеревья}

end;

Узел прошитого бинарного дерева имеет иную структуру

Type ptr = ^node;

node = record

info: integer; {Информационное поле}

ltag, rtag: boolean; {Тэги прошивочных нитей}

left, right: pt; {Указатели на левое и правое поддеревья}

end;

Логические поля в прошитом дереве могут принимать следующие значения.

1. ltag=true, следовательно, left представляет собой обычную связь.

2. ltag=false, следовательно, left указывает на узел-предшественник.

3. rtag=true, следовательно, right представляет собой обычную связь.

4. rtag=false, следовательно, right указывает на узел-преемник.

Рассмотрим вставку новой вершины слева от заданной в симметрично прошитое бинарное дерево (рис. 6.2). На рис. 6.3 показано результирующее дерево.

Рис. 6.2 – Исходное симметрично прошитое дерево

Рис. 5 – Прошитое дерево после вставки в него нового элемента

Здесь требовалось вставить вершину I вкачестве левого поддерева вершины А, если А не имеет левого поддерева. В противном случае новая вершина вставляется между А и ее левым сыном.

Для удобства создания и обхода дерева используется дополнительная головная вершина Head, которая служит при симметричном обходе предшественником его первой вершины и приемником всех его концевых вершин.

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