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


Comments

  • nice use of templates

    Posted by Legacy on 12/08/2003 12:00am

    Originally posted by: satish kumar

    your prigram is some what bug free.
    but there are some restricted usages for deletion
    and the member functions

    Reply
  • Balanced binary trees

    Posted by Legacy on 05/28/2001 12:00am

    Originally posted by: John Duncan

    The Dinkumware STL (the one that comes with MSVC) already includes a red-black tree, another sort of self-balancing tree. Types std::set and std::map both derive from xtree, which is a red-black tree implementation. Red-black trees guarantee (2*log n) worst-case search time. Before you use a custom class, you should consider whether the standard class is sufficient for your needs, as this improves the learning curve for someone reading your software and reduces your potential error rate.

    Reply
  • This is just what I needed

    Posted by Legacy on 09/22/2000 12:00am

    Originally posted by: Josh

    I am taking a class in windows programming and want to focus on the windows part not the data structres. I spent the last semester building B and b+ trees and extendable hashing. That class was a ton of work :(

    Reply
  • Using it for parsing Mathematical Expressions

    Posted by Legacy on 02/17/2000 12:00am

    Originally posted by: Robert Noldin

    Would you be able to use this binary tree for parsing of mathematical equations suck as.

    ((( A + B ) > 20 ) AND ( (y - z) < 10 ) )

    Reply
  • An alternative algorithm to an AVL Tree

    Posted by Legacy on 02/22/1999 12:00am

    Originally posted by: Daren Yong

    Yes I thought avl trees were the best for sorting items in large lists.

    Even more so where you have a frequently updated large list. :)

    But as it turns out a HEAP can sometimes be more efficient if you are willing to give up a few tree operations. (Specifically inserts are log n rather than in AVL trees where you must do tree balancing).

    Specifically the algorithm you can use is called a HEAPSORT and works by repeatedly removing the minimum item from the priority queue (heap).

    For more info check out:

    Data Structures and Algorithm Analysis in C
    By Mark Weiss

    Reply
  • Hope all Bugs are fixed - please redownload the new code and new sample

    Posted by Legacy on 11/18/1998 12:00am

    Originally posted by: Andreas J�ger

    I hope I have fixed all the Bugs in Delete() and RestructureDelete(). Tests with hundrets of thousands of Inserts and Deletes with permanent balance and consistency checks were successful. Please download the new version of the code. The demo is also updated.

    Have a lot of fun with my class!

    Reply
  • Another Bug in CAVLTree<T>::Delete(T* data)

    Posted by Legacy on 11/17/1998 12:00am

    Originally posted by: David Patrick

    The following lines appear  starting at line 910 in AVLBaum.h
    
    

    if (item != NULL && item->Left != NULL && item->Right != NULL)
    {
    CAVLNode<T>* y = item->Left->GetLastNodeInOrder();
    CAVLNode<T>* z = y->Left;
    delete item->Data;
    item->Data = y->Data;
    y->Data = NULL;
    if (y->IsLeftSibling())
    y->Parent->Left = z;
    else
    y->Parent->Right = z;
    if (z != NULL)
    z->Parent = y->Parent;
    startitem = item; <<< bug here >>>
    delete y;
    }
    startitem->RestructureDelete();

    Instead of "startitem = item;"
    the line should be "startitem = y->Parent;"

    After the desired node is deleted, the line

    "startitem->RestructureDelete();"

    goes through and rebalances the tree to account for the deleted node. The rebalancing starts at the node above the deleted node and recurses back up the tree till it gets to the root or it has balanced the tree.

    The problem is that when the node that is to be deleted, ie "item", has both a left & right branch then the actual node itself is not deleted, but a different node, ie "y", is deleted. The code as it originally stood started to rebalance the tree at the node originally designated to be deleted ( "item" ) instead of starting at the parent of the node that was actually deleted ( "y" )( parent being "y->Parent" ). This was a problem because "item" is closer to the root of the tree than the parent of "y" and hence the subtree starting at "item" does not itself get balanced.

    I noticed the error when I did a delete of the root node of a tree that had both left & right branches .. The item got deleted, but the "Balance" values for the nodes in the tree were not always correctly set.

    Reply
  • Warning - Dont call tree.Delete(myiterator.GetData())

    Posted by Legacy on 11/15/1998 12:00am

    Originally posted by: David Patrick


    Yeah, it should have been obvious but it wasnt to me the first time.

    the myiterator object maintains a pointer to the current node, which is deleted as a result of the delete call and hence on the next reference, such as in myiterator++, the copy of the current node that the iterator maintains is no longer valid and hence the operator++() function is working with, at best, garabage.

    Seriously though, I love this class.

    Reply
  • Bug in CAVLTree<T>::Delete(T* data)

    Posted by Legacy on 11/05/1998 12:00am

    Originally posted by: David Patrick

    First let me say this is a great class, I use it all the time .. hence probably why I was able to find this
    bug.
    
    

    The following line appears at starting at line 910 in AVLBaum.h

    if (item != NULL && item->Left != NULL && item->Right != NULL)
    {
    CAVLNode<T>* y = item->Left->GetLastNodeInOrder();
    CAVLNode<T>* z = y->Left;
    delete item->Data;
    item->Data = y->Data;
    y->Data = NULL;
    if (y->IsLeftSibling())
    y->Parent->Left = z;
    else
    y->Parent->Right = z;
    if (z != NULL)
    z->Parent = y->Parent;
    startitem = item;
    delete y; <<< bug here >>>
    }

    if y->Left is not NULL then when the delete y is executed then z is also deleted since y->Left was never reset to NULL after being assigned to z.

    Recommend changing

    if (z != NULL)
    z->Parent = y->Parent;

    to

    if (z != NULL)
    {
    z->Parent = y->Parent;
    y->Left = NULL;
    }

    or just add the unconditional statement

    y->Left = NULL;

    after the assignment of y->Left to z.

    Reply
  • Great template class!

    Posted by Legacy on 10/29/1998 12:00am

    Originally posted by: Patty You

    I truly enjoy using this template class! Thank you for sharing with us!

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

Top White Papers and Webcasts

  • The first phase of API management was about realizing the business value of APIs. This next wave of API management enables the hyper-connected enterprise to drive and scale their businesses as API models become more complex and sophisticated. Today, real world product launches begin with an API program and strategy in mind. This API-first approach to development will only continue to increase, driven by an increasingly interconnected web of devices, organizations, and people. To support this rapid growth, …

  • Java developers know that testing code changes can be a huge pain, and waiting for an application to redeploy after a code fix can take an eternity. Wouldn't it be great if you could see your code changes immediately, fine-tune, debug, explore and deploy code without waiting for ages? In this white paper, find out how that's possible with a Java plugin that drastically changes the way you develop, test and run Java applications. Discover the advantages of this plugin, and the changes you can expect to see …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds