3.cpp

#include <iostream>
using namespace std;

struct CNode {
    CNode(int k) :
        key(k), left(NULL), right(NULL), height(1)
    { 
    }

    int key;
    int height;
    CNode* left;
    CNode* right;
};

int Height(CNode* node)
{
    return node ? node->height : 0;
}

int BalanceFactor(CNode* node)
{
    return Height(node->right) - Height(node->left);
}

void FixHeight(CNode* node)
{
    int hl = Height(node->left);
    int hr = Height(node->right);
    node->height = (hl > hr ? hl : hr) + 1;
}

CNode* RotateRight(CNode* p) // правый поворот вокруг p
{
    if (p == NULL)
        return NULL;

    CNode *tmp = p->left;
    p->left = tmp->right;
    tmp->right = p;
    FixHeight(p);
    FixHeight(tmp);
    return tmp;
}

CNode* RotateLeft(CNode *p) // левый поворот вокруг p
{
    if (p == NULL)
        return NULL;

    CNode *tmp = p->right;
    p->right = tmp->left;
    tmp->left = p;
    FixHeight(p);
    FixHeight(tmp);
    return tmp;
}

CNode* Balance(CNode *p)
{
    if (p == NULL)
        return NULL;

    FixHeight(p);
    if( BalanceFactor(p) > 1 )
    {
        if( BalanceFactor(p->right) < 0 )
            p->right = RotateRight(p->right);
        return RotateLeft(p);
    }
    if( BalanceFactor(p) < -1 )
    {
        if( BalanceFactor(p->left) > 0  )
            p->left = RotateLeft(p->left);
        return RotateRight(p);
    }
    return p;
}

CNode* Insert(CNode* root, int key)
{
    if( root == NULL ) 
        return new CNode(key);

    if( key < root->key )
        root->left = Insert(root->left,key);
    else
        root->right = Insert(root->right,key);
    return Balance(root);
}

CNode* FindMin(CNode* p)
{
    return p->left ? FindMin(p->left) : p;
}

CNode* RemoveMin(CNode* p)
{
    if( p->left==0 )
        return p->right;
    p->left = RemoveMin(p->left);
    return Balance(p);
}

CNode* Remove(CNode* p, int k)
{
    if( !p ) return 0;
    if( k < p->key )
        p->left = Remove(p->left,k);
    else if( k > p->key )
        p->right = Remove(p->right,k);	
    else //  k == p->key 
    {
        CNode* q = p->left;
        CNode* r = p->right;
        delete p;
        if( !r ) return q;
        CNode* min = FindMin(r);
        min->right = RemoveMin(r);
        min->left = q;
        return Balance(min);
    }
    return Balance(p);
}

void Delete(CNode* node)
{
	if (!node) return;
	Delete(node->left);
	Delete(node->right);
	delete node;
}

int main()
{
	CNode* root = 0;

	while( true ) {
		int key = 0;
		std::cin >> key;
		if( std::cin.eof() ) {
			break;
		}
		if( key >= 0 ) {
			root = Insert(root, key);
		} else {
			root = Remove(root, -key);
		}
	}

	std::cout << Height(root);

	Delete(root);

	return 0;
}