Difference between revisions of "AVL Tree"

From Free Pascal wiki
Jump to navigationJump to search
Line 14: Line 14:
 
*Deleting an item takes O(log(n))
 
*Deleting an item takes O(log(n))
 
*Finding the lowest or highest item takes log(n)
 
*Finding the lowest or highest item takes log(n)
*Finding the sucessor or precessor item takes O(log(n))
+
*Finding the sucessor or predecessor item takes O(log(n))
 
*Iterating through all items in order takes O(n)
 
*Iterating through all items in order takes O(n)
 
*Enumerators for running from lowest to highest and highest to lowest
 
*Enumerators for running from lowest to highest and highest to lowest

Revision as of 09:39, 18 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:

<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> 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 insensiive under Windows
                // so this find can also find a node with the Filename 'TEST' under Windows

end; </Delphi>

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:

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