AVLTree - template version

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