Difference between revisions of "AVL Tree"
m (Text replace - "Delphi>" to "syntaxhighlight>") |
|||
Line 131: | Line 131: | ||
Node:=Tree.FindKey(Pointer(Filename),@CompareFilenameWithMyData); | Node:=Tree.FindKey(Pointer(Filename),@CompareFilenameWithMyData); | ||
+ | end; | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | =Associative arrays using AVL trees= | ||
+ | |||
+ | An associative array is an array where instead of an index an different key is used. For example a string. | ||
+ | The unit AvgLvlTree implements several associative arrays using AVL trees: | ||
+ | |||
+ | *TStringToStringTree: string to string, you can choose case sensitive or case insensitive or provide your own string comparison function | ||
+ | *TStringToPointerTree: As TStringToStringTree but to arbitrary pointers, which might be objects | ||
+ | |||
+ | Here is an example demonstrating how to use a TStringToStringTree: | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | uses | ||
+ | AvgLvlTree; | ||
+ | var | ||
+ | NameToValue: TStringToStringTree; | ||
+ | S2SItem: PStringToStringItem; | ||
+ | begin | ||
+ | // create | ||
+ | NameToValue:=TStringToStringTree.Create(false); // false = Names are compared case insensitive via ''AnsiCompareText'' | ||
+ | |||
+ | // set values | ||
+ | NameToValue['First'] := 'One'; | ||
+ | NameToValue['Second'] := 'Two'; | ||
+ | |||
+ | // get values | ||
+ | writeln('First=',NameToValue['first']); // writes one | ||
+ | writeln('Second=',NameToValue['second']); // writes two | ||
+ | writeln('Third=',NameToValue['second']); // write the empty string | ||
+ | |||
+ | // check if a key is defined | ||
+ | writeln('First exists: ',NameToValue.Contains('first')); // gives true | ||
+ | writeln('Third exists: ',NameToValue.Contains('third')); // gives false | ||
+ | |||
+ | // enumerate all values | ||
+ | for S2SItem in NameToValue do | ||
+ | writeln('Name=',S2SItem^.Name,' Value=',S2SItem^.Value); | ||
+ | |||
+ | // free | ||
+ | NameToValue.Free; | ||
end; | end; | ||
</syntaxhighlight> | </syntaxhighlight> |
Revision as of 00:04, 27 March 2012
TAVLTree
Implemented in the FCL unit avl_tree. This is the predecessor of TAvgLvlTree.
TAvgLvlTree
Where to get: Unit AvgLvlTree of Lazarus package LazUtils of the Lazarus sources.
The AVL trees - Average Level Trees are sorted self balancing binary trees. Similar to a list like TPFList a TAvgLvlTree can store arbitrary data (Pointer), but contrary to TFPList the tree is always sorted and balanced. Therefore searching is very fast. Features:
- You can define your own compare function or method.
- Searching an item or key takes O(log(n))
- Inserting an item takes O(log(n))
- Deleting an item takes O(log(n))
- Finding the lowest or highest item takes log(n)
- Finding the sucessor or predecessor item takes O(log(n))
- Iterating through all items in order takes O(n)
- Enumerators for running from lowest to highest and highest to lowest
- Supports duplicates
- Keeps duplicates order stable.
- It is not thread safe, but it does not use any global variables. So it can be used in threads just like TFPList.
Creating a tree
By default the tree is sorted for the pointers. That means similar to TFPList you can add any pointers or objects:
uses AvgLvlTree; // in package lazutils
Tree:=TAvgLvlTree.Cteate;
Tree.Add(AnObject1);
Tree.Add(AnObject2);
...
// If you want to know if an item is already in the tree use Find:
if Tree.Find(AnObject1)<>nil then
writeln('AnObject is in the tree');
...
// To remove an item from the tree use:
Tree.Remove(AnObject1);
To create a tree for your custom data you only need a compare function. The following example demonstrates how to sort TMyData objects via their Filenames:
uses AvgLvlTree; // in package lazutils
type
TMyData = class
public
Filename: string;
Content: string;
end;
function CompareMyData(Data1, Data2: Pointer): integer;
begin
Result:=CompareFilenames(TMyData(d1).Filename,TMyData(d2).Filename);
end;
...
var
MyData1: TMyData;
Tree: TAvgLvlTree;
begin
Tree:=TAvgLvlTree.Create(@CompareMyData);
MyData1:=TMyData.Create;
MyData1.Filename:='SomeFile';
Tree.Add(MyData1);
end;
Enumerating all items of a tree
This will enumerate from lowest to highest:
var
MyData: TMyData;
begin
for Node in Tree do begin
MyData:=TMyData(Node.Data);
writeln(MyData.Filename);
end;
end;
This will enumerate from highest to lowest:
var
MyData: TMyData;
begin
for Node in Tree.GetEnumeratorHighToLow do begin
MyData:=TMyData(Node.Data);
writeln(MyData.Filename);
end;
end;
Searching items
You can search an item with the same key:
var
Node: TAvgLvlTreeNode;
begin
MyData.Filename:='test';
Node:=Tree.Find(MyData); // finds a node with a Filename = 'test'
// Note: The above function CompareFilenames works case insensitive under Windows
// so under Windows it can find a node with Filename 'TEST'
end;
Note: Find will find a node where your compare function returns 0.
You can also search directly with a filename, without creating a TMyData. The function FindKey takes as arguments a key (here: the filename) and a special compare function:
function CompareFilenameWithMyData(Filename, MyData: Pointer): integer;
begin
Result:=CompareFilenames(String(Filename),TMyData(MyData).Filename);
end;
...
var
Filename: string;
Node: TAvgLvlTreeNode;
begin
Filename:='Test';
Node:=Tree.FindKey(Pointer(Filename),@CompareFilenameWithMyData);
end;
Associative arrays using AVL trees
An associative array is an array where instead of an index an different key is used. For example a string. The unit AvgLvlTree implements several associative arrays using AVL trees:
- TStringToStringTree: string to string, you can choose case sensitive or case insensitive or provide your own string comparison function
- TStringToPointerTree: As TStringToStringTree but to arbitrary pointers, which might be objects
Here is an example demonstrating how to use a TStringToStringTree:
uses
AvgLvlTree;
var
NameToValue: TStringToStringTree;
S2SItem: PStringToStringItem;
begin
// create
NameToValue:=TStringToStringTree.Create(false); // false = Names are compared case insensitive via ''AnsiCompareText''
// set values
NameToValue['First'] := 'One';
NameToValue['Second'] := 'Two';
// get values
writeln('First=',NameToValue['first']); // writes one
writeln('Second=',NameToValue['second']); // writes two
writeln('Third=',NameToValue['second']); // write the empty string
// check if a key is defined
writeln('First exists: ',NameToValue.Contains('first')); // gives true
writeln('Third exists: ',NameToValue.Contains('third')); // gives false
// enumerate all values
for S2SItem in NameToValue do
writeln('Name=',S2SItem^.Name,' Value=',S2SItem^.Value);
// free
NameToValue.Free;
end;