AVL-tree generic classes (Views: 30)
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/ |