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: The foll example

<Delphi> 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;

... Tree:=TAvgLvlTree.Create(@CompareMyData); MyData1:=TMyData.Create; MyData1.Filename:='SomeFile'; Tree.Add(MyData1); </Delphi>