Welcome to
aleprojects.com

Red-Black Tree. Properties and methods of the TAleRBTreeNode class.

Class TAleRBTreeNode defined as

TAleRBTreeNode = class(TObject)
private
CLeft,CRight,CParent:TAleRBTreeNode;
NodeColor:TNodeColor;
dwCount:Longint;

function    GetRoot:TAleRBTreeNode;
function    GetMostLeft:TAleRBTreeNode;
function    GetMostRight:TAleRBTreeNode;

protected
procedure   RotateLeft;
procedure   RotateRight;
function    CompareKey(lpKey:Pointer):Longint;virtual;

public
property    Left:TAleRBTreeNode read CLeft write CLeft;
property    Right:TAleRBTreeNode read CRight write CRight;
property    Parent:TAleRBTreeNode read CParent write CParent;
property    Color:TNodeColor read NodeColor write NodeColor;
property    Root:TAleRBTreeNode read GetRoot;
property    Count:Longint read dwCount;
property    MostLeft:TAleRBTreeNode read GetMostLeft;
property    MostRight:TAleRBTreeNode read GetMostRight;

constructor Create;
destructor  Destroy;override;
function    InsertNode(N:TAleRBTreeNode; var OldNode:TAleRBTreeNode):TAleRBTreeNode;
function    DeleteNode(N:TAleRBTreeNode):TAleRBTreeNode;
function    Key:Pointer;virtual;
function    FindKey(lpKey:Pointer; var FindResult:Longint):TAleRBTreeNode;
procedure   ToArray(var A:TAleRBTreeNodesArray);
end;

Properties

Left
Right

property Left:TAleRBTreeNode;
property Right:TAleRBTreeNode;

Return or set left or right nodes.


Parent

property Parent:TAleRBTreeNode;

Returns or set parent node.


Color

property Color:TNodeColor;

Returns or set node color.
Property type defined as TNodeColor = (rbtree_black,rbtree_red);


Root

property Root:TAleRBTreeNode;

Returns root of the tree. Read only.


Count

property Count:LongInt;

Returns number of nodes of subtree. Read only.

For the tree root is equal to total number of nodes.


MostLeft

property MostLeft:TAleRBTreeNode;

Returns most left node of subtree (min key value). Read only.


MostRight

property MostRight:TAleRBTreeNode;

Returns most right node of subtree (max key value). Read only.


Methods

RotateLeft
RotateRight

procedure RotateLeft;
procedure RotateRight;

Internal methods performing nodes rotations. Used for rebalancing tree.


CompareKey

function CompareKey(lpKey:Pointer):LongInt;virtual;

Compares instance key with the key passed by lpKey. Returns values: -1 (key in lpKey is less than instance key), 0 (keys are equal), 1 (key in lpKey is greater than instance key).

Should be overriden in TAleRBTreeNode descendant.

TAleRBTreeNodeInt = class(TAleRBTreeNode)
private
dwKey:Longint;
...
protected
function CompareKey(lpKey:Pointer):Longint;override;
...
end;
...
function TAleRBTreeNodeInt.CompareKey;
begin
if Longint(lpKey^)>dwKey then CompareKey:=1 else
if Longint(lpKey^)<dwKey then CompareKey:=-1 else CompareKey:=0;
end;

Create

constructor Create;

Class constructor.


Destroy

destructor Destroy;override;

Class destructor.


InsertNode

function InsertNode(N:TAleRBTreeNode; var OldNode:TAleRBTreeNode):TAleRBTreeNode;

Method InsertNode inserts new node in the tree, rebalances the tree and returns new root node of the tree. Variable OldNode contains replaced node with the same key, otherwise it is nil.


DeleteNode

function DeleteNode(N:TAleRBTreeNode):TAleRBTreeNode;

Method DeleteNode removes node from the tree, rebalances the tree and returns new root node of the tree. After removing last node DeleteNode returns nil. DeleteNode doesn't free instance and release memory. After calling DeleteNode variable Node still keeps the removed node. It is necessary to manually free this instance (Node.Free).


Key

function Key:Pointer;virtual;

Returns pointer to the instance key.

Should be overriden in TAleRBTreeNode descendant.

TAleRBTreeNodeInt = class(TAleRBTreeNode)
private
dwKey:Longint;
...
public
function Key:Pointer;override;
...
end;
...
function TAleRBTreeNodeInt.Key;
begin
Key:=@dwKey;
end;

FindKey

function FindKey(lpKey:Pointer; var FindResult:LongInt):TAleRBTreeNode;

Returns node with key in lpKey parameter or nearest node if keys don't match. Value of FindResult parameter: -1; 0; 1 (key passed in parameter is less than key of returned node; keys are equal; key passed in parameter is greater than key of returned node).


ToArray

procedure ToArray(var A:TAleRBTreeNodesArray);

Returns in A array with tree nodes sorted by keys.

Type TAleRBTreeNodesArray defined as TAleRBTreeNodesArray = array of TAleRBTreeNode;