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.