SplayTree v2

#include <iostream>

using namespace std;

template<typename T>
struct Node {

    T key;
    Node* child[2];

    Node() {
        this->child[0] = nullptr;
        this->child[1] = nullptr;
    }

    Node(T key) {
        this->key = key;
        this->child[0] = nullptr;
        this->child[1] = nullptr;
    }

    Node(T key, Node* left, Node* right) {
        this->key = key;
        this->child[0] = left;
        this->child[1] = right;
    }
};

template <typename T>
Node<T>* tree_rotate(Node<T>* x, bool dir) {
    if (x == nullptr || x->child[dir] == nullptr)
        return x;
    Node<T>* y = x->child[!dir];
    x->child[!dir] = y->child[dir];
    y->child[dir] = x;
    return y;
}

template <typename T>
Node<T>* splay_insert(Node<T>* h, T key){

    if (nullptr == h) {
        return new Node<T>(key);
    }

    if (key < h->key) {

        //      Node<T> hl = h.child[0];
        if (nullptr == h->child[0]) {
            return new Node<T>(key, nullptr, h);
        }

        if (key < h->child[0]->key) {
            //      Node<T> hll = hl.child[0];
            h->child[0]->child[0] = splay_insert(h->child[0]->child[0], key);
            h = tree_rotate(h, 1);
        }
        else{
            //      Node<T> hlr = hl.child[1];
            h->child[0]->child[1] = splay_insert(h->child[0]->child[1], key);
            h = tree_rotate(h->child[0], 0);
        }

        return tree_rotate(h, 1);
    }

    //      Node<T> hr = h.child[1];
    if (nullptr == h->child[1]){
        return new Node<T>(key, h, nullptr);
    }

    if (key > h->child[1]->key){
        //      Node<T> hrr = hr.child[1];
        h->child[1]->child[1] = splay_insert(h->child[1]->child[1], key);
        h = tree_rotate(h, 0);
    }
    else{
        //      Node<T> hrl = hr.child[0];
        h->child[1]->child[0] = splay_insert(h->child[1]->child[0], key);
        h = tree_rotate(h->child[1], 1);
    }

    return tree_rotate(h, 0);
}

int main() {
    system("COLOR F0");

    Node<int> root(5);
    Node<int> newRoot = *splay_insert(&root, 7);

    system("PAUSE");
    return 0;
}