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;

// end of sample code

Last updated 16 Sep 1998


  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Cloud computing isn't new, but it's still a hot topic in technology circles. Moving to the cloud has done great things for many businesses. When it comes to handling a basic business necessity, cloud computing has brought many improvements to overall business continuity. Using the cloud for DR makes a lot of sense for many, but it's not exactly the most simple concept. Read this eBook to find answers to all the key questions IT professionals have about cloud-based disaster recovery, and helpful info around the …

  • Live Event Date: July 8, 2015 @ 2:00 p.m. ET / 11:00 a.m. PT With business driving the increasing adoption of agile methodologies such as Continuous Integration and Continuous Deployment, the need for agile database tooling has become even more important. In many companies, the database development lifecycle has become the bottleneck in an otherwise agile delivery process. As such, database professionals are under increasing pressure to shorten delivery timelines even further, only increasing the stakes …

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date