Welcome to
aleprojects.com

RB-дерево. Класс TAleRBTreeNode.

О том, что такое красно-черное дерево (RB-tree, Red-black tree) написано много, поэтому о нем коротко. RB-дерево - один из вариантов двоичных деревьев, поддерживающих себя в приблизительно сбалансированном состоянии при операциях добавления и удаления элементов. Сбалансированность дерева обеспечивает время поиска пропорциональное высоте дерева, равной log2N, где N количество элементов дерева. Такое же время поиска обеспечивает упорядоченный массив при поиске методом деления пополам. Однако, самое главное - это то, что время операций добавления и удаления элементов RB-дерева также пропорционально log2N в отличие от упорядоченного массива, где время этих операций пропорционально N (сдвиги элементов массива).

Ссылки по теме
1) подробно о красно-черных деревьях (wikipedia)
2) визуализация работы красно-черного дерева

Литература по теме
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein - Introduction to Algorithms, Second Edition. The MIT Press.

Ниже представлена работающая реализация RB-дерева на Delphi. Каждый узел дерева является экземпляром класса потомка TAleRBTreeNode. Класс TAleRBTreeNode содержит в себе основные свойства и методы для поиска, добавления, удаления и балансировки и предназначен для наследования и расширения. В первую очередь это касается хранения ключа и данных. В классе TAleRBTreeNode нет ключа и данных, так как это специфично для каждой задачи.

Скачать

Пример класса-потомка

TAleRBTreeNodeWithTextKey = class(TAleRBTreeNode)
private
lpcKey: PChar;

procedure SetTextKey(NewKey: PChar);

protected
function CompareKey(lpKey: Pointer):Longint;override;

public
property TextKey:PChar read lpcKey write SetTextKey;
destructor Destroy;override;
function Key:Pointer;override;

end;

При создании класса-потомка необходимо переопределить по крайней мере два виртуальных метода CompareKey и Key. Опционально - Destroy (для корректного освобождения памяти под ключ и данные). А также добавить методы и свойства для доступа к данным и иного функционала.

Виртуальный метод CompareKey должен уметь сравнивать между собой ключи и возвращать значения -1; 0; 1 (ключ, переданный в качестве параметра, меньше ключа экземпляра класса; равен; больше). Вызывается внутри методов базового класса TAleRBTreeNode, реализующих поиск, добавление и удаление.

Виртуальный метод Key должен вернуть указатель на ключ. Как работать с этим указателем метод CompareKey уже "знает". Больше ни для чего другого метод Key внутри класса TAleRBTreeNode не используется.

Реализация методов

procedure TAleRBTreeNodeWithTextKey.SetTextKey;
begin
if lpcKey <> nil then StrDispose(lpcKey);
lpcKey := StrNew(NewKey);
end; //SetTextKey 

function TAleRBTreeNodeWithTextKey.CompareKey;
begin
CompareKey := StrIComp(lpKey, lpcKey);
end; //CompareKey 

destructor TAleRBTreeNodeWithTextKey.Destroy;
begin
if lpcKey <> nil then StrDispose(lpcKey);
inherited Destroy;
end; //Destroy

function TAleRBTreeNodeWithTextKey.Key;
begin
Key := lpcKey;
end; //Key 

Теперь с этим классом можно работать как с деревом, хотя он и не содержит данных.

...
var Tree: TAleRBTreeNodeWithTextKey;
...
//предположим, что есть форма TForm с полем Edit1 и кнопками Button1, Button2, Button3


//добавить в дерево
procedure TForm1.Button1Click(Sender: TObject);
var NewNode: TAleRBTreeNodeWithTextKey;
    OldNode: TAleRBTreeNode;
begin
//создать новый элемент и установить значение ключа
NewNode :=T AleRBTreeNodeWithTextKey.Create;
NewNode.TextKey := StrNew(PChar(Edit1.Text));
//добавление элемента в дерево
if Tree <> nil then
 begin
   Tree:=Tree.InsertNode(NewNode, OldNode) as TAleRBTreeNodeWithTextKey;
   if OldNode <> nil then OldNode.Free;
 end else Tree := NewNode;
end;


//найти элемент в дереве
procedure TForm1.Button2Click(Sender: TObject);
var Node: TAleRBTreeNodeWithTextKey;
    Res: Longint; 
begin
if Tree = nil then Node := nil else Node := Tree.FindKey(PChar(Edit1.Text), Res) as TAleRBTreeNodeWithTextKey;

//результат выполнения
//Node=nil           - точно ничего не найдено, т.к. дерева нет (прим.: метод FindKey никогда не возвращает nil)
//Node<>nil & Res=0  - точное совпадение ключа, Node - это найденный элемент
//Node<>nil & Res=1  - ключ не найден, Node ближайший по значению ключа элемент, ключ элемента Node меньше искомого ключа
//Node<>nil & Res=-1 - ключ не найден, Node ближайший по значению ключа элемент, ключ элемента Node больше искомого ключа
// иных вариантов нет
end;


//удалить элемент из дерева
procedure TForm1.Button3Click(Sender: TObject);
var Node: TAleRBTreeNodeWithTextKey;
    Res: Longint; 
begin
//сначала найти удаляемый элемент
if Tree = nil then Res := -1 else Node := Tree.FindKey(PChar(Edit1.Text), Res) as TAleRBTreeNodeWithTextKey;

if Res = 0 then //элемент найден
 begin
   Tree := Tree.DeleteNode(Node) as TAleRBTreeNodeWithTextKey;
   Node.Free;
 end;
end;


procedure TForm1.FormCreate(Sender: TObject);
begin
Tree := nil;
end;


procedure TForm1.FormDestroy(Sender: TObject);
begin
Tree.Free;
end;

Комментарии к коду

Добавление

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

Удаление

Метод DeleteNode исключает элемент из дерева, осуществляет перебалансировку дерева и возвращает указатель на корневой элемент, вершину дерева. Присваивание необходимо по тем же причинам - перебалансировка и то, что удаляемый элемент может быть корневым. После удаления последнего элемента из дерева метод DeleteNode возвращает nil. Исключение элемента из дерева не подразумевает уничтожение элемента и освобождение памяти. Это необходимо сделать вручную. После вызова DeleteNode переменная Node по-прежнему хранит указатель на исключенный из дерева элемент.

Методы InsertNode, DeleteNode и FindKey возвращают значение типа TAleRBTreeNode. Чтобы было возможно присвоение родителя потомку, используется оператор as.