Difference between revisions of "AVL Tree"
Line 21: | Line 21: | ||
==Creating a tree== | ==Creating a tree== | ||
− | To create a tree you only need a compare function. The following example demonstrates how to sort TMyData objects via their Filenames: | + | By default the tree is sorted for the pointers. That means similar to TFPList you can add any pointers or objects: |
+ | |||
+ | <Delphi> | ||
+ | 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); | ||
+ | </Delphi> | ||
+ | |||
+ | 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: | ||
<Delphi> | <Delphi> |
Revision as of 03:50, 18 March 2012
TAVLTree
Implemented in the FCL unit avl_tree. This is the predecessor of TAvgLvlTree.
TAvgLvlTree
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 precessor 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:
<Delphi> 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); </Delphi>
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:
<Delphi> 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; </Delphi>
Enumerating all items of a tree
This will enumerate from lowest to highest:
<Delphi> var
MyData: TMyData;
begin
for Node in Tree do begin MyData:=TMyData(Node.Data); writeln(MyData.Filename); end;
end; </Delphi>
This will enumerate from highest to lowest:
<Delphi> var
MyData: TMyData;
begin
for Node in Tree.GetEnumeratorHighToLow do begin MyData:=TMyData(Node.Data); writeln(MyData.Filename); end;
end; </Delphi>
Searching items
You can search an item with the same key:
<Delphi> Node:=Tree.Find(MyData); </Delphi>
Note: Find will find a node where your compare function returns 0.