Difference between revisions of "AVL Tree"

From Lazarus wiki
(Searching items)
m (Text replace - "Delphi>" to "syntaxhighlight>")
Line 25: Line 25:
 
By default the tree is sorted for the pointers. That means similar to TFPList you can add any pointers or objects:
 
By default the tree is sorted for the pointers. That means similar to TFPList you can add any pointers or objects:
  
<Delphi>
+
<syntaxhighlight>
 
uses AvgLvlTree; // in package lazutils
 
uses AvgLvlTree; // in package lazutils
  
Line 38: Line 38:
 
// To remove an item from the tree use:
 
// To remove an item from the tree use:
 
Tree.Remove(AnObject1);
 
Tree.Remove(AnObject1);
</Delphi>
+
</syntaxhighlight>
  
 
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:
 
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>
+
<syntaxhighlight>
 
uses AvgLvlTree; // in package lazutils
 
uses AvgLvlTree; // in package lazutils
 
type
 
type
Line 67: Line 67:
 
   Tree.Add(MyData1);
 
   Tree.Add(MyData1);
 
end;
 
end;
</Delphi>
+
</syntaxhighlight>
  
 
==Enumerating all items of a tree==
 
==Enumerating all items of a tree==
Line 73: Line 73:
 
This will enumerate from lowest to highest:
 
This will enumerate from lowest to highest:
  
<Delphi>
+
<syntaxhighlight>
 
var
 
var
 
   MyData: TMyData;
 
   MyData: TMyData;
Line 82: Line 82:
 
   end;
 
   end;
 
end;
 
end;
</Delphi>
+
</syntaxhighlight>
  
 
This will enumerate from highest to lowest:
 
This will enumerate from highest to lowest:
  
<Delphi>
+
<syntaxhighlight>
 
var
 
var
 
   MyData: TMyData;
 
   MyData: TMyData;
Line 95: Line 95:
 
   end;
 
   end;
 
end;
 
end;
</Delphi>
+
</syntaxhighlight>
  
  
Line 102: Line 102:
 
You can search an item with the same key:
 
You can search an item with the same key:
  
<Delphi>
+
<syntaxhighlight>
 
var
 
var
 
   Node: TAvgLvlTreeNode;
 
   Node: TAvgLvlTreeNode;
Line 111: Line 111:
 
                 // so under Windows it can find a node with Filename 'TEST'
 
                 // so under Windows it can find a node with Filename 'TEST'
 
end;
 
end;
</Delphi>
+
</syntaxhighlight>
  
 
'''Note:''' '''Find''' will find a node where your compare function returns 0.
 
'''Note:''' '''Find''' will find a node where your compare function returns 0.
Line 117: Line 117:
 
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:
 
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>
+
<syntaxhighlight>
 
function CompareFilenameWithMyData(Filename, MyData: Pointer): integer;
 
function CompareFilenameWithMyData(Filename, MyData: Pointer): integer;
 
begin
 
begin
Line 132: Line 132:
  
 
end;
 
end;
</Delphi>
+
</syntaxhighlight>

Revision as of 00:44, 25 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:

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

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

This will enumerate from lowest to highest:

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

This will 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;


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;