Author: Alex Konshin

Balanced binary tree (AVL-tree) generic classes.

Answer:

AVLtrees unit implement fast insertion, replacing, deletion and search of item 
(complexity is O*log(N)). 
It contains low level functions, low level class and user-friendly classes. 
Most of functions are implemented on BASM (inline assembler). 

You may use TStringKeyAVLtree, TIntegerKeyAVLtree classes directly or declare 
descedants from one of these. 

Example for more complex way - declaring own classes: 

1   type
2     TMyItem = class;
3   
4     TMyCollection = class(TStringKeyAVLtree)
5     protected
6       function GetItems(AKey: string): TMyItem;
7     public
8       constructor Create;
9       function Add(const AKey, ADescription: string): TMyItem;
10      property Items[AKey: string]: TMyItem read GetItems;
11    end;
12  
13    TMyItem = class(TStringKeyAVLtreeNode)
14    protected
15      FDescription: string;
16    public
17      property FileName: string read FKey;
18        // for your convinience, FKey is defined in base class
19      property Desciption: string read FDescription write FDescription;
20    end;
21  
22  constructor TMyCollection.Create;
23  begin
24    inherited Create(TMyItem); // class of items
25  end;
26  
27  function TMyCollection.Add(const AKey, ADescription: string): TMyItem;
28  begin
29    Result := TMyItem(inherited Add(AKey));
30    if Result = nil then
31      raise Exception.Create('Item ''' + AKey + ''' already exists');
32    Result.Description := ADescription;
33  end;
34  
35  function GetItems(AKey: string): TMyItem;
36  begin
37    Result := TMyItem(Find(AKey));
38  end;


See also little sample supplied with unit. 

See Dr.D.E.Knuth "Art of Computer Programming" for more information about balanced 
trees. 
For implementation of item deletion I use an article "An Iterative Algorithm for 
Deletion from AVL-Balanced Binary Trees" by Ben Pfaff , 
http://www.msu.edu/user/pfaffben/avl http://www.msu.edu/user/pfaffben/avl 

AVLtrees unit (sources) is available on my homepage http://www.mtgroup.ru/~alexk/ 
http://www.mtgroup.ru/~alexk/