Шаблон AVL_Tree предназначен для представления сбалансированного бинарного дерева, предложенного советскими учёными Г.М. Адельсоном-Вельским и Е.М. Ландисом в 1962 году. При разработке этого шаблона использовалась книга Н. Вирта "Алгоритмы и структуры данных":

template <typename K, typename D = Void> class AVL_Tree
{
public:
    struct Node
    {
        K key;
        D data;
        Node * left, * right;
        int bal;
    };

    class NodeStor
    {
    public:
        virtual Node * get() = 0;
        virtual void put ( Node * ) = 0;
    };
private:
    Node * root;
    NodeStor & stor;
    unsigned count;
    bool isDel;
// Здесь реализация функций:
	.....
public:
    explicit AVL_Tree ( NodeStor & s ) : root ( 0 ), stor ( s ), count ( 0 ) {}

    ~AVL_Tree ()
    {
        delAll ( root );
    }

    D & add ( const K & x, const D & d )
    {
        bool h;
        return add ( x, d, root, h );
    }

    D & add ( const K & x )
    {
        D d;
        bool h;
        return add ( x, d, root, h );
    }

    bool del ( const K & x )
    {
        isDel = false;
        delet ( x, root );
        return isDel;
    }

    D * find ( const K & x )
    {
        Node * p = root;
        while ( p )
        {
            if ( p->key > x )
                p = p->left;
            else
            if ( p->key < x )
                p = p->right;
            else
                return & p->data;
        }
        return 0;
    }

    unsigned size() const
    {
        return count;
    }

    bool test() const
    {
        if ( count != countItems() )
            return false;
        return test ( root );
    }
};

Функции-члены add добавляют новый элемент, если его ещё не было в дереве, или меняют его данные, если элемент с таким ключём уже там был. Функция-член del удаляет элемент с указанным ключём. Функция-член find возвращает указатель на данные элемента с указанным ключём, если он есть, и 0 - в противном случае. Функция-член size возвращает количество элементов в дереве. Функция-член test проверяет дерево на корректность.

Класс AVL_TreeNodeStor является хранилищем для узлов дерева, из которого их можно брать и возвращать обратно:

template <typename K, typename D = Void> 
class AVL_TreeNodeStor : public AVL_Tree<K, D>::NodeStor
{
    typename AVL_Tree<K, D>::Node * ptr;
public:
    AVL_TreeNodeStor() : ptr(0) {}

    ~AVL_TreeNodeStor()
    {
        while ( ptr )
        {
            AVL_Tree::Node * p = ptr->left;
            delete ptr;
            ptr = p;
        }
    }

    virtual typename AVL_Tree<K, D>::Node * get()
    {
        if ( ptr )
        {
            AVL_Tree<K, D>::Node * p = ptr;
            ptr = p->left;
            return p;
        }
        else
            return new AVL_Tree<K, D>::Node;
    }

    virtual void put ( typename AVL_Tree<K, D>::Node * p )
    {
        p->left = ptr;
        ptr = p;
    }

    const D * find ( const K & x ) const
    {
        const AVL_Tree<K, D>::Node * p = ptr;
        while ( p )
        {
            if ( p->key == x ) return & p->data;
            p = p->left;
        }
        return 0;
    }

    const D * first () const
    {
        return ptr ? & ptr->data : 0;
    }
};

Исходники находятся в файле AVL_Tree.h.