Welcome to
aleprojects.com

Red-Black Tree. TAleRBTreeNode Delphi Class.

There has been written a lot about red-black trees (RB-trees), so only few words will be said. Red-black tree is a binary search tree maintaining itself in approximately balanced state after inserting or deleting nodes. Balanced state provides search time proportional to tree height that is equal to log2N, where N is number of tree nodes. The same time provides ordered array with bisection method. However, the most important is the fact that time required for inserting or deleting nodes in red black tree is also proportional to log2N unlike the ordered array where time is proportional to N (due to shifts of the array elements).

Links
1) About red-black trees (wikipedia)
2) Visualization of red-black tree

Bibliography
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein - Introduction to Algorithms, Second Edition. The MIT Press.

Below is a working Delphi implementation of the red-black tree. Each tree node is an instance of the TAleRBTreeNode class descendant. TAleRBTreeNode class encapsulates basic properties and methods for searching, inserting, deleting and balancing and is designed to be inherited and extended. Descendant classes should provide storage and access to key and data.

Download

Descendant class example

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;

Descendant class should override at least two virtual methods - CompareKey and Key. Optionally Destroy (for releasing memory used for key and data).

Virtual method CompareKey compares keys and returns integer values -1; 0; 1 (key passed in parameter is less than key of instance; keys are equal; key passed in parameter is greater than key of instance). Is called inside methods of ancestor class TAleRBTreeNode on insertion, deleting and searching.

Virtual method Key returns pointer to the key value. Method CompareKey already "knows" how to work with this pointer. Method Key is not used for anything else.

Methods implementation

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

Now this class can be used as red-black tree although it contains no data.

...
var Tree:TAleRBTreeNodeWithTextKey;
...
//suppose, we have TForm with editbox Edit1 and buttons Button1, Button2, Button3


//insert in the rb-tree
procedure TForm1.Button1Click(Sender: TObject);
var NewNode:TAleRBTreeNodeWithTextKey;
    OldNode:TAleRBTreeNode;
begin
//create new node and set key value
NewNode:=TAleRBTreeNodeWithTextKey.Create;
NewNode.TextKey:=StrNew(PChar(Edit1.Text));
//insert node in the rb-tree
if Tree<>nil then
 begin
    Tree:=Tree.InsertNode(NewNode,OldNode) as TAleRBTreeNodeWithTextKey;
    if OldNode<>nil then OldNode.Free;
 end else Tree:=NewNode;
end;


//find node in the rb-tree
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;

//find result
//Node=nil           - nothing is found since there is no tree (rem.: method FindKey never returns nil)
//Node<>nil & Res=0  - keys match exactly, Node is found element
//Node<>nil & Res=1  - key is not found, Node is nearest by key value element, key of element Node is less
//Node<>nil & Res=-1 - key is not found, Node is nearest by key value element, key of element Node is greater
// no more cases
end;


//delete node from the rb-tree
procedure TForm1.Button3Click(Sender: TObject);
var Node:TAleRBTreeNodeWithTextKey;
    Res:Longint; 
begin
//find node to be removed
if Tree=nil then Res:=-1 else Node:=Tree.FindKey(PChar(Edit1.Text),Res) as TAleRBTreeNodeWithTextKey;

if Res=0 then //node is found
 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;

Comments

Insertion

Method InsertNode inserts a new node in the red-black tree, rebalances it and returns new root node. Assignment of the new root node to the Tree variable is neccessary because the tree was rebalanced, so the old root node might be moved to another position and, secondly, when we insert a new node with existing key, the replaced node may turned out to be a root one.
Variable OldNode (var parameter of function) contains replaced node, otherwise it is nil.

Removing

Method DeleteNode deletes node from the red-black tree, rebalances it and also returns new root node because of the reasons indicated above. After deleting of the last node, DeleteNode returns nil. DeleteNode doesn't free instance Node and release memory. After calling DeleteNode variable Node still keeps the removed node. This instance is to be freed manually (Node.Free).

Methods InsertNode, DeleteNode and FindKey returns value of type TAleRBTreeNode. That's why operator as is used.