Click here to Skip to main content
13,298,551 members (72,199 online)
Click here to Skip to main content
Add your own
alternative version


31 bookmarked
Posted 22 Feb 2000

Addison-Velski and Landis (AVL) Binary Trees

, 22 Feb 2000
Rate this:
Please Sign up or sign in to vote.
Describes an implementation of AVL Trees.
  • Download demo project - 54 Kb
  • I have implemented the binary trees of Addison-Velski and Landis (AVL-Trees), which allow standard operations like insert, search and delete in logarithmical time. Ordinary binary trees can become very obscure. They can become a linear structure and the basic operations take linear and not logarithmical time. The advantage of the AVL-Trees is a strategy of restructuring the tree after insert and delete operations. The restructuring operation itself only takes logarithmical time. So the trees are highly efficient binary trees to hold a large number of items. I use such trees to sort data. The sort of data using AVL-Trees takes n*log(n) time, so you can sort a lot of data in optimal time. I have sorted with that technology hundreds of thousands of items within a quarter of an hour. It is very easy to eliminate duplicates, duplicates will not be inserted in the tree. What other algorithm works so efficiently? And the greatest advantage is that the code is absolutely easy to use, 10 lines are enough to sort a file. The Trees are implemented as templates, so you can use everything you want as tree items. Items only must be comparable. The code is self-documentating. The classes are CAVLNode<class T>, CAVLTree<class T> and CAVLTreeIterator<class T>.

    Here is an example to sort a file (file should not have identical lines, otherwise the duplicates are eliminated):

    // sample code
    #include <fstream.h>
    #include "AVLBaum.h"
    void SortFile(const char* ifname, const char* ofname)
    	ifstream is(ifname);
    	ofstream os(ofname);
    	char buffer[255];
    	CAVLTree<CString> tree;
    	while (is.getline(buffer, sizeof(buffer)-1)
    		tree.Insert(new CString(buffer));
    	CAVLTreeIterator<CString> iter(tree);
    	while (iter)
    		os << *(iter.GetData()) << endl;
    // end of sample code


    This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

    A list of licenses authors might use can be found here


    About the Author

    Andreas Jäger
    Web Developer
    Germany Germany
    No Biography provided

    You may also be interested in...

    Comments and Discussions

    QuestionAVL Trees Pin
    Ben McNamara13-Sep-15 18:45
    memberBen McNamara13-Sep-15 18:45 
    QuestionHELP! Pin
    nguyenspk4-May-12 0:48
    membernguyenspk4-May-12 0:48 
    GeneralAdelson-Velskii, not "Addison-Velski" Pin
    Vassili Postnikov20-Sep-00 21:41
    sussVassili Postnikov20-Sep-00 21:41 
    GeneralExcellent stuff. Pin
    Nick Fenwick22-Aug-00 3:00
    sussNick Fenwick22-Aug-00 3:00 

    General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

    Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

    Permalink | Advertise | Privacy | Terms of Use | Mobile
    Web04 | 2.8.171207.1 | Last Updated 23 Feb 2000
    Article Copyright 2000 by Andreas Jäger
    Everything else Copyright © CodeProject, 1999-2017
    Layout: fixed | fluid