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

template <class T> class AVL_Tree
{
public:
    struct Node
    {
        T key;
        Node * left, * right;
        int bal;
    };

    class NodeStor
    {
    public:
        virtual Node * get() = 0;
        virtual void put ( Node * ) = 0;
    };
private:
    Node * root;
    NodeStor * stor;

    Здесь реализация следующих функций:

    static const T & add ( const T & x, Node * & p, bool & h, NodeStor * stor )...

    static bool delet ( const T & x, Node * & p, NodeStor * stor )...

    static void delAll ( Node * p, NodeStor * stor )...

    static unsigned countItems ( const Node * p )...

    static bool test ( const Node * p )...

public:
    AVL_Tree ( NodeStor * p = 0 ) : root ( 0 ), stor ( p ) {}

    ~AVL_Tree ()
    {
        delAll ( root, stor );
    }

    const T & add ( const T & x )
    {
        bool h;
        return add ( x, root, h, stor );
    }

    void del ( const T & x )
    {
        delet ( x, root, stor );
    }

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

    unsigned countItems() const
    {
        return countItems ( root );
    }

    bool test() const
    {
        return test ( root );
    }
};

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

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

template <class T> class AVL_TreeNodeStor : public AVL_Tree<T>::NodeStor
{
    AVL_Tree<T>::Node * data;
public:
    AVL_TreeNodeStor() : data(0) {}

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

    virtual AVL_Tree<T>::Node * get()
    {
        if ( data )
        {
            AVL_Tree<T>::Node * p = data;
            data = p->left;
            return p;
        }
        else
            return new AVL_Tree<T>::Node;
    }

    virtual void put ( AVL_Tree<T>::Node * p )
    {
        p->left = data;
        data = p;
    }

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

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