Фиксированное дерево

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

Таблица MainTable

Название поля Тип поля Комментарий

ID	Autoincrement	Первичный ключ
Lev	Integer	Уровень текущего узла
Parent1	Integer	Ссылка на родителя 1-го уровня (корень)
Parent2	Integer	Ссылка на родителя 2-го уровня
Parent3	Integer	Ссылка на родителя 3-го уровня
Parent4	Integer	Ссылка на родителя 4-го уровня
Parent5	Integer	Ссылка на родителя 5-го уровня
Name	Char	Название узла

Поле Lev может принимать значения от 1 (корень дерева) до 5 (узел максимально возможной глубины). Значение поля ParentN для любого N равно:

значению первичного ключа предка уровня N (при N < Lev);
значению первичного ключа текущего узла (при N = Lev);
0 (при N > Lev).

{GetLevel -- вспомогательная функция, которая возвращает уровень узла Node. Выделена для упрощения реализации основных процедур.} function GetLevel(Node : Integer) : Integer; begin with OpenQuery(Format('SELECT Lev FROM MainTable WHERE ID='+IntToStr(Node))) do Result:=Fields[0].AsInteger; end; procedure OutTree(Root : Integer); var S : String; Q : TQuery; L : Integer; begin L:=GetLevel(Root); S:='SELECT * FROM MainTable WHERE Parent%d=%d '+ 'ORDER BY Parent1,Parent2,Parent3,Parent4,Parent5'; Q:=OpenQuery(Format(S,[L,Root])); while NOT Q.Eof do begin OutNode(Q.FieldByName('ID').AsInteger, Q.FieldByName('Lev').AsInteger-L, Q.FieldByName('Name').AsString); Q.Next; end; end; procedure AddNode(Parent : Integer; const Name : String); var S : String; L : Integer; begin L:=GetLevel(Parent); if L >= 5 then Exit; // Следующий запрос не будет работать в Local SQL. S:='INSERT INTO MainTable (Lev,Parent1,Parent2,Parent3,Parent4,Parent5,Name) '+ 'SELECT Lev+1,Parent1,Parent2,Parent3,Parent4,Parent5,"%s" FROM MainTable '+; 'WHERE ID=%d'; ExecQuery(Format(S,[Name,Parent])); S:='UPDATE MainTable SET Parent%d=ID WHERE ID=%d'; ExecQuery(Format(S,[L+1,LastInsertID])); end; procedure DeleteNode(Node : Integer); var S : String; begin S:='DELETE FROM MainTable WHERE Parent%d=%d'; ExecQuery(Format(S,[GetLevel(Node),Node])); end; function NodeInSubtree(Node,Parent : Integer) : Boolean; var S : String; Q : TQuery; begin S:='SELECT Parent%d FROM MainTable WHERE ID=%d'; Q:=OpenQuery(Format(S,[GetLevel(Parent),Node])); Result:=(Q.Fields[0].AsInteger = Parent); end; procedure SetParent(Node,Parent : Integer); var S : String; Q : TQuery; NodeL,ParentL,dL,i : Integer; function DecLevel : String; var j : Integer; begin Result:=''; for j:=NodeL to 5 do Result:=Result+Format('Parent%d=Parent%d,',[j-dL,j]); for j:=5-dL+1 to 5 do Result:=Result+Format('Parent%d=0,',[j]); Result:=Result+Format('Lev=Lev-%d,',[dL]); end; function IncLevel : String; var DelS : String; j : Integer; begin Result:=''; DelS:='DELETE FROM MainTable WHERE (Parent%d=%d) AND (Lev>%d)'; ExecQuery(Format(DelS,[NodeL,Node,5+dL])); for j:=5 downto (NodeL-dL) do Result:=Result+Format('Parent%d=Parent%d,',[j,j+dL]); Result:=Result+Format('Lev=Lev+%d,',[-dL]); end; begin NodeL:=GetLevel(Node); Q:=OpenQuery(Format('SELECT * FROM MainTable WHERE ID=%d',[Parent])); ParentL:=Q.FieldByName('Lev').AsInteger; dL:=NodeL-ParentL-1; S:='UPDATE MainTable SET '; if dL <> 0 then begin if dL > 0 then S:=S+DecLevel else S:=S+IncLevel; end; for i:=1 to ParentL do S:=S+Format('Parent%d=%d,',[i,Q.Fields[i+1].AsInteger]); S[Length(S)]:=#32; ExecQuery(Format(S+'WHERE Parent%d=%d',[NodeL,Node])); end;

Как видно из приведенных примеров, в реализации всех операций удалось уйти от рекурсии. Количество запросов не зависит ни от количества узлов в дереве, ни от его глубины. Да и сама реализация стала несколько проще за исключением процедуры SetParent. На самом деле в ней не так все страшно, как кажется. Просто я попытался в одну процедуру запихнуть обработку нескольких различных ситуаций, которые, по уму, должны обрабатываться самостоятельно. На всякий случай (если кому-то сложно разбирать мои паскалевские каракули) хочу привести примеры запросов, которые реализуют эту операцию для различных ситуаций (запросы не сработают на Local SQL).

Ситуация 1. При изменении родителя происходит уменьшение уровня узла. Пусть мы узлу Node уровня 3 назначаем родителем узел Parent уровня 1. В результате выполнения операции уровень всех узлов поддерева Node уменьшится на 1. UPDATE MainTable AS T1,MainTable AS T2 SET T1.Lev=T1.Lev-1,T1.Parent1=T2.Parent1,T1.Parent2=T1.Parent3, T1.Parent3=T1.Parent4,T1.Parent4=T1.Parent5,T1.Parent5=0 WHERE (T1.Parent3=Node) AND (T2.ID=Parent);

Ситуация 2. При изменении родителя происходит увеличение уровня узла. Пусть мы узлу Node уровня 2 назначаем родителем узел Parent уровня 2. В результате выполнения операции уровень всех узлов поддерева Node увеличится на 1. Если в поддереве узла Node имеются узлы уровня 5, то они должны быть предварительно удалены, так как выйдут за пределы допустимой глубины дерева. DELETE FROM MainTable WHERE (Parent2=Node) AND (Lev>=5); UPDATE MainTable AS T1,MainTable AS T2 SET T1.Parent5=T1.Parent4,T1.Parent4=T1.Parent3,T1.Parent3=T1.Parent2, T1.Parent2=T2.Parent2,T1.Parent1=T2.Parent1,T1.Lev=T1.Lev+1 WHERE (T1.Parent2=Node) AND (T2.ID=Parent);

Ситуация 3. При изменении родителя не происходит изменение уровня узла. Пусть мы узлу Node уровня 3 назначаем родителем узел Parent уровня 2. В результате выполнения операции уровень всех узлов поддерева Node не меняется. UPDATE MainTable AS T1,MainTable AS T2 SET T1.Parent1=T2.Parent1,T1.Parent2=T2.Parent2 WHERE (T1.Parent2=Node) AND (T2.ID=Parent);

Кстати, фиксированное дерево -- единственный вариант представления дерева, для которого мне удалось в полном объеме решить вставшую изначально проблему: вывести все узлы поддерева в нужном порядке одним запросом.

Содержание раздела