Splay tree

#include <iostream>
#include <utility>
#include <stack>
#include <queue>
using namespace std;

template <class T>
class Node
{
private:
    Node* left;
    Node* right;
    Node* parent;
    T data;
public:

    Node<T>()
    {
        parent = left = right = nullptr;
        data = T();
    }

    Node<T>(T const& n)
    {
        left = right = parent = nullptr;
        data = n;
    }

    T getData()
    {
        return data;
    }

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

    template<class T>
    friend class SplayTree;

};


template<class T>
class SplayTree
{
private:
    Node<T>* root;

    //zag
    void leftRotate(Node<T>* p)
    {
        Node<T>* x = p->right;
        p->right = x->left;

        if (x->left != nullptr)
            x->left->parent = p;

        if (p->parent == nullptr)
            root = x;
        else if (p->parent->left == p)
            p->parent->left = x;
        else p->parent->right = x;

        x->parent = p->parent;
        x->left = p;
        p->parent = x;
    }

    //zig
    void rightRotate(Node<T>* p)
    {
        Node<T>* x = p->left;
        p->left = x->right;

        if (x->right != nullptr)
            x->right->parent = p;

        if (p->parent == nullptr)
            root = x;
        else if (p == p->parent->left)
            p->parent->left = x;
        else
            p->parent->right = x;

        x->parent = p->parent;
        x->right = p;
        p->parent = x;
    }

    void splay(Node<T>* x)
    {
        while (x->parent != nullptr)
        {
            //zag and zig if the parent x does haven't a parent
            if (x->parent->parent == nullptr)
                if (x == x->parent->left)
                    rightRotate(x->parent);
                else
                    leftRotate(x->parent);
            else if (x == x->parent->left && x->parent == x->parent->parent->left)
            {
                //zig-zig
                rightRotate(x->parent->parent);
                rightRotate(x->parent);
            }
            else if (x == x->parent->right && x->parent == x->parent->parent->right)
            {
                //zag-zag
                leftRotate(x->parent->parent);
                leftRotate(x->parent);
            }
            else if (x == x->parent->right && x->parent == x->parent->parent->left)
            {
                //zig-zag
                leftRotate(x->parent);
                rightRotate(x->parent);
            }
            else
            {
                //zag-zig
                rightRotate(x->parent);
                leftRotate(x->parent);
            }
        }

    }

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

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

        return treeSearch(key, node->right);
    }



    Node<T>* join(Node<T>* s, Node<T>* t)
    {
        if (s == nullptr)
            return t;
        if (t == nullptr)
            return s;

        Node<T>* x = find_max(s);
        splay(x);
        x->right = t;
        t->parent = x;

        return x;
    }

    pair<Node<T>*, Node<T>*> split(T const& data)
    {
        Node<T>* s;
        Node<T>* t;
        Node<T>* x = find(data);
        splay(x);

        if (x->right != nullptr)
        {
            t = x->right;
            t->parent = nullptr;
        }

        s = x;
        s->right = nullptr;
        x == nullptr;

        return { s, t };
    }

    Node<T>* tree_insert(T const& data)
    {
        Node<T>* insert_node = new Node<T>(data);

        if (insert_node == nullptr) throw "Nullptr";

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

        Node<T>* cur = root;

        while (true)
        {

            if (data < cur->data)
            {
                if (cur->left == nullptr)
                {
                    cur->left = insert_node;
                    insert_node->parent = cur;
                    break;
                }
                else cur = cur->left;
            }
            else
            {
                if (cur->right == nullptr)
                {
                    cur->right = insert_node;
                    insert_node->parent = cur;
                    break;
                }
                else cur = cur->right;
            }
        }
        return insert_node;
    }

public:

    SplayTree()
    {
        root = nullptr;
    }

    SplayTree(Node<T> N)
    {
        this->root->data = N->data;
        this->root->left = N->left;
        this->root->right = N->right;
    }

    Node<T>* getRoot()
    {
        return root;
    }

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

        if (ans != nullptr)
            splay(ans);

        return ans;
    }


    void erase(const T& data)
    {
        pair<Node<T>*, Node<T>*> Q = split(data);

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

        if (Q.first->left == nullptr)
            Q.first->left->parent = nullptr;

        root = join(Q.first->left, Q.second);
    }

    void insert(T const& data)
    {
        Node<T>* ans = tree_insert(data);

        if (ans != nullptr)
            splay(ans);
    }

    Node<T>* find_max(Node<T>* node)
    {
        Node<T>* cur = node;
        for (cur; cur->right != nullptr; cur = cur->right);

        splay(cur);
        return cur;
    }

    void PreOrder() const
    {
        cout << "\nPreOrder: ";
        if (root == nullptr) return;

        stack<Node<T>*> s;
        s.push(root);

        while (!s.empty())
        {

            Node<T>* cur = s.top();
            s.pop();

            cout << cur->data << " ";

            if (cur->left) s.push(cur->left);
            if (cur->right) s.push(cur->right);

        }

        cout << '\n';

    }

    void InOrder() const
    {
        cout << "\nInOrder: ";
        if (root == nullptr) return;

        stack<Node<T>*> s;
        Node<T>* cur = root;

        s.push(root);

        while (!s.empty())
        {

            while (cur->left != nullptr)
            {
                s.push(cur->left);
                cur = cur->left;
            }

            Node<T>* v = s.top();
            s.pop();

            cout << v->data << " ";
            if (v->right) s.push(v->right);
        }

        cout << '\n';
    }

    void PostOrder() const
    {

        cout << "\nPostOrder: ";

        stack<Node<T>*> s, q;
        s.push(root);
        q.push(root);

        while (!s.empty())
        {
            Node<T>* cur = s.top();
            s.pop();

            if (cur->left)
            {
                q.push(cur->left);
                s.push(cur->left);
            }

            if (cur->right)
            {
                q.push(cur->right);
                s.push(cur->right);
            }

        }

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

            cout << cur->data << " ";
        }
    }

    ~SplayTree<T>()
    {
        while (root != nullptr)
        {
            erase(root->data);
        }
    }
};

int main()
{
    SplayTree<int> A;
    A.insert(15);
    A.insert(10);
    A.insert(40);
    A.insert(20);
    A.insert(100);
    A.insert(1);
    A.insert(6);
    A.insert(14);

    Node<int>* ptr = A.find_max(A.getRoot());
    Node<int>* ptr2 = A.find(15);

    if (ptr2) cout << ptr2->getData() << " is find" << '\n';
    cout << "The max element in tree: " << ptr->getData() << '\n';

    A.PreOrder();

    A.erase(40);
    cout << "Element 40 is deleted\n";

    A.PreOrder();
    A.InOrder();
    A.PostOrder();

    return 0;
}