Treap

#include <iostream>
#include <vector>
#include <random>
#include <ctime>
#include <queue>
using namespace std;


template<class T>
class Node
{
private:
    Node<T>* left;
    Node<T>* right;
    T key;
    int priority;

public:
    Node<T>()
        : left(nullptr)
        , right(nullptr)
        , key(T())
        , priority(rand())
    { }

    Node<T>(const T& _key)
        : left(nullptr)
        , right(nullptr)
        , key(_key)
        , priority(rand())
    { }

    ~Node<T>()
    {
        delete left;
        delete right;
        left = right = nullptr;
    }

    template <class T>
    friend class Treap;

    template <class T>
    friend ostream& operator <<(ostream& out, Treap<T>& Tr);
};

template <class T>
class Treap
{
private:


    Node<T>* root;
    int size;

    Node<T>* merge(Node<T>* LeftTree, Node<T>* RightTree)
    {
        if (LeftTree == nullptr)
            return RightTree;
        if (RightTree == nullptr)
            return LeftTree;

        if (LeftTree->priority > RightTree->priority)
        {
            LeftTree->right = merge(LeftTree->right, RightTree);
            return LeftTree;
        }
        else
        {
            RightTree->left = merge(LeftTree, RightTree->left);
            return RightTree;
        }
    }

    void split(Node<T>* node, Node<T>*& outLeft, Node<T>*& outRight, const T& data)
    {
        if (!node)
        {
            outLeft = outRight = nullptr;
            return;
        }

        if (node->key <= data)
        {
            outLeft = node;
            split(node->right, outLeft->right, outRight, data);
        }
        else
        {
            outRight = node;
            split(node->left, outLeft, outRight->left, data);
        }
    }

    void inserting(Node<T>*& node, Node<T>* elem)
    {
        Node<T>* l;
        Node<T>* r;
        split(node, l, r, elem->key);

        node = merge(merge(l, elem), r);
    }

    void remove(Node<T>*& node, const T& data)
    {
        Node<T>* l;
        Node<T>* r;
        Node<T>* mid;

        split(root, l, r, data-1);
        split(r, mid, r, data);

        node = merge(l, r);

    }

    void build_treap(vector<int>& vec)
    {
        for (int i = 0; i < vec.size(); ++i)
        {
            insert(vec[i]);
        }
    }

    Node<T>* treeSearch(Node<T>* node, const T& data) const
    {
        if (!node || node->key == data)
            return node;

        if (node->key < data)
            return treeSearch(node->right,data);

        return treeSearch(node->left, data);
    }

public:

    Treap()
        : root(nullptr)
        , size(0)
    { }

    Treap(vector<T>& vec)
    {
        build_treap(vec);
    }

    int getSize() const
    {
        return size;
    }

    bool empty() const
    {
        return (size == 0);
    }

    bool find(const T& data) const
    {
        Node<T>* ans = treeSearch(root, data);

        return (data == ans->key);
    }

    void insert(const T& data)
    {
        Node<T>* elem = new Node<T>(data);
        if (!elem)
            throw "MemoryAllocError";

        if (!root)
            root = elem;
        else
            inserting(root, elem);

        size++;
    }

    void erase(const T& data)
    {
        if (!root)
        {
            cout << "Treap is empty";
            return;
        }

        remove(root, data);
        size--;
    }


    template <class T>
    friend ostream& operator <<(ostream& out, Treap<T>& Tr);
};

template <class T>
ostream& operator <<(ostream& out, Treap<T>& Tr)
{
    if (out && Tr.root)
    {
        queue<Node<T>*> q;
        q.push(Tr.root);

        while (!q.empty())
        {
            Node<T>* v = q.front();
            q.pop();

            if (v->right) q.push(v->right);
            if (v->left) q.push(v->left);

            out << "Key: " << v->key << ", Priority: " << v->priority << '\n';
        }
    }

    return out;
}

int main()
{

    Treap<int> treap;
    treap.insert(10);
    treap.insert(15);
    treap.insert(16);
    treap.insert(40);
    treap.insert(41);

    cout << "Size: " << treap.getSize() << '\n';
    cout << "Treap:\n" << treap;

    treap.erase(41);
    cout << "Size: " << treap.getSize() << '\n';
    cout << "Treap:\n" << treap;


    cout << "Check build on vector:\n";
    vector<int> vec = { 1, 2, 3, 15, 12, 10 };
    Treap<int> treap2(vec);

    cout << "Treap2:\n" << treap2;

    cout << "15 is " << (treap.find(15) ? "find" : "not find") << '\n';

    return 0;
}