AVLTree - template version


How to Help Your Business Become an AI Early Adopter

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 has the potential to offer many benefits that can enable great success within your business. However, there are still many myths floating around about backing up to the cloud. In this eBook, you'll discover the truth about five of the most common cloud myths, including myths about security, maintaining regulatory compliance and more. Get to the truth, so you can backup to the cloud with confidence.

  • IDC estimates that more than 70% of organizations have a cloud-first application deployment strategy to align with digital transformation initiatives. As such, many organizations are transitioning to Microsoft Office 365 and utilizing public clouds such as Microsoft Azure. However, IT leaders are discovering that default data protection schemes are not as robust as they desire. As a result, many are turning to Veeam® to provide the necessary data management and protection policies demanded by the …

Most Popular Programming Stories

More for Developers

RSS Feeds

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