AVLTreeDraft

#include <algorithm>
#include <assert.h>
#include <iostream>

// АВЛ-дерево с целочисленными ключами.
class CAVLTree {
public:
    CAVLTree() : root( nullptr ) {}
    bool Has( int key ) const;
    void Add( int key );
    void Remove( int key );

private:
    // Узел дерева. Пока без Count.
    struct CAVLTreeNode {
        int Key;
        int Height;
        CAVLTreeNode* Left;
        CAVLTreeNode* Right;
        CAVLTreeNode( int key ) : Key( key ), Height( 1 ), Left( nullptr ), Right( nullptr ) {}
    };

    CAVLTreeNode* root;

    static void add( CAVLTreeNode*& node, int key );
    static void fixupBalance( CAVLTreeNode*& node );
    static int height( const CAVLTreeNode* node ) { return node == nullptr ? 0 : node->Height; }
    static int balance( const CAVLTreeNode* node );
    static void fixHeight( CAVLTreeNode* node );
    static int rotateLeft( CAVLTreeNode* node );
    static int rotateRight( CAVLTreeNode* node );
};

void CAVLTree::Add( int key )
{
    add( root, key );
}

// Рекурсивное добавление узла в поддерево.
// node передается по ссылке, чтобы обновить указатель в случае поворота или добавления нового узла.
void CAVLTree::add( CAVLTreeNode*& node, int key )
{
    if( node == nullptr ) {
        node = new CAVLTreeNode( key );
        return;
    }
    // Рекурсивно добавляем узел.
    if( node->Key < key ) {
        add( node->Right, key );
    } else {
        add( node->Left, key );
    }
    // Восстановим баланс текущего узла.
    fixupBalance( node );
}

int CAVLTree::balance( const CAVLTreeNode* node )
{
    assert( node != nullptr );
    return height( node->Left ) - height( node->Right );
}

void CAVLTree::fixupBalance( CAVLTreeNode*& node )
{
    assert( node != nullptr );

    if( balance( node ) == 2 ) {
        if( balance( node->Left ) == -1 ) {
            rotateLeft( node->Left );
        }
        rotateRight( node );
    } else if( height( node->Left ) - height( node->Right ) == -2 ) {
        if( balance( node->Right ) == 1 ) {
            rotateRight( node->Right );
        }
        rotateLeft( node );
    } else {
        fixHeight( node );
    }
}

void CAVLTree::fixHeight( CAVLTreeNode* node )
{
    node->Height = std::max( height( node->Left ), height( node->Right ) ) + 1;
}

int main()
{
    CAVLTree tree;
    return 0;
}