AVLTree

#include <iostream>

using namespace std;

struct AVLTree{

    int position;
    int key;
    int depth;
    AVLTree* left;
    AVLTree* right;

    AVLTree() :
    position(0),
    key(0),
    depth(0),
    left( nullptr ),
    right( nullptr )
    {}

    explicit AVLTree( int key );

};

AVLTree::AVLTree( int key ) :
position( 0 ),
key( key ),
depth( 1 ),
left( nullptr ),
right( nullptr )
{}

int Number_of_higher ( AVLTree* root ) {
    if( root == nullptr )
        return 0;
    return Number_of_higher( root->left ) + Number_of_higher( root->right ) + 1;

}

void update_depth( AVLTree*& root ) {

    if( root == nullptr ) {
        return;
    } else {
        if( root->left != nullptr && root->right != nullptr ){
            if( root->left->depth > root->right->depth ) {
                root->depth = root->left->depth + 1;
            } else {
                root->depth = root->right->depth + 1;
            }
        }
    }

}

int safe_depth( AVLTree* root ) {
    if( root == nullptr ) {
        return 0;
    } else {
        return root->depth;
    }
}

AVLTree* balance( AVLTree*& tree ) {
    if( tree == nullptr ) {
        return nullptr;
    }
    int imbalance = 0;
    imbalance = safe_depth( tree->left ) - safe_depth( tree->right );

    if( imbalance < -1 ) {
        AVLTree* a = tree;
        AVLTree* b = tree->right;
        AVLTree* L = tree->left;
        AVLTree* c = b->left;
        AVLTree* R = b->right;
        if( c->depth <= R->depth ) {
            b->left = a;
            a->left = L;
            a->right = c;
            update_depth( a );
            update_depth( R );
            return R;
        } else {
            AVLTree* c1 = c->left;
            AVLTree* c2 = c->right;
            a->right = c1;
            c->left = a;
            b->left = c2;
            c->right = b;
            update_depth( a );
            update_depth( b );
            update_depth( c );
            return c;
        }
    } else if( imbalance > 1 ) {
        AVLTree* a = tree;
        AVLTree* b = tree->right;
        AVLTree* L = tree->left;
        AVLTree* c = b->left;
        AVLTree* R = b->right;
        if( c->depth <= L->depth ) {
            b->right = a;
            a->left = c;
            a->right = R;
            update_depth( a );
            update_depth( R );
        } else {
            AVLTree* M = c->right;
            AVLTree* N = c->right;
            a->left = N;
            c->right = a;
            c->left = b;
            b->right = M;
            update_depth( a );
            update_depth( b );
            update_depth( c );
        }
        return nullptr;
    } else {
        return tree;
    }

}

void update_position( AVLTree*& root ) {
    if( root == nullptr ) {
        return;
    }
    update_position( root->left );
    update_position( root->right );
    root->position++;
}

AVLTree* insert( AVLTree*& root, AVLTree* current ) {

    if( root == nullptr ){
        root = current;
        return root;
    }

    if( root->key > current->key ) {
        current->position += 1 + Number_of_higher( root->right );
        insert( root->left, current );
    } else {
        root->position++;
        update_position( root->left );
        insert( root->right, current );
    }

    update_depth( root );
    balance( root );
    return root;
}

void update_remove_position( AVLTree*& root ) {
    if( root == nullptr ) {
        return;
    }
    update_remove_position( root->left );
    update_remove_position( root->right );
    root->position--;
}

AVLTree* findmin( AVLTree* root ) {
    if( root->left != nullptr ) {
        return findmin(root->left);
    } else {
        return root;
    }
}

AVLTree* removemin( AVLTree*& root ) {

    if( root->left == nullptr ) {
        return root->right;
    }

    root->left = removemin( root->left );

    return balance( root );
}

AVLTree* remove( AVLTree*& root, int position ) {
    if( root == nullptr ) {
        return nullptr;
    }

    if( root->position > position ) {
        root->position--;
        update_remove_position( root-> left );
        root->right =  remove( root->right, position );
    } else if( root->position < position ) {
        root->left = remove( root->left, position );
    } else {

        update_remove_position( root->left );

        AVLTree* left = root->left;
        AVLTree* right = root->right;

        delete root;
        root = NULL;

        if( right == nullptr ) {
            return left;
        }

        AVLTree* min = findmin( right );
        min->right = removemin( right );
        min->left = left;
        update_depth( root );
        return balance( min );

    }

    update_depth( root );
    return balance( root );
}

void deletetree( AVLTree*& root ) {
    if( root == nullptr )
        return;

    deletetree( root->left );
    deletetree( root->right );

    delete root;
    root = NULL;
}

int main() {
    int n = 0;
    int height = 0;
    int com = 0;


    cin >> n;
    cin >> com >> height;
    cout<<" ";
    AVLTree* root = new AVLTree ( height );

    cout << root->position << " ";

    for( int i = 1; i < n; i++ ) {

        cin >> com;
        cin >> height;

        if( com == 2 ) {
            root = remove(root, height);
        } else {
            AVLTree* current = new AVLTree( height );
            insert( root, current );
            cout << current->position << " ";
        }

    }

    deletetree( root );

    return 0;
}