Treap

#include <bits/stdc++.h>

using namespace std;

struct Treap
{
    int key, p;
    Treap *left, *right;
};

Treap* New_node(int x)
{
    Treap* nod = new Treap;
    nod->key = x;
    nod->p = rand();
    nod->left = nod->right = NULL;
    return nod;
}

Treap* rot_right(Treap* y)
{
    Treap *x = y->left;
    y->left = x->right;
    x->right = y;
    return x;
}

Treap* rot_left(Treap* y)
{
    Treap *x = y->right;
    y->right = x->left;
    x->left = y;
    return x;
}

void Insert(Treap* &node, int key)
{
    if(node == NULL)
        node = New_node(key);
    else
    {
        if(key < node->key)
        {
            Insert(node->left, key);
            if(node->p < node->left->p)
                node = rot_right(node);
        }
        else
        {
            Insert(node->right, key);
            if(node->p < node->right->p)
                node = rot_left(node);
        }
    }
}

Treap* Search(Treap* node, int key)
{
    if(node->key == key)
        return node;
    if(key < node->key)
        Search(node->left, key);
    else
        Search(node->right, key);
}

Treap* Delete(Treap* node, int key)
{
    if(!node)
        return node;
    if(key < node->key)
        node->left = Delete(node->left, key);
    else if(key > node->key)
        node->right = Delete(node->right, key);
    else if(!node->left || !node->right)
    {
        Treap* aux = (node->left ? node->left : node->right);
        delete node;
        node = aux;
    }
    else if(node->left->p > node->right->p)
    {
        node = rot_right(node);
        node->right = Delete(node->right, key);
    }
    else
    {
        node = rot_left(node);
        node->left = Delete(node->left, key);
    }
    return node;
}

void Inorder(Treap* node)
{
    if(node)
    {
        Inorder(node->left);
        cout << "Nodul curent este: " << node->key << " " << node->p << " ";
        if(node->left)
            cout << "Fiul sau stang are valoarea: " << node->left->key << " " << node->left->p << " ";
        if(node->right)
            cout << "Fiul sau drept are valoarea: " << node->right->key << " " << node->right->p << " ";
        cout << '\n';
        Inorder(node->right);
    }
}

int main()
{
    cout << "Treap\n";
    cout << "Alegeti una dintre opiunile urmatoare:\n";
    cout << "1.Inserare nod.\n";
    cout << "2.Cautare valoare.\n";
    cout << "3.Stergere nod.\n";
    cout << "4.Afisarea treapului.\n";
    int T, c, key;
    Treap* root = NULL;
    while(1)
    {
        cin >> c;
        if(c == 1)
        {
            cout << "Introduceti valoarea nodului de inserat: ";
            cin >> key;
            Insert(root, key);
            cout << "Nod inserat!\n";
        }
        else if(c == 2)
        {
            cout << "Introduceti valoarea nodului de cautat: ";
            cin >> key;
            Treap* nod = NULL;
            nod = Search(root, key);
            if(!nod)
                cout << key << "Nu exista in treap acum!\n";
            else
                cout << nod->key << " " << nod->p << '\n';
        }
        else if(c == 3)
        {
            cout << "Introduceti valoarea nodului de sters: ";
            cin >> key;
            root = Delete(root, key);
        }
        else if(c == 4)
        {
            //cout << "Ta daaa\n";
            Inorder(root);
            cout << '\n';
        }
    }
    return 0;
}