AVLTree – template version

Download Source and Demo project: avl.zip

I have implemented the binary tree’s of Addison-Velski and Landis (AVL-Tree’s), which
allow Standard-operation 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-Tree’s is a
strategy of restructurate the tree after Insert- and Delete-operations. The
restructuration itself only takes logarithmical time. So the trees are high-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 hundrets 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 efficient? 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 item. 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;
		iter++;
	}
}

// end of sample code

Last updated 16 Sep 1998