Splay Tree

#include <iostream>

using namespace std;

class Node {
public:
    int key;
    Node* child[2];

    Node() {
        this->child[0] = nullptr;
        this->child[1] = nullptr;
    }
    Node(int key) {
        this->key = key;
        this->child[0] = nullptr;
        this->child[1] = nullptr;
    }
    Node(int key, Node* leftChild, Node* rightChild) {
        this->key = key;
        this->child[0] = leftChild;
        this->child[1] = rightChild;
    }
    ~Node() {}
};

/**
    Searching
*/

// Long version
Node* search(Node* node, int key) {
    if (nullptr == node || node->key == key)
        return node;
    if (node->key <= key)
        return search(node->child[0], key);
    return search(node->child[1], key);
}

// Short version
Node* searchShort(Node* node, int key) {
    if (nullptr == node || node->key == key)
        return node;
    return searchShort(node->child[ node->key <= key ], key);
}


/**
    Rotating
*/

// Rotate right
Node* rotateRight(Node* x) {
    if (nullptr == x || x->child[0] == nullptr)
        return x;
    Node* y = x->child[0];
    x->child[0] = y->child[1];
    y->child[1] = x;
    return y;
}

// Rotate left
Node* rotateLeft(Node* x) {
    if (nullptr == x || x->child[1] == nullptr)
        return x;
    Node* y = x->child[1];
    x->child[1] = y->child[0];
    y->child[0] = x;
    return y;
}

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



    Node child1(-4);            Node child2(3);
                //                  //
                //                  //
            Node child3(2, &child1, &child2);                   Node child4(18);
                                        //                      //
                                        //                      //
                                    Node parent(5, &child3, &child4);



    Node* searchNode = searchShort(&parent, 13);

    if (nullptr == searchNode) {
        cout << "Couldn't find the node!" << endl;
    }
    else {
        cout << "Found the node with key: " << searchNode->key << endl;
    }
    cout << endl;

    cout << "Rotating right..." << endl;
    Node* yRight = rotateRight(&parent);
    cout << "Y node is: " << yRight->key << endl;

    cout << "Rotating left..." << endl;
    Node* yLeft = rotateLeft(&parent);
    cout << "Y node is: " << yLeft->key << endl;

    cout << "Rotating left again (Y has no right child)..." << endl;
    yLeft = rotateLeft(yLeft);
    if (nullptr == yLeft) {
        cout << "Same situation: " << yLeft->key << endl;
    } else {
        cout << "Y node is: " << yLeft->key << endl;
    }
    cout << endl;

    system("PAUSE");
    return 0;
}