AVL-tree generic classes

Problem/Question/Abstract:

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:

type
  TMyItem = class;

  TMyCollection = class(TStringKeyAVLtree)
  protected
    function GetItems(AKey: string): TMyItem;
  public
    constructor Create;
    function Add(const AKey, ADescription: string): TMyItem;
    property Items[AKey: string]: TMyItem read GetItems;
  end;

  TMyItem = class(TStringKeyAVLtreeNode)
  protected
    FDescription: string;
  public
    property FileName: string read FKey;
      // for your convinience, FKey is defined in base class
    property Desciption: string read FDescription write FDescription;
  end;

constructor TMyCollection.Create;
begin
  inherited Create(TMyItem); // class of items
end;

function TMyCollection.Add(const AKey, ADescription: string): TMyItem;
begin
  Result := TMyItem(inherited Add(AKey));
  if Result = nil then
    raise Exception.Create('Item ''' + AKey + ''' already exists');
  Result.Description := ADescription;
end;

function GetItems(AKey: string): TMyItem;
begin
  Result := TMyItem(Find(AKey));
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

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