AVLTree.cpp

Go to the documentation of this file.

/** @file AVLTree.cpp
* @author Gabor Madl
* @date Created 10/2006
* @brief AVL-tree template class.
*
*
* =================================================================
* DREAM License v2.0
* 
* DREAM - Distributed Real-time Embedded Analysis Method
* http://dre.sourceforge.net.
* Copyright (c) 2005-2007 Gabor Madl, All Rights Reserved.
* 
* This file is part of DREAM.
* 
* DREAM is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation. No future versions of
* the GPL license may be automatically applied to DREAM. It is in
* the sole discretion of the copyright holder to determine whether
* DREAM may be released under a different license or terms. There
* are no restrictions on the use of DREAM for any purpose.
* 
* DREAM is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* 
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
* 
* By submitting comments, suggestions, code, code snippets,
* techniques (including that of usage), and algorithms, submitters
* acknowledge that they have the right to do so, that any such
* submissions are given freely and unreservedly, and that they
* waive any claims to copyright or ownership. In addition,
* submitters acknowledge that any such submission might become
* part of the copyright maintained on the overall body of code,
* which comprises DREAM. By making a submission, submitter agrees
* to these terms. Furthermore, submitters acknowledge that the
* incorporation or modification of such submissions is entirely
* at the discretion of the moderators of the DREAM project.
* 
* DREAM links to the Libxml2 third party library. Please see 
* COPYING-libxml for the copyright information of Libxml2.
* =================================================================
*/

#ifndef DREAM_AVLTREECPP
#define DREAM_AVLTREECPP

#include "AVLTree.h"

namespace DREAM
{

/////////////////////////////////////////////////////////////////////////////
//
// AVLTreeNode
//
/////////////////////////////////////////////////////////////////////////////

template <class key_type, class item_type>
AVLTreeNode <key_type, item_type>::AVLTreeNode (key_type key, item_type item, AVLTreeNode <key_type, item_type>* parent) 
: first (key), second (item), left_ (NULL), right_ (NULL), parent_ (parent), depth_ (1), depth_count_ (0)
{
};

template <class key_type, class item_type>
AVLTreeNode <key_type, item_type>::~AVLTreeNode ()
{
        if (left_)
                delete left_;
        if (right_)
                delete right_;
}

template <class key_type, class item_type>
void AVLTreeNode <key_type, item_type>::calculate_depth ()
{
        uint left_depth = 0, right_depth = 0;

        if (left_)
                left_depth = left_->depth_;

        if (right_)
                right_depth = right_->depth_;

        if (left_depth == right_depth)
        {
                if (left_depth == 0)
                        depth_count_ = 1;
                else
                        depth_count_ = left_->depth_count_ + right_->depth_count_;

                depth_ = left_depth + 1;
        }
        else if (left_depth > right_depth)
        {
                depth_ = left_depth + 1;
                depth_count_ = left_->depth_count_;
        }
        else
        {
                depth_ = right_depth + 1;
                depth_count_ = right_->depth_count_;
        }

        if (parent_)
                parent_->calculate_depth ();
}

template <class key_type, class item_type>
inline uint AVLTreeNode <key_type, item_type>::depth ()
{
        return depth_;
}

template <class key_type, class item_type>
AVLTreeNode <key_type, item_type>* AVLTreeNode <key_type, item_type>::iter_next ()
{
        AVLTreeNode <key_type, item_type>* node_ptr;

        // Let's find the next largest element
        if (right_)
        {
                node_ptr = right_;

                // find leftmost child
                while (node_ptr->left_)
                        node_ptr = node_ptr->left_;

                return node_ptr;
        }
        else
        {
                if (parent_)
                        node_ptr = parent_;
                else
                        return NULL;

                while ((node_ptr->parent_) && (node_ptr->first < first))
                        node_ptr = node_ptr->parent_;

                return ((!node_ptr->parent_) && (node_ptr->first < first)) ? NULL : node_ptr;
        }
}

template <class key_type, class item_type>
AVLTreeNode <key_type, item_type>* AVLTreeNode <key_type, item_type>::iter_previous ()
{
        AVLTreeNode <key_type, item_type>* node_ptr;

        // Let's find the next smallest element
        if (left_)
        {
                node_ptr = left_;

                // find rightmost child
                while (node_ptr->right_)
                        node_ptr = node_ptr->right_;

                return node_ptr;
        }
        else
        {
                if (parent_)
                        node_ptr = parent_;
                else
                        return NULL;

                while ((node_ptr->parent_) && (node_ptr->first > first))
                        node_ptr = node_ptr->parent_;

                return ((!node_ptr->parent_) && (node_ptr->first > first)) ? NULL : node_ptr;
        }
}

template <class key_type, class item_type>
const AVLTreeNode <key_type, item_type>* AVLTreeNode <key_type, item_type>::iter_next () const
{
        const AVLTreeNode <key_type, item_type>* node_ptr;

        // Let's find the next largest element
        if (right_)
        {
                node_ptr = right_;

                // find leftmost child
                while (node_ptr->left_)
                        node_ptr = node_ptr->left_;

                return node_ptr;
        }
        else
        {
                if (parent_)
                        node_ptr = parent_;
                else
                        return NULL;

                while ((node_ptr->parent_) && (node_ptr->first < first))
                        node_ptr = node_ptr->parent_;

                return ((!node_ptr->parent_) && (node_ptr->first < first)) ? NULL : node_ptr;
        }
}

template <class key_type, class item_type>
const AVLTreeNode <key_type, item_type>* AVLTreeNode <key_type, item_type>::iter_previous () const
{
        const AVLTreeNode <key_type, item_type>* node_ptr;

        // Let's find the next smallest element
        if (left_)
        {
                node_ptr = left_;

                // find rightmost child
                while (node_ptr->right_)
                        node_ptr = node_ptr->right_;

                return node_ptr;
        }
        else
        {
                if (parent_)
                        node_ptr = parent_;
                else
                        return NULL;

                while ((node_ptr->parent_) && (node_ptr->first > first))
                        node_ptr = node_ptr->parent_;

                return ((!node_ptr->parent_) && (node_ptr->first > first)) ? NULL : node_ptr;
        }
}

template <class key_type, class item_type>
inline AVLTreeNode <key_type, item_type>* AVLTreeNode <key_type, item_type>::left ()
{
        return left_;
}

template <class key_type, class item_type>
inline const AVLTreeNode <key_type, item_type>* AVLTreeNode <key_type, item_type>::left () const
{
        return left_;
}

template <class key_type, class item_type>
inline void AVLTreeNode <key_type, item_type>::left (AVLTreeNode <key_type, item_type>* node_ptr)
{
        left_ = node_ptr;
}

template <class key_type, class item_type>
inline AVLTreeNode <key_type, item_type>* AVLTreeNode <key_type, item_type>::right ()
{
        return right_;
}

template <class key_type, class item_type>
inline const AVLTreeNode <key_type, item_type>* AVLTreeNode <key_type, item_type>::right () const
{
        return right_;
}

template <class key_type, class item_type>
inline void AVLTreeNode <key_type, item_type>::right (AVLTreeNode <key_type, item_type>* node_ptr)
{
        right_ = node_ptr;
}

template <class key_type, class item_type>
inline AVLTreeNode <key_type, item_type>* AVLTreeNode <key_type, item_type>::parent ()
{
        return parent_;
}

template <class key_type, class item_type>
inline const AVLTreeNode <key_type, item_type>* AVLTreeNode <key_type, item_type>::parent () const
{
        return parent_;
}

template <class key_type, class item_type>
inline void AVLTreeNode <key_type, item_type>::parent (AVLTreeNode <key_type, item_type>* node_ptr)
{
        parent_ = node_ptr;
}

template <class key_type, class item_type>
AVLTreeNode <key_type, item_type>& AVLTreeNode <key_type, item_type>::operator= (AVLTreeNode <key_type, item_type>& node)
{
        first = node.first;
        second = node.second;
        left_ = node.left_;
        right_ = node.right_;
        parent_ = node.parent_;
        return *this;
}

/////////////////////////////////////////////////////////////////////////////
//
// AVLTree
//
/////////////////////////////////////////////////////////////////////////////

template <class key_type, class item_type>
AVLTree <key_type, item_type>::AVLTree ()
: root_ptr_ (NULL), last_ptr_ (NULL), size_ (0) {};

template <class key_type, class item_type>
AVLTree <key_type, item_type>::~AVLTree ()
{
        if (root_ptr_)
                delete root_ptr_;
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::assign (const AVLTreeNode <key_type, item_type>* begin_node, const AVLTreeNode <key_type, item_type>* end_node)
{
        Const_Iterator <AVLTreeNode <key_type, item_type> > iter, begin_iter, end_iter;
        begin_iter = begin_node;
        end_iter = end_node;

        for (iter = begin_iter; iter != end_iter; iter++)
                insert (iter->first, iter->second);
}


template <class key_type, class item_type>
void AVLTree <key_type, item_type>::assign (Iterator <AVLTreeNode <key_type, item_type> >& begin_iter, Iterator <AVLTreeNode <key_type, item_type> >& end_iter)
{
        Iterator <AVLTreeNode <key_type, item_type> > iter;

        for (iter = begin_iter; iter != end_iter; iter++)
                insert (iter->first, iter->second);
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::assign (Const_Iterator <AVLTreeNode <key_type, item_type> >& begin_iter, Const_Iterator <AVLTreeNode <key_type, item_type> >& end_iter)
{
        Const_Iterator <AVLTreeNode <key_type, item_type> > iter;

        for (iter = begin_iter; iter != end_iter; iter++)
                insert (iter->first, iter->second);
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::balance (AVLTreeNode <key_type, item_type>* node_ptr)
{
        uint left = 0, right = 0;
        
        if (node_ptr->left_)
                left = node_ptr->left_->depth_;
        if (node_ptr->right_)
                right = node_ptr->right_->depth_;

        if (left > right + 1)
        {
                // Left subtree is too deep, balance right
                balance_right (node_ptr);
        }
        else if (right > left + 1)
        {
                // Right subtree is too deep, balance left
                balance_left (node_ptr);
        }

        if (node_ptr->parent_)
                balance (node_ptr->parent_);
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::balance_left (AVLTreeNode <key_type, item_type>* node_ptr)
{
        AVLTreeNode <key_type, item_type>* right_subtree = node_ptr->right_;
        AVLTreeNode <key_type, item_type>* middle_subtree = right_subtree->left_;
        AVLTreeNode <key_type, item_type>* parent_ptr = node_ptr->parent_;

        uint middle_depth = 0, right_depth = 0;
        if (middle_subtree)
                middle_depth = middle_subtree->depth_;
        if (right_subtree->right_)
                right_depth = right_subtree->right_->depth_;

        if (right_depth > middle_depth)
        {
                // Simple rotation
                node_ptr->right_ = middle_subtree;
                if (middle_subtree)
                        middle_subtree->parent_ = node_ptr;

                right_subtree->left_ = node_ptr;
                node_ptr->parent_ = right_subtree;

                if (parent_ptr)
                {
                        // Non-root node
                        if (parent_ptr->left_ == node_ptr)
                        {
                                // Node is the left child of its parent
                                parent_ptr->left_ = right_subtree;
                        }
                        else
                        {
                                // Node is the right child of its parent
                                parent_ptr->right_ = right_subtree;
                        }
                        right_subtree->parent_ = parent_ptr;
                }
                else
                {
                        // Root node
                        root_ptr_ = right_subtree;
                        right_subtree->parent_ = NULL;
                }

                node_ptr->calculate_depth ();
                balance (node_ptr);
        }
        else
        {
                // Middle tree has to be the new root, multiple rotations
                AVLTreeNode <key_type, item_type>* middle_left = middle_subtree->left_;
                AVLTreeNode <key_type, item_type>* middle_right = middle_subtree->right_;

                // Left side of the tree
                middle_subtree->left_ = node_ptr;
                node_ptr->parent_ = middle_subtree;

                node_ptr->right_ = middle_left;
                if (middle_left)
                        middle_left->parent_ = node_ptr;

                // Right side of the tree
                middle_subtree->right_ = right_subtree;
                if (right_subtree)
                        right_subtree->parent_ = middle_subtree;

                if (right_subtree)
                        right_subtree->left_ = middle_right;
                if (middle_right)
                        middle_right->parent_ = right_subtree;

                // Reconstruct tree
                if (parent_ptr)
                {
                        // Non-root node
                        if (parent_ptr->left_ == node_ptr)
                        {
                                // Node is the left child of its parent
                                parent_ptr->left_ = middle_subtree;
                        }
                        else
                        {
                                // Node is the right child of its parent
                                parent_ptr->right_ = middle_subtree;
                        }
                        middle_subtree->parent_ = parent_ptr;
                }
                else
                {
                        // Root node
                        root_ptr_ = middle_subtree;
                        middle_subtree->parent_ = NULL;
                }

                if (right_subtree)
                        right_subtree->calculate_depth ();
                node_ptr->calculate_depth ();

                if (right_subtree)
                        balance (right_subtree);
                balance (node_ptr);
        }
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::balance_right (AVLTreeNode <key_type, item_type>* node_ptr)
{
        AVLTreeNode <key_type, item_type>* left_subtree = node_ptr->left_;
        AVLTreeNode <key_type, item_type>* middle_subtree = left_subtree->right_;
        AVLTreeNode <key_type, item_type>* parent_ptr = node_ptr->parent_;

        uint middle_depth = 0, left_depth = 0;
        if (middle_subtree)
                middle_depth = middle_subtree->depth_;
        if (left_subtree->left_)
                left_depth = left_subtree->left_->depth_;

        if (left_depth > middle_depth)
        {
                // Simple rotation
                node_ptr->left_ = middle_subtree;
                if (middle_subtree)
                        middle_subtree->parent_ = node_ptr;

                left_subtree->right_ = node_ptr;
                node_ptr->parent_ = left_subtree;

                if (parent_ptr)
                {
                        // Non-root node
                        if (parent_ptr->left_ == node_ptr)
                        {
                                // Node is the left child of its parent
                                parent_ptr->left_ = left_subtree;
                        }
                        else
                        {
                                // Node is the right child of its parent
                                parent_ptr->right_ = left_subtree;
                        }
                        left_subtree->parent_ = parent_ptr;
                }
                else
                {
                        // Root node
                        root_ptr_ = left_subtree;
                        left_subtree->parent_ = NULL;
                }

                node_ptr->calculate_depth ();
                balance (node_ptr);
        }
        else
        {
                // Middle tree has to be the new root, multiple rotations
                AVLTreeNode <key_type, item_type>* middle_left = middle_subtree->left_;
                AVLTreeNode <key_type, item_type>* middle_right = middle_subtree->right_;

                // Right side of the tree
                middle_subtree->right_ = node_ptr;
                node_ptr->parent_ = middle_subtree;

                node_ptr->left_ = middle_right;
                if (middle_right)
                        middle_right->parent_ = node_ptr;

                // Left side of the tree
                middle_subtree->left_ = left_subtree;
                if (left_subtree)
                        left_subtree->parent_ = middle_subtree;

                if (left_subtree)
                        left_subtree->right_ = middle_left;
                if (middle_left)
                        middle_left->parent_ = left_subtree;

                // Reconstruct tree
                if (parent_ptr)
                {
                        // Non-root node
                        if (parent_ptr->left_ == node_ptr)
                        {
                                // Node is the left child of its parent
                                parent_ptr->left_ = middle_subtree;
                        }
                        else
                        {
                                // Node is the right child of its parent
                                parent_ptr->right_ = middle_subtree;
                        }
                        middle_subtree->parent_ = parent_ptr;
                }
                else
                {
                        // Root node
                        root_ptr_ = middle_subtree;
                        middle_subtree->parent_ = NULL;
                }

                if (left_subtree)
                        left_subtree->calculate_depth ();
                node_ptr->calculate_depth ();

                if (left_subtree)
                        balance (left_subtree);
                balance (node_ptr);
        }
}

template <class key_type, class item_type>
AVLTreeNode <key_type, item_type>* AVLTree <key_type, item_type>::begin ()
{
        if (!root_ptr_)
                return NULL;

        AVLTreeNode <key_type, item_type>* node_ptr = root_ptr_;

        while (node_ptr->left_)
                node_ptr = node_ptr->left_;

        return node_ptr;
}

template <class key_type, class item_type>
const AVLTreeNode <key_type, item_type>* AVLTree <key_type, item_type>::begin () const
{
        if (!root_ptr_)
                return NULL;

        AVLTreeNode <key_type, item_type>* node_ptr = root_ptr_;

        while (node_ptr->left_)
                node_ptr = node_ptr->left_;

        return node_ptr;
}

template <class key_type, class item_type>
inline void AVLTree <key_type, item_type>::clear ()
{
        if (root_ptr_)
        {
                delete root_ptr_;
                size_ = 0;
                root_ptr_ = NULL;
        }
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::destroy ()
{
        if (root_ptr_)
        {
                Iterator <AVLTreeNode <key_type, item_type> > iter;
                for (iter = begin (); iter != end (); iter++)
                        delete iter->second;

                delete root_ptr_;
                size_ = 0;
                root_ptr_ = NULL;
        }
}

template <class key_type, class item_type>
inline bool AVLTree <key_type, item_type>::empty ()
{
        return (size_ == 0) ? true : false;
}

template <class key_type, class item_type>
inline bool AVLTree <key_type, item_type>::empty () const
{
        return (size_ == 0) ? true : false;
}

template <class key_type, class item_type>
inline AVLTreeNode <key_type, item_type>* AVLTree <key_type, item_type>::end ()
{
        return NULL;
}

template <class key_type, class item_type>
inline const AVLTreeNode <key_type, item_type>* AVLTree <key_type, item_type>::end () const
{
        return NULL;
}

template <class key_type, class item_type>
inline void AVLTree <key_type, item_type>::erase (key_type key)
{
        erase (find (key));
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::erase (Iterator <AVLTreeNode <key_type, item_type> >& iter)
{
        AVLTreeNode <key_type, item_type>* parent_ptr = iter->parent_;
        AVLTreeNode <key_type, item_type>* left_ptr = iter->left_;
        AVLTreeNode <key_type, item_type>* right_ptr = iter->right_;
        --size_;

        // No children
        if ((!left_ptr) && (!right_ptr))
        {
                erase_leaf (*iter, parent_ptr);
        }
        else if ((!left_ptr) || (!right_ptr))
        {
                // Only one child
                if (!left_ptr)
                {
                        erase_right_child (*iter, parent_ptr, right_ptr);
                }
                else
                {
                        erase_left_child (*iter, parent_ptr, left_ptr);
                }
        }
        else
        {
                erase (*iter, parent_ptr, left_ptr, right_ptr);
        }
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::erase (AVLTreeNode <key_type, item_type>* node_ptr, 
                AVLTreeNode <key_type, item_type>* parent_ptr, AVLTreeNode <key_type, item_type>* left_ptr,
                AVLTreeNode <key_type, item_type>* right_ptr)
{
        // Node has two children
        if (parent_ptr)
        {
                // Non-root node
                if (parent_ptr->left_ == node_ptr)
                {
                        // The node is the left child of its parent
                        // Could start with the larger node as well
                        AVLTreeNode <key_type, item_type>* new_node_ptr = 
                                get_smaller_node (node_ptr, left_ptr, right_ptr);

                        // Reconstruct tree
                        parent_ptr->left_ = new_node_ptr;
                        new_node_ptr->parent_ = parent_ptr;
                        new_node_ptr->calculate_depth ();
                        balance (new_node_ptr);
                }
                else
                {
                        // The node is the right child of its parent
                        // Could start with the smaller node as well
                        AVLTreeNode <key_type, item_type>* new_node_ptr = 
                                get_larger_node (node_ptr, left_ptr, right_ptr);

                        // Reconstruct tree
                        parent_ptr->right_ = new_node_ptr;
                        new_node_ptr->parent_ = parent_ptr;
                        new_node_ptr->calculate_depth ();
                        balance (new_node_ptr);
                }
        }
        else
        {
                // Root node
                // Could start with the larger node as well
                AVLTreeNode <key_type, item_type>* new_node_ptr = 
                        get_smaller_node (node_ptr, left_ptr, right_ptr);

                // Reconstruct tree
                root_ptr_ = new_node_ptr;
                root_ptr_->parent_ = NULL;
                root_ptr_->calculate_depth ();
                balance (root_ptr_);
        }

        // Prevent recursive delete
        node_ptr->left_ = NULL;
        node_ptr->right_ = NULL;
        delete node_ptr;
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::erase_leaf (AVLTreeNode <key_type, item_type>* node_ptr, AVLTreeNode <key_type, item_type>* parent_ptr)
{
        if (parent_ptr)
        {
                // Simple leaf
                if (parent_ptr->left_ == node_ptr)
                {
                        // leaf is left child
                        parent_ptr->left_ = NULL;
                }
                else
                        // leaf is right child
                        parent_ptr->right_ = NULL;

                parent_ptr->calculate_depth ();
                balance (parent_ptr);
        }
        else
                root_ptr_ = NULL;

        delete node_ptr;
        return;
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::erase_left_child (AVLTreeNode <key_type, item_type>* node_ptr, 
        AVLTreeNode <key_type, item_type>* parent_ptr, AVLTreeNode <key_type, item_type>* left_ptr)
{
        if (parent_ptr)
        {
                // Left child
                // Find out whether the node pointed to by iter is a left or right child
                if (parent_ptr->left_ == node_ptr)
                {
                        // Left child
                        parent_ptr->left_ = left_ptr;
                }
                else
                {
                        // Right child
                        parent_ptr->right_ = left_ptr;
                }
        }
        else
        {
                root_ptr_ = left_ptr;
        }

        left_ptr->parent_ = parent_ptr;
        left_ptr->calculate_depth ();
        balance (left_ptr);
        // Prevent recursive delete
        node_ptr->left_ = NULL;
        delete node_ptr;
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::erase_right_child (AVLTreeNode <key_type, item_type>* node_ptr, 
        AVLTreeNode <key_type, item_type>* parent_ptr, AVLTreeNode <key_type, item_type>* right_ptr)
{
        if (parent_ptr)
        {
                // Right child
                // Find out whether the node pointed to by iter is a left or right child
                if (parent_ptr->left_ == node_ptr)
                {
                        // Left child
                        parent_ptr->left_ = right_ptr;
                }
                else
                {
                        // Right child
                        parent_ptr->right_ = right_ptr;
                }
        }
        else
        {
                root_ptr_ = right_ptr;
        }

        right_ptr->parent_ = parent_ptr;
        right_ptr->calculate_depth ();
        balance (right_ptr);
        // Prevent recursive delete
        node_ptr->right_ = NULL;
        delete node_ptr;
}

template <class key_type, class item_type>
AVLTreeNode <key_type, item_type>* AVLTree <key_type, item_type>::find (const key_type& key)
{
        if (!root_ptr_)
                return NULL;

        AVLTreeNode <key_type, item_type>* node_ptr = root_ptr_;

        // Non-recursive implementation for faster performance
        while (((node_ptr->first < key) && (node_ptr->right_)) || ((key < node_ptr->first) && (node_ptr->left_)))
        {
                node_ptr = (node_ptr->first < key) ? node_ptr->right_ : node_ptr->left_;
        }

        return (node_ptr->first == key) ? node_ptr : NULL;
}

template <class key_type, class item_type>
const AVLTreeNode <key_type, item_type>* AVLTree <key_type, item_type>::find (const key_type& key) const
{
        if (!root_ptr_)
                return NULL;

        AVLTreeNode <key_type, item_type>* node_ptr = root_ptr_;

        // Non-recursive implementation for faster performance
        while (((node_ptr->first < key) && (node_ptr->right_)) || ((key < node_ptr->first) && (node_ptr->left_)))
        {
                node_ptr = (node_ptr->first < key) ? node_ptr->right_ : node_ptr->left_;
        }

        return (node_ptr->first == key) ? node_ptr : NULL;
}

template <class key_type, class item_type>
AVLTreeNode <key_type, item_type>* AVLTree <key_type, item_type>::get_smaller_node (AVLTreeNode <key_type, item_type>* node_ptr,
        AVLTreeNode <key_type, item_type>* left_ptr, AVLTreeNode <key_type, item_type>* right_ptr)
{
        // Get the next smaller element
        AVLTreeNode <key_type, item_type>* new_node_ptr = node_ptr->left_;

        if (new_node_ptr->right_)
        {
                // Find rightmost child
                while (new_node_ptr->right_)
                        new_node_ptr = new_node_ptr->right_;

                if (new_node_ptr->left_)
                {
                        new_node_ptr->parent_->right_ = new_node_ptr->left_;
                        new_node_ptr->left_->parent_ = new_node_ptr->parent_;
                        new_node_ptr->left_->calculate_depth ();
                        balance (new_node_ptr->left_);
                }
                else
                {
                        new_node_ptr->parent_->right_ = NULL;
                        new_node_ptr->parent_->calculate_depth ();
                        balance (new_node_ptr->parent_);
                }

                new_node_ptr->left_ = left_ptr;
                left_ptr->parent_ =new_node_ptr;
        }

        // Reconstruct tree
        new_node_ptr->right_ = right_ptr;
        right_ptr->parent_ = new_node_ptr;

        return new_node_ptr;
}

template <class key_type, class item_type>
AVLTreeNode <key_type, item_type>* AVLTree <key_type, item_type>::get_larger_node (AVLTreeNode <key_type, item_type>* node_ptr,
        AVLTreeNode <key_type, item_type>* left_ptr, AVLTreeNode <key_type, item_type>* right_ptr)
{
        // Get the next larger element
        AVLTreeNode <key_type, item_type>* new_node_ptr = node_ptr->right_;

        if (new_node_ptr->left_)
        {
                // Find rightmost child
                while (new_node_ptr->left_)
                        new_node_ptr = new_node_ptr->left_;

                if (new_node_ptr->right_)
                {
                        new_node_ptr->parent_->left_ = new_node_ptr->right_;
                        new_node_ptr->right_->parent_ = new_node_ptr->parent_;
                        new_node_ptr->right_->calculate_depth ();
                        balance (new_node_ptr->right_);
                }
                else
                {
                        new_node_ptr->parent_->left_ = NULL;
                        new_node_ptr->parent_->calculate_depth ();
                        balance (new_node_ptr->parent_);
                }

                new_node_ptr->right_ = right_ptr;
                right_ptr->parent_ = new_node_ptr;
        }

        // Reconstruct tree
        left_ptr->parent_ = new_node_ptr;
        new_node_ptr->left_ = left_ptr;

        return new_node_ptr;
}

template <class key_type, class item_type>
void AVLTree <key_type, item_type>::insert (key_type key, item_type item)
{
        ++size_;
        if (root_ptr_)
        {
                AVLTreeNode <key_type, item_type>* node_ptr = root_ptr_;

                // Prefer to grow to the left if keys equal
                // Non-recursive implementation for faster performance
                while (((node_ptr->first < key) && (node_ptr->right_)) || ((key < node_ptr->first) && (node_ptr->left_)))
                        node_ptr = (node_ptr->first < key) ? node_ptr->right_ : node_ptr->left_;

                // Found leaf
                if (node_ptr->first == key)
                        node_ptr->second = item;
                else if (node_ptr->first < key)
                {
                        node_ptr->right_ = new AVLTreeNode <key_type, item_type> (key, item, node_ptr);
                        node_ptr->right_->calculate_depth ();
                        if (node_ptr == last_ptr_)
                                last_ptr_ = last_ptr_->right_;
                        balance (node_ptr->right_);
                }
                else
                {
                        node_ptr->left_ = new AVLTreeNode <key_type, item_type> (key, item, node_ptr);
                        node_ptr->left_->calculate_depth ();
                        balance (node_ptr->left_);
                }
        }
        else
        {
                // Create root node
                root_ptr_ = new AVLTreeNode <key_type, item_type> (key, item);
                last_ptr_ = root_ptr_;
                root_ptr_->calculate_depth ();
                balance (root_ptr_);
        }
}

template <class key_type, class item_type>
inline AVLTreeNode <key_type, item_type>* AVLTree <key_type, item_type>::last ()
{
        return last_ptr_;
}

template <class key_type, class item_type>
inline const AVLTreeNode <key_type, item_type>* AVLTree <key_type, item_type>::last () const
{
        return last_ptr_;
}

template <class key_type, class item_type>
item_type& AVLTree <key_type, item_type>::operator [] (uint i)
{
        // This function is NOT similar to std::map, but to std::vector
        // Quite inefficient...
        Iterator <AVLTreeNode <key_type, item_type> > iter;
        iter = begin ();

        uint j;
        for (j = 0; j < i; j++)
                ++iter;

        return iter->second;
}

template <class key_type, class item_type>
const item_type& AVLTree <key_type, item_type>::operator [] (uint i) const
{
        // This function is NOT similar to std::map, but to std::vector
        // Quite inefficient...
        Const_Iterator <AVLTreeNode <key_type, item_type> > iter;
        iter = begin ();

        uint j;
        for (j = 0; j < i; j++)
                ++iter;

        return iter->second;
}

template <class key_type, class item_type>
inline uint AVLTree <key_type, item_type>::size () const
{
        return size_;
}

};

#endif

---