Cod sursa(job #2418270)

Utilizator mihai2003LLL LLL mihai2003 Data 4 mai 2019 15:20:46
Problema Heapuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.22 kb
#include <iostream>
#include <fstream>

class Node
{
public:
    Node *left,*right;
    int key,_height;
    int height()
    {
        if(this==NULL)
            return 0;
        return _height;
    }
    Node(int k)
    {
        key=k;
        _height=1;
        left=right=NULL;
    }
};

Node *right_rotate(Node * y)
{
    Node * aux=y->left;
    Node * t2=aux->right;
    aux->right=y;
    y->left=t2;
    y->_height=std::max(y->left->height(),y->right->height())+1;
    aux->_height=std::max(aux->left->height(),aux->right->height())+1;
    return aux;
}

Node *left_rotate(Node *x)
{
    Node *y=x->right;
    Node *t2=y->left;
    y->left=x;
    x->right=t2;
    x->_height=std::max(x->left->height(),x->right->height())+1;
    y->_height=std::max(y->left->height(),y->right->height())+1;
    return y;
}

int get_balance(Node *n)
{
    if(n==NULL)
        return 0;
    return n->left->height()-n->right->height();
}

Node *insert(Node *node,int key)
{
    if(node==NULL)
        return new Node(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;
    node->_height =1+std::max(node->left->height(),node->right->height());
    int balance = get_balance(node);
    if (balance > 1 && key < node->left->key)
        return right_rotate(node);
    if (balance < -1 && key > node->right->key)
        return left_rotate(node);
    if (balance > 1 && key > node->left->key)
    {
        node->left = left_rotate(node->left);
        return right_rotate(node);
    }
    if (balance < -1 && key < node->right->key)
    {
        node->right = right_rotate(node->right);
        return left_rotate(node);
    }
    return node;
}

Node * minValueNode(Node* node)
{
    Node* current = node;
    while (current->left != NULL)
        current = current->left;
    return current;
}

Node* deleteNode(Node* root, int key)
{
    if (root == NULL)
        return root;
    if ( key < root->key )
        root->left = deleteNode(root->left, key);
    else if( key > root->key )
        root->right = deleteNode(root->right, key);
    else
    {
        if( (root->left == NULL) ||
                (root->right == NULL) )
        {
            Node *temp = root->left ?
                         root->left :
                         root->right;
            if (temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else
                *root = *temp;
            delete temp;
        }
        else
        {
            Node* temp = minValueNode(root->right);
            root->key = temp->key;
            root->right = deleteNode(root->right,
                                     temp->key);
        }
    }
    if (root == NULL)
        return root;
    root->_height = 1 + std::max(root->left->height(),
                           root->right->height());
    int balance = get_balance(root);
    if (balance > 1 &&
            get_balance(root->left) >= 0)
        return right_rotate(root);
    if (balance > 1 &&
            get_balance(root->left) < 0)
    {
        root->left = left_rotate(root->left);
        return right_rotate(root);
    }

    if (balance < -1 &&
            get_balance(root->right) <= 0)
        return left_rotate(root);
    if (balance < -1 &&
            get_balance(root->right) > 0)
    {
        root->right = right_rotate(root->right);
        return left_rotate(root);
    }

    return root;
}
std::ifstream in("heapuri.in");
std::ofstream out("heapuri.out");
#include <vector>
std::vector<int>v;
int main()
{
    Node *bst=NULL;
    int n,t,aux;
    in>>n;
    for(int i=1;i<=n;i++){
        in>>t;
        if(t==3)
            out<<minValueNode(bst)->key<<'\n';
        else{
            in>>aux;
            if(t==1){
                if(bst==NULL)
                    bst=insert(bst,aux);
                else
                    bst=insert(bst,aux);
                v.push_back(aux);
            }
            else{
                bst=deleteNode(bst,v[aux-1]);

            }
        }
    }

    return 0;
}