Articles   Members Online:
-Article/Tip Search
-News Group Search over 21 Million news group articles.
-Delphi/Pascal
-CBuilder/C++
-C#Builder/C#
-JBuilder/Java
-Kylix
Member Area
-Home
-Account Center
-Top 10 NEW!!
-Submit Article/Tip
-Forums Upgraded!!
-My Articles
-Edit Information
-Login/Logout
-Become a Member
-Why sign up!
-Newsletter
-Chat Online!
-Indexes NEW!!
Employment
-Build your resume
-Find a job
-Post a job
-Resume Search
Contacts
-Contacts
-Feedbacks
-Link to us
-Privacy/Disclaimer
Embarcadero
Visit Embarcadero
Embarcadero Community
JEDI
Links
How to use AVL-tree generic classes Turn on/off line numbers in source code. Switch to Orginial background IDE or DSP color Comment or reply to this aritlce/tip for discussion. Bookmark this article to my favorite article(s). Print this article
07-Jul-03
Category
Algorithm
Language
Delphi 4.x
Views
136
User Rating
No Votes
# Votes
0
Replies
0
Publisher:
DSP, Administrator
Reference URL:
DKB
			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/ 




			
Vote: How useful do you find this Article/Tip?
Bad Excellent
1 2 3 4 5 6 7 8 9 10

 

Advertisement
Share this page
Advertisement
Download from Google

Copyright © Mendozi Enterprises LLC