Title: AVL-tree generic classes.
Question: Balanced binary tree (AVL-tree) generic classes.
Answer:
Excuse my english.
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/