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

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

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

Прошитые деревья - один из способов использования памяти, занимаемой в дереве пустыми указателями. Прошивка дерева позволяет выполнять b-обход дерева без использования рекурсии или стека, с помощью обычного цикла (как линейный список). Это значительно ускоряет процесс b-обхода деревьев с большим числом узлов.

В прошитом дереве конечные связи (которые в обычном дереве равны nil), указывают на предшественников и преемников узлов в b-обходе. То есть если в обычном дереве llink=nil, то в прошитом llink указывает на предшественника данного узла, а если в обычном дереве rlink=nil, то в прошитом rlink указывает на преемника данного узла в b-обходе. Например:

На этом рисунке прошитые связи (<нити>) обозначены пунктирными линиями. Значение самой левой и самой правой нити будет объяснено ниже.

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

type ptr = ^node;
node = record	
	info : char;	
	llink, rlink : ptr        
end;

type ptr = ^node;        
node = record	
	info : char;	
	ltag, rtag : boolean;	
	llink, rlink : ptr        
end;

Значения связей в прошитом дереве приведены в следующей таблице:

Для того, чтобы значения самой левой и самой правой нити были определены, вводится головной узел HEAD. Дерево из приведенного выше примера в прошитом виде будет представлено в памяти следующим образом (для наглядности обозначим true через '+', false через '-'):

А пустое прошитое дерево выглядит следующим образом:

Алгоритм b-обхода прошитого дерева

Пусть HEAD - указатель на головной узел прошитого дерева, p - указатель на текущий узел. Тогда алгоритм b-обхода (ЛКП) прошитого дерева можно сформулировать следующим образом:

1. Переходим к корню дерева ( p := HEAD^.llink ).
2. До тех пор, пока p^.ltag равен true, повторять: p := p^.llink (то есть доходим по левой ветви до самого левого узла).
3. Обрабатываем узел p (например, печатаем p^.info).
4. Если p^.rtag равен false, то p := p^.rlink и переход к п. 3 (переход к преемнику). Иначе p:= p^.rlink и переход к п. 2.

Алгоритм заканчивает работу когда p станет равным HEAD. Для ПКЛ-обхода следует везде, кроме пункта 1, поменять местами llink и rlink, ltag и rtag.

Алгоритм прошивки дерева

1. Строится обычное (непрошитое) дерево любым из способов. При этом поля ltag и rtag создаваемых узлов дерева остаются неопределенными, а llink и rlink соответственно указывают на левое или правое поддерево либо равны nil. На корень построенного дерева указывает указатель root.
2. Создается головной узел, llink которого указывает на корень дерева, а rlink на сам головной узел:
   

   
   new(HEAD);
   HEAD^.llink := root;
   HEAD^.rlink := HEAD;
   

   (информационное поле и поля тэгов головного узла можно оставить неопределенными).
3. Прошивка левых связей.

   Вводится дополнительный глобальный указатель pold (указатель на предшествующий текущему узел) с начальным значением HEAD ( pold := HEAD ). Указатель на текущий узел p устанавливаем на корень дерева ( p := HEAD^.llink ).

   Выполняется ЛКП-обход с помощью любого из алгоритмов. При обработке каждого узела проверяем: если p^.llink!=nil, то p^.ltag:=true; иначе p^.ltag:=false; p^.llink:=pold; (указатель на предшественника). В любом случае выполняем pold:=p.
   Например, при использовании рекурсии, фрагмент процедуры прошивки левых связей leftsew будет выглядеть так:

   leftsew( p^.llink );
   if p^.llink <> nil then p^.ltag := true
   else begin
   p^.ltag := false;
   p^.llink := pold;
   end;
   pold := p;
   leftsew( p^.rlink );
   

4. Прошивка правых связей.

   
   pold := HEAD;
   p := HEAD^.llink;
   	

   Затем выполняется процедура rightsew, которая подобна процедуре прошивки левых связей, но использует ПКЛ-обход. Для этого в процедуре leftsew надо везде поменять местами местами llink и rlink, ltag и rtag. Однако поскольку левые связи уже прошиты, то при рекурсивном вызове процедуры rightsew для левых поддеревьев никогда не получим указатель, равный nil, и рекурсия будет бесконечной. Чтобы этого избежать, следует выполнять рекурсивный вызов для левого поддерева только в том случае, если это поддерево действительно существует:

   
   if p^.ltag rightsew( p^.llink );
   

Замечание 1. Если дерево необходимо обрабатывать только в порядке ЛКП, то достаточно прошить только правые связи. Если только в порядке ПКЛ - то только левые связи.

Замечание 2. При изменениях в дереве (добавлении или удалении узлов) его нужно прошивать заново. Поэтому прошитые деревья целесообразно использовать в тех задачах, где изменения в деревьях происходят редко, а b-обход выполняется часто.

Литература

1. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. - М.: Мир, 1989.
2. Кнут Д. Искусство программирования для ЭВМ: Т.1: Основные алгоритмы: Пер. с англ. - М.: Мир, 1976.

Copyright c2000-2002 Михаил Марковский
Перевод в HTML Александр Бессонов