- Bing Maps
- Speedcams in Moscow
- WP8 emulator tool
- Expression parser and evaluator (.NET, C#)
- Start - simple example
- Variables, properties, arrays and collections
- Functions and methods
- Something about iterating through UTF-16 Unicode strings (.NET, C#)
- Simple geo calculations
- Delphi (old works)
- Red-Black Tree. TAleRBTreeNode Delphi Class.
- Associative array. TAleAssociativeArray and TAleValue Delphi classes.
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).
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.
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.
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;
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.
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.