AVLTree - template version

WEBINAR:On-Demand

Application Security Testing: An Integral Part of DevOps

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

• 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

• 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.

• 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 :(

• 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 ) )

• 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).

Data Structures and Algorithm Analysis in C
By Mark Weiss

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!

• 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();

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.

```

• 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.

• 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.

```

• 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!

• You must have javascript enabled in order to post comments.

Top White Papers and Webcasts

• A CRM solution holds a wealth of information and document generation tools allow users to take that information and create documents with both visual appeal and function. Document generation is the process of automatically producing a file and document generation applications save companies time, mistakes, and money. You bought Salesforce to be more efficient — why are you still manually creating proposals, contracts, invoices, and account plans? Read this eBook to learn how you can automate virtually …

• Hybrid IT consists of both cloud and on-premises data center infrastructure. This book helps you understand both sides of the hybrid IT equation and how HPE can help your organization transform its IT operations and save time and money in the process. I delve into the worlds of security, economics, and operations to show you new ways to support your business workloads.

Most Popular Programming Stories

• There have been no articles posted today.