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):
#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++;
}
}