AVL Tree

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

To create a tree 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 the tree

<Delphi> var

 MyData: TMyData;

begin

 for Node in Tree do begin
   MyData:=TMyData(Node.Data);
   writeln(MyData.Filename);
 end;

end; </Delphi>