AVL Tree
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.Create;
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
Enumerate from lowest to highest
var
MyData: TMyData;
begin
for Node in Tree do begin
MyData:=TMyData(Node.Data);
writeln(MyData.Filename);
end;
end;
Notes:
- You can insert new nodes while enumerating with this enumerator.
- You must not delete the Node, nor change the Node.Data using this enumerator.
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;
Delete all nodes that fits a condition
If you need full control over the enumeration you can use Node.Sucessor and Node.Precessor. Here is an example how to delete all nodes that fits a filter:
var
Node: TAvgLvlTreeNode;
begin
Node:=Tree.FindLowest;
while Node<>nil do begin
NextNode:=Node.Successor;
if TMyData(Node.Data).Flag=true then
Tree.Delete(Node); // Note: this frees the Node, not the Node.Data. Use Tree.FreeAndDelete(Node) to free the Data.
Node:=NextNode;
end;
end;
Note:
- TMyData.Flag is just an example property. You can check whatever you want.
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;
Resorting, changing the order
You can change the compare function. The tree will automatically rebuild itself. The Nodes will be destroyed and all Data will be added into new nodes. For example you can switch from comparing case sensitive to case insensitive:
type
TMyData = class
public
Name: string;
constructor Create(aName: string);
end;
constructor TMyData.Create(aName: string);
begin
Name:=aName;
end;
function CompareMyDataCaseSensitive(Data1, Data2: Pointer): integer;
begin
Result:=CompareStr(TMyData(Data1).Name,TMyData(Data2).Name);
end;
function CompareMyDataCaseInsensitive(Data1, Data2: Pointer): integer;
begin
Result:=AnsiCompareText(TMyData(Data1).Name,TMyData(Data2).Name);
end;
procedure Demo;
var
Tree: TAvgLvlTree;
Node: TAvgLvlTreeNode;
begin
Tree:=TAvgLvlTree.Create(@CompareMyDataCaseSensitive);
Tree.Add(TMyData.Create('ABC'));
Tree.Add(TMyData.Create('Test'));
Tree.Add(TMyData.Create('abc'));
Tree.Add(TMyData.Create('test'));
writeln('sorted case sensitive:');
for Node in Tree do
writeln(' ',TMyData(Node.Data).Name);
// sort case insensitivie
Tree.OnCompare:=@CompareMyDataCaseInsensitive;
writeln('sorted case insensitive:');
for Node in Tree do
writeln(' ',TMyData(Node.Data).Name);
end;
Output:
sorted case sensitive: ABC Test abc test sorted case insensitive: ABC abc Test test
Associative arrays using AVL trees
An associative array is an array where instead of a the position an arbitrary key is used to find an item. 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['third']); // third is not yet set, it writes 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;
Indexed AVL Tree
TIndexedAVLTree extends TAvgLvlTree with the ability to access the nodes via their index (0=lowest, Count-1=highest) similar to an array. In other words it is like an array that is always sorted.
uses
AvgLvlTree;
type
TMyData = class
public
Name: string;
constructor Create(aName: string);
end;
constructor TMyData.Create(aName: string);
begin
Name:=aName;
end;
function CompareMyDataCaseInsensitive(Data1, Data2: Pointer): integer;
begin
Result:=AnsiCompareText(TMyData(Data1).Name,TMyData(Data2).Name);
end;
var
SortedArray: TIndexedAVLTree;
Node: TIndexedAVLTreeNode;
begin
// create
SortedArray:=TIndexedAVLTree.Create(@CompareMyDataCaseInsensitive);
SortedArray.Add(TMyData.Create('Mars'));
SortedArray.Add(TMyData.Create('Earth'));
SortedArray.Add(TMyData.Create('Venus'));
// access items via index
for i:=0 to SortedArray.Count-1 do
writeln(i,': ',TMyData(SortedArray[i]).Name);
// access nodes via GetNodeAtIndex
for i:=0 to SortedArray.Count-1 do
writeln(i,': ',TMyData(SortedArray.GetNodeAtIndex(i).Data).Name);
// get the index of a node
i:=2;
Node:=SortedArray.GetNodeAtIndex(i);
writeln(i,'=',SortedArray.NodeToIndex(Node));
SortedArray.FreeAndClear; // free nodes and objects
SortedArray.Free; // free the tree
end;
See also
- Data Structures, Containers, Collections Alternative data structures