This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 
  AVL Tree Template
  Submitted by



Since I received a couple of responses to my offer to share my AVL template, here it is! I've also enclose a test application that verifies correct functioning. What is an AVL tree? An AVL tree is a mostly balanced tree that has the property that no subtree is every more than 1 longer than its sibling. This is slightly better than a red-black tree which has the property that no subtree is ever more than twice as long as its sibling. Here's a message by Yordan (warjo) that presents many interesting facts about AVL trees - link

What's special about this template? It's short, it implements insert, remove, and find, it comes with an iterator, it works :) I use it in instances when one would normally use a hash or other map, which is why the template takes a Key and an Item. I know that traditionally, ordered trees have only an Item, and sort based on that item, but a typical use for this template is for an asset cache, or state machine cache in a scripting engine. In those cases, the Items are not inherently ordered, but their handles are. Adding operator <, >, and == to objects which are not inherently comparable (such as state machines) would be icky architecturally, Why an AVL tree instead of using the STL? 1) I prefer AVL trees to red-black trees. 2) I mainly code for consoles and various considerations to do with console compilers, code footprint, and cross platform compatiblity preclude using the STL at this time. 3) When I debug I like to be able to quickly access the data structures I am traversing without having to open up the various allocators and what-not associated with STL. I know VC gives you tools to write macros to display the data any way I like, but since I don't develop with VC, that doesn't help me. This template is free for use, no warrantee or suitability for any particular purpose is expressed or implied. Verify that it works the way you expect before you incorporate it into your own project. - nick (meshula)

Currently browsing [avltree.zip] (5,376 bytes) - [avltest.cpp] - (1,330 bytes)


#include "avl.h"
#include <iostream>
#include <stdlib.h>

using namespace std; 	//introduces namespace std
int main( void )
{
	int i;
	AVL<short, short> junk;

	cout << "adding items\n";

	for (i = 0; i < 20; ++i)
	{
		junk.Insert(i, i + 1);
	}

	cout << "creating iterator\n";

	AVL<short, short>::Iterator<short, short> iter(&junk);

	bool more;
	short key = 3, item;

	more = iter.Find(key, item);
	cout << "Finding 3\n";
	cout << "key - " << key << " item - " << item << "\n";

	iter.GetFirst(key, item);

	cout << "Tree contains:\n";
	
	more = iter.GetFirst(key, item);
	while (more)
	{
		cout << "key - " << key << " item - " << item << "\n";
		more = iter.GetNext(key, item);
	}

	cout << "removing even keys\n";

	for (i = 0; i < 20; i += 2)
	{
		junk.Remove(i);
	}
	
	more = iter.GetFirst(key, item);
	while (more)
	{
		cout << "key - " << key << " item - " << item << "\n";
		more = iter.GetNext(key, item);
	}

	cout << "removing odd keys\n";

	for (i = 1; i < 20; i += 2)
	{
		junk.Remove(i);
	}

	more = iter.GetFirst(key, item);
	while (more)
	{
		cout << "key - " << key << " item - " << item << "\n";
		more = iter.GetNext(key, item);
	}

	cout << "done\n";

	return 0;
}

Currently browsing [avltree.zip] (5,376 bytes) - [AVL.h] - (15,750 bytes)


/*==========================================================================

	   _____                .__          .__          
	  /     \   ____   _____|  |__  __ __|  | _____   
	 /  \ /  \_/ __ \ /  ___/  |  \|  |  \  | \__  \  
	/    Y    \  ___/ \___ \|   Y  \  |  /  |__/ __ \_
	\____|__  /\___  >____  >___|  /____/|____(____  /
	        \/     \/     \/     \/                \/ 
	   _________   ____.____      ___________                      
	  /  _  \   \ /   /|    |     \__    ___/______   ____   ____  
	 /  /_\  \   Y   / |    |       |    |  \_  __ \_/ __ \_/ __ \ 
	/    |    \     /  |    |___    |    |   |  | \/\  ___/\  ___/ 
	\____|__  /\___/   |_______ \   |____|   |__|    \___  >\___  >
	        \/                 \/                        \/     \/ 

	with thanks to -
		Greig McLachlan of http://www.learntoprogram.com
			for providing a clean implementation of Insert which I used as a starting point
		Jason F Boxall of CSC330
			who posted his assignment on the web, I double checked my Remove implementation against his.
		R Levow of http://www.cse.fau.edu/~roy/cop3530.98f/prog5-BSTIterator.html
			who posted an algorithm for creating binary tree iterators

	http://meshula.artistnation.com
										2002

	The template is free for use, no warrantee or suitability for any particular 
	purpose is expressed or implied. Verify that it works the way you expect before you 
	incorporate it into your own project.

	public interface -
	
		AVL();
		~AVL();
		bool  Insert(KeyType key, ItemType item);
		bool  Remove(KeyType key);
		bool  Find(KeyType key, ItemType& item);
		short GetDepth()
		
		Iterator(Iterator*)
		Iterator(AVL*)
		~Iterator()
		
			// all return true for success, false for failure or end of tree

			bool GetFirst(KeyType& key, ItemType& item)
			bool GetNext(KeyType& key, ItemType& item)
			bool GetCurrent(KeyType& key, ItemType& item)
			bool Find(KeyType key, ItemType& item)

  ==========================================================================*/


/*--------------------------------------------------------------------------------------------
	    ___     ___           _           _                 _   _             
	   / \ \   / / |       __| | ___  ___| | __ _ _ __ __ _| |_(_) ___  _ __  
	  / _ \ \ / /| |      / _` |/ _ \/ __| |/ _` | '__/ _` | __| |/ _ \| '_ \ 
	 / ___ \ V / | |___  | (_| |  __/ (__| | (_| | | | (_| | |_| | (_) | | | |
	/_/   \_\_/  |_____|  \__,_|\___|\___|_|\__,_|_|  \__,_|\__|_|\___/|_| |_|
  --------------------------------------------------------------------------------------------*/

template<class KeyType, class ItemType>
class AVL
{
protected:
	template<class KeyType, class ItemType>
	class AVLNode
	{
	public:
		AVLNode(KeyType key, ItemType item) :
			m_Balance(0), m_Depth(0),
			m_Key(key), m_Data(item),
			m_pLeft(0), m_pRight(0)
		{
		}
		
		short		m_Balance;
		short		m_Depth;
		
		KeyType		m_Key;
		ItemType	m_Data;

		AVLNode*	m_pLeft;
		AVLNode*	m_pRight;
	};

	AVLNode<KeyType, ItemType>* m_pRoot;

public:

	/*------------------------------------------------------------------------
		             _     _ _        _       _             __                
		 _ __  _   _| |__ | (_) ___  (_)_ __ | |_ ___ _ __ / _| __ _  ___ ___ 
		| '_ \| | | | '_ \| | |/ __| | | '_ \| __/ _ \ '__| |_ / _` |/ __/ _ \
		| |_) | |_| | |_) | | | (__  | | | | | ||  __/ |  |  _| (_| | (_|  __/
		| .__/ \__,_|_.__/|_|_|\___| |_|_| |_|\__\___|_|  |_|  \__,_|\___\___|
		|_|                                                                    */

	AVL() : m_pRoot(0) { }
	~AVL() { }
	
	void 	Insert(KeyType key, ItemType item);
	void 	Remove(KeyType key);
	bool 	Find  (KeyType key, ItemType& item);
	
	short	GetDepth() const {	return (m_pRoot ? m_pRoot->m_Depth : 0);	}

	/*------------------------------------------------------------------------
		 _ _                 _             
		(_) |_ ___ _ __ __ _| |_ ___  _ __ 
		| | __/ _ \ '__/ _` | __/ _ \| '__|
		| | ||  __/ | | (_| | || (_) | |   
		|_|\__\___|_|  \__,_|\__\___/|_|   
																				*/

	template<class KeyType, class ItemType>
	class Iterator
	{
	#define kMaxAVLDepth 32
	
	public:
		Iterator(Iterator* pCopyMe) : 
			mpAVL(pCopyMe->mpAVL), mpCurr(pCopyMe->mpCurr)
		{
			mTraversalStackIndex = pCopyMe->mTraversalStackIndex;

			for (int i = 0; i < mTraversalStackIndex; ++i)
				mTraversalStack[i] = pCopyMe->mTraversalStack[i];
		}
		
		Iterator(AVL<KeyType, ItemType>* pTree) : mpAVL(pTree)
		{
			KeyType key;
			ItemType item;
			GetFirst(key, item);
		}

		~Iterator() { }

		bool GetCurrent(KeyType& key, ItemType& item)
		{
			if (mpCurr)
			{
				key = mpCurr->m_Key;
				item = mpCurr->m_Data;
				return true;
			}
			else
				return false;
		}

		// returns false if the tree is empty
		bool GetFirst (KeyType& key, ItemType& item)
		{
			mTraversalStackIndex = 0;
			
			if (!mpAVL->m_pRoot)
			{
				mpCurr = 0;
				item = 0;
				return false;
			}
			else
			{
				AVLNode<ItemType, KeyType>* pCurr = mpAVL->m_pRoot;
				AVLNode<ItemType, KeyType>* pPrev = pCurr;
				while (pCurr)
				{
					pPrev = pCurr;

					if (pCurr->m_pLeft)
						mTraversalStack[mTraversalStackIndex++] = pCurr;

					pCurr = pCurr->m_pLeft;
				}
			
				mpCurr = pPrev;
				key = mpCurr->m_Key;
				item = mpCurr->m_Data;
				return true;
			}
		}

		bool GetNext  (KeyType& key, ItemType& item)
		{
			if (!mpCurr)	// already done?
			{
				item = 0;
				return false;
			}
			else
			{
				AVLNode<KeyType, ItemType>* pCurr = mpCurr->m_pRight;	// start looking to the right

				while (true)	// this while forces a traversal as far left as possible
				{
					if (pCurr)	// if we have a pcurr, push it and go left, and repeat.
					{
						mTraversalStack[mTraversalStackIndex++] = pCurr;
						pCurr = pCurr->m_pLeft;
					}
					else	// backtrack
					{
						if (mTraversalStackIndex > 0)
						{
							AVLNode<KeyType, ItemType>* pCandidate = mTraversalStack[--mTraversalStackIndex];

							// did we backtrack up a right branch?
							if (mpCurr == pCandidate->m_pRight)
							{
								// if there is a parent, return the parent.
								if (mTraversalStackIndex > 0)
								{
									mpCurr = mTraversalStack[--mTraversalStackIndex];
									key = mpCurr->m_Key;
									item = mpCurr->m_Data;
									return true;
								}
								else	// if up a right branch, and no parent, traversal finished
								{
									mpCurr = 0;
									item = 0;
									return false;
								}
							}
							else	// up a left branch, done.
							{
								mpCurr = pCandidate;
								key = mpCurr->m_Key;
								item = mpCurr->m_Data;
								return true;
							}
						}
						else	// totally done
						{
							mpCurr = 0;
							item = 0;
							return false;
						}
					}
				}
			}
		}

		bool Find     (KeyType  key, ItemType& item)
		{
			AVLNode<KeyType, ItemType>* pCurr = mpAVL->m_pRoot;
			mTraversalStackIndex = 0;

			while (true)
			{
				AVLNode<KeyType, ItemType>* pPushMe = pCurr;
				if (pCurr->m_Key == key)	// already done?
				{
					mpCurr = pCurr;
					item = mpCurr->m_Data;
					return true;
				}
					
				if (pCurr->m_Key > key)
					pCurr = pCurr->m_pLeft;
				else
					pCurr = pCurr->m_pRight;

				if (pCurr)	// maintain the stack so that GetNext will work.
				{
					mTraversalStack[mTraversalStackIndex++] = pPushMe;
				}
				else	// couldn't find it.
				{
					mpCurr = 0;
					mTraversalStackIndex = 0;
					return false;
				}
			}
			
			return true;
		}

	protected:
		AVL*						mpAVL;		
		AVLNode<KeyType, ItemType>*	mTraversalStack[kMaxAVLDepth];
		short						mTraversalStackIndex;
		AVLNode<KeyType, ItemType>*	mpCurr;				// for iteration
	};

	friend class AVL::Iterator<KeyType, ItemType>;

protected:
	void _Insert        		(KeyType key, ItemType item, AVLNode<KeyType, ItemType>*& root);
	void _Remove				(AVLNode<KeyType, ItemType>*& root, KeyType key, bool& delOK);
	void _RemoveBothChildren	(AVLNode<KeyType, ItemType>*& root, AVLNode<KeyType, ItemType>*& curr, bool& delOK);
	bool _Find					(KeyType key, ItemType& item, AVLNode<KeyType, ItemType>* root);
	void ComputeBalance 		(AVLNode<KeyType, ItemType>*  root);
	void Balance        		(AVLNode<KeyType, ItemType>*& root);
	void BalanceRight			(AVLNode<KeyType, ItemType>*& root);
	void BalanceLeft			(AVLNode<KeyType, ItemType>*& root);
	void RotateLeft				(AVLNode<KeyType, ItemType>*& root);
	void RotateRight			(AVLNode<KeyType, ItemType>*& root);
};


/*--------------------------------------------------------------------------------------------
	 _                     _   _             
	(_)_ __  ___  ___ _ __| |_(_) ___  _ __  
	| | '_ \/ __|/ _ \ '__| __| |/ _ \| '_ \ 
	| | | | \__ \  __/ |  | |_| | (_) | | | |
	|_|_| |_|___/\___|_|   \__|_|\___/|_| |_|
  --------------------------------------------------------------------------------------------*/

template<class KeyType, class ItemType>
void AVL<KeyType,ItemType>::Insert(KeyType key, ItemType item)
{
	if (m_pRoot == 0)
	{
		m_pRoot = new AVLNode<KeyType, ItemType>(key, item);
	}
	else
		_Insert(key, item, m_pRoot);
}

template<class KeyType, class ItemType>
void AVL<KeyType, ItemType>::_Insert(KeyType key, ItemType item, AVLNode<KeyType, ItemType>*& root)
{
	if (key < root->m_Key)
	{
		if (root->m_pLeft)
			_Insert(key, item, root->m_pLeft);
		else
			root->m_pLeft = new AVLNode<KeyType, ItemType>(key, item);
	}
	else if (key > root->m_Key)
	{
		if (root->m_pRight)
			_Insert(key, item, root->m_pRight);
		else
			root->m_pRight = new AVLNode<KeyType, ItemType>(key, item);
	}
	else
	{
		// error - can't have duplicate keys.
		// if duplicate keys are okay, change key < to key <= above
	}
	
	ComputeBalance(root);
	Balance(root);
}

/*--------------------------------------------------------------------------------------------
	                                    _ 
	 _ __ ___ _ __ ___   _____   ____ _| |
	| '__/ _ \ '_ ` _ \ / _ \ \ / / _` | |
	| | |  __/ | | | | | (_) \ V / (_| | |
	|_|  \___|_| |_| |_|\___/ \_/ \__,_|_|
  --------------------------------------------------------------------------------------------*/
                                      
template<class KeyType, class ItemType>
void AVL<KeyType, ItemType>::Remove(KeyType key)
{
	bool delOK = false;
	_Remove(m_pRoot, key, delOK);
}

template<class KeyType, class ItemType>
void AVL<KeyType, ItemType>::_Remove(AVLNode<KeyType, ItemType>*& root, KeyType key, bool& delOK)
{
	if (!root)
	{
		delOK = false;
	}
	else if (root->m_Key > key)	// go to left subtree
	{
		_Remove(root->m_pLeft, key, delOK);

		if (delOK)
		{
			ComputeBalance(root);
			BalanceRight(root);
		}
	}
	else if (root->m_Key < key) // go to right subtree
	{
		_Remove(root->m_pRight, key, delOK);

		if (delOK)
		{
			ComputeBalance(root);
			BalanceLeft(root);
		}
	}
	else	// node found!
	{
		AVLNode<KeyType, ItemType>* pMe = root;
		
		if (!root->m_pRight)
		{
			root = root->m_pLeft;
			delOK = true;
			delete pMe;
		}
		else if (!root->m_pLeft)
		{
			root = root->m_pRight;
			delOK = true;
			delete pMe;
		}
		else
		{
			_RemoveBothChildren(root, root->m_pLeft, delOK);
			if (delOK)
			{
				ComputeBalance(root);
				Balance(root);
			}
				
			delOK = true;
		}
	}
}

template<class KeyType, class ItemType>
void AVL<KeyType, ItemType>::_RemoveBothChildren(AVLNode<KeyType, ItemType>*& root, AVLNode<KeyType, ItemType>*& curr, bool& delOK)
{
	if (!curr->m_pRight)
	{
		root->m_Key = curr->m_Key;
		root->m_Data = curr->m_Data;
		AVLNode<KeyType, ItemType>* pMe = curr;
		curr = curr->m_pLeft;
		delete pMe;
		delOK = true;
	}
	else
	{
		_RemoveBothChildren(root, curr->m_pRight, delOK);
		if (delOK)
		{
			ComputeBalance(root);
			Balance(root);
		}
	}
}

/*--------------------------------------------------------------------------------------------
	                         _     _             
	 ___  ___  __ _ _ __ ___| |__ (_)_ __   __ _ 
	/ __|/ _ \/ _` | '__/ __| '_ \| | '_ \ / _` |
	\__ \  __/ (_| | | | (__| | | | | | | | (_| |
	|___/\___|\__,_|_|  \___|_| |_|_|_| |_|\__, |
	                                       |___/ 
  --------------------------------------------------------------------------------------------*/

template<class KeyType, class ItemType>
bool AVL<KeyType, ItemType>::Find(KeyType key, ItemType& item)
{
	return _Find(key, item, m_pRoot);
}

template<class KeyType, class ItemType>
bool AVL<KeyType, ItemType>::_Find(KeyType key, ItemType& item, AVLNode<KeyType, ItemType>* root)
{
	if (root)
	{
		if (root->m_Key == key)
		{
			item = root->m_Data;
			return true;
		}
		
		if (key < root->m_Key)
			return _Find(key, item, root->m_pLeft);
		else
			return _Find(key, item, root->m_pRight);
	}
	else
	{
		return false;
	}
}


/*--------------------------------------------------------------------------------------------
	 _           _                  _             
	| |__   __ _| | __ _ _ __   ___(_)_ __   __ _ 
	| '_ \ / _` | |/ _` | '_ \ / __| | '_ \ / _` |
	| |_) | (_| | | (_| | | | | (__| | | | | (_| |
	|_.__/ \__,_|_|\__,_|_| |_|\___|_|_| |_|\__, |
	                                        |___/ 
  --------------------------------------------------------------------------------------------*/

template<class KeyType, class ItemType>
void AVL<KeyType, ItemType>::ComputeBalance(AVLNode<KeyType, ItemType>* root)
{
	if (root)
	{
		short leftDepth  = root->m_pLeft  ? root->m_pLeft->m_Depth  : 0;
		short rightDepth = root->m_pRight ? root->m_pRight->m_Depth : 0;

		root->m_Depth = 1 + ((leftDepth > rightDepth) ? leftDepth : rightDepth);
		root->m_Balance = rightDepth - leftDepth;
	}
}

template<class KeyType, class ItemType>
void AVL<KeyType, ItemType>::Balance(AVLNode<KeyType, ItemType>*& root)
{
	// AVL trees have the property that no branch is more than 1 longer than its sibling

	if (root->m_Balance > 1)
		BalanceRight(root);
		
	if (root->m_Balance < -1)
		BalanceLeft(root);
}

template<class KeyType, class ItemType>
void AVL<KeyType, ItemType>::BalanceRight(AVLNode<KeyType, ItemType>*& root)
{
	if (root->m_pRight)
	{
		if (root->m_pRight->m_Balance > 0)
		{
			RotateLeft(root);
		}
		else if (root->m_pRight->m_Balance < 0)
		{
			RotateRight(root->m_pRight);
			RotateLeft(root);
		}
	}
}

template<class KeyType, class ItemType>
void AVL<KeyType, ItemType>::BalanceLeft(AVLNode<KeyType, ItemType>*& root)
{
	if (root->m_pLeft)
	{
		if (root->m_pLeft->m_Balance < 0)
		{
			RotateRight(root);
		}
		else if (root->m_pLeft->m_Balance > 0)
		{
			RotateLeft(root->m_pLeft);
			RotateRight(root);
		}
	}
}

template<class KeyType, class ItemType>
void AVL<KeyType, ItemType>::RotateLeft(AVLNode<KeyType, ItemType>*& root)
{
	AVLNode<KeyType, ItemType>* pTemp = root;
	root = root->m_pRight;
	pTemp->m_pRight = root->m_pLeft;
	root->m_pLeft = pTemp;

	ComputeBalance(root->m_pLeft);
	ComputeBalance(root->m_pRight);
	ComputeBalance(root);
}

template<class KeyType, class ItemType>
void AVL<KeyType, ItemType>::RotateRight(AVLNode<KeyType, ItemType>*& root)
{
	AVLNode<KeyType, ItemType>* pTemp = root;
	root = root->m_pLeft;
	pTemp->m_pLeft = root->m_pRight;
	root->m_pRight = pTemp;

	ComputeBalance(root->m_pLeft);
	ComputeBalance(root->m_pRight);
	ComputeBalance(root);
}

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.