Splay_Tree_C++

#include<bits/stdc++.h>
using namespace std;

#define MX 10005

class Splay_Tree {
    unsigned int tree_size;

    typedef struct Node{
        int key;
        Node *left, *right, *parent;

        explicit Node(const int& val):left(nullptr), right(nullptr), parent(nullptr), key(val){}
    }Node;
    Node* root;

    void rotateLeft(Node *u);
    void rotateRight(Node *u);
    Node *join(Node *u, Node *v);
    Node *getMaxNode(Node *u);
    Node *insertBST(const int& val);
    Node *search(Node *u, const int& val);
    void splay(Node *u);

    void printNodeInternal(Node* nodes[MX], int last_indx, int level, int max_level);
    void printNode(Node* R);
    void printWhiteSpace(int cnt);
    int maxLevel(Node* node);
    bool isAllElementsNull(Node* nodes[MX], int last_indx);
    Node* deleteNodes(Node* R);

public:

    Splay_Tree() : root(nullptr), tree_size(0) {}
    void insert(const int& val);
    bool find(const int& val);
    void remove(const int& val);
    unsigned int size(){ return tree_size; }
    bool empty(){ return size()==0; }
    void printBTree();

    virtual ~Splay_Tree(){
        root = deleteNodes(this->root);
        tree_size = 0;
    }
};


void Splay_Tree::rotateLeft(Node *u){
    if(u->right){
        Node* v = u->right;
        u->right = v->left;
        if(v->left)v->left->parent = u;
        v->parent = u->parent;
        if(!u->parent)this->root = v;
        else if( u == u->parent->left ) u->parent->left = v;
        else u->parent->right = v;
        v->left = u;
        u->parent = v;
    }
}

void Splay_Tree::rotateRight(Node *u){
    if(u->left){
        Node* v = u->left;
        u->left = v->right;
        if(v->right)v->right->parent = u;
        v->parent = u->parent;
        if(!u->parent)this->root = v;
        else if( u == u->parent->left ) u->parent->left = v;
        else u->parent->right = v;
        v->right = u;
        u->parent = v;
    }
}

Splay_Tree::Node *Splay_Tree::join(Node* u, Node* v){
    Node *node = nullptr, *left_root = u, *right_root = v;
    Node* current_root = nullptr;
    if(left_root){
        left_root->parent = nullptr;
        node = getMaxNode(left_root);
        splay(node);
        current_root = node;
    }
    if(right_root){
        if(left_root) node->right = right_root;
        else current_root = right_root;

        right_root->parent = node;
    }
    return current_root;
}

Splay_Tree::Node *Splay_Tree::getMaxNode(Node* u){
    while( u->right ) u = u->right;
    return u;
}

Splay_Tree::Node *Splay_Tree::insertBST(const int &val) {
    Node *curr = this->root, *par = nullptr;
    while(curr){
        par = curr;
        (val <= curr->key) ? curr = curr->left : curr = curr->right;
    }
    curr = new Node(val);
    curr->parent = par;
    if(!par)this->root = curr;
    else (curr->key <= par->key) ? (par->left = curr) : (par->right = curr);
    return curr;
}

//returns null or node or parent(just before)
Splay_Tree::Node *Splay_Tree::search(Node *u, const int& val){
    if(!u || u->key==val)return u;
    else if(val < u->key){
        if(!u->left)return u;
        else return search(u->left, val);
    }
    else{
        if(!u->right)return u;
        else return search(u->right, val);
    }
}


void Splay_Tree::splay(Node* u){
    while(true) {
        if(!u->parent)break;
        else if( !u->parent->parent ) {//left or right...makes u root
            if( u->parent->left == u ) rotateRight( u->parent );
            else rotateLeft( u->parent );
        }
        else if( u->parent->left == u && u->parent->parent->left == u->parent ) {//left left case
            rotateRight( u->parent->parent );
            rotateRight( u->parent );
        }
        else if( u->parent->left == u && u->parent->parent->right == u->parent ){ //right-left case
            rotateRight( u->parent );
            rotateLeft( u->parent );
        }
        else if( u->parent->right == u && u->parent->parent->right == u->parent ) {//right-right case
            rotateLeft( u->parent->parent );
            rotateLeft( u->parent );
        }
        else if( u->parent->right == u && u->parent->parent->left == u->parent ){//left-right case
            rotateLeft( u->parent );
            rotateRight( u->parent );
        }
    }
}


void Splay_Tree::insert(const int& val){
    Node *current = insertBST(val);
    this->tree_size++;
    splay(current);
}


bool Splay_Tree::find(const int& val){
    Node *node = search(this->root, val);
    bool found;
    found = !(!node || node->key != val);
    if(node)splay(node);
    return found;
}


void Splay_Tree::remove(const int& val){
    Node *node = search(this->root, val);
    if(!node)return;
    else if(node->key!=val){
        splay(node);
        return;
    }
    else{
        splay(node);
        node = this->root;
        Node *left_root = node->left, *right_root = node->right;
        delete node;
        node = nullptr;
        this->root = join(left_root, right_root);
        this->tree_size--;
    }
}


//for printing purpose
void Splay_Tree::printNodeInternal(Node* nodes[MX], int last_indx, int level, int max_level){
    if(last_indx == 0 || isAllElementsNull(nodes, last_indx))
        return;

    int floor = max_level - level;
    int edgeLines = (int)pow(2, max(floor-1, 0));
    int firstSpaces = (int)pow(2, floor) - 1;
    int betweenSpaces = (int)pow(2, (floor+1))-1;

    printWhiteSpace(firstSpaces);

    Node* newNodes[MX];
    int new_last_indx = 0;

    for(int i = 0; i < last_indx; i++){
        Node* node = nodes[i];
        if(node){
            cout<<node->key;
            newNodes[new_last_indx++] = node->left;
            newNodes[new_last_indx++] = node->right;
        }
        else{
            newNodes[new_last_indx++] = nullptr;
            newNodes[new_last_indx++] = nullptr;
            cout<<" ";
        }
        printWhiteSpace(betweenSpaces);
    }
    cout<<endl;

    for(int i = 1; i <= edgeLines ; ++i){
        for(int j = 0; j < last_indx; j++){

            printWhiteSpace(firstSpaces - i);

            if(!nodes[j]){
                printWhiteSpace(edgeLines + edgeLines + i + 1);
                continue;
            }

            if(nodes[j]->left)cout<<"/";
            else printWhiteSpace(1);

            printWhiteSpace(i+i-1);

            if(nodes[j]->right)cout<<"\\";
            else printWhiteSpace(1);

            printWhiteSpace(edgeLines + edgeLines - i);

        }
        cout<<endl;
    }

    printNodeInternal(newNodes, new_last_indx, level + 1, max_level);

}

void Splay_Tree::printNode(Node* R){
    int max_level = maxLevel(R);
    Node* nodes[MX];
    int last_indx = 0;
    nodes[last_indx++] = R;
    printNodeInternal(nodes, last_indx, 1, max_level);
}

void Splay_Tree::printWhiteSpace(int cnt){
    for(int i = 0; i < cnt; i++)cout<<" ";
}

int Splay_Tree::maxLevel(Node* node){
    if(!node)return 0;
    return max(maxLevel(node->left), maxLevel(node->right)) + 1;
}

bool Splay_Tree::isAllElementsNull(Node* nodes[MX], int last_indx){
    for(int i = 0; i < last_indx ; i++){
        if(nodes[i] != nullptr)return false;
    }
    return true;
}

Splay_Tree::Node *Splay_Tree::deleteNodes(Node *R){
    if(R== nullptr)return R;
    R->left = deleteNodes(R->left);
    R->right = deleteNodes(R->right);
    delete R;
    R = nullptr;
    return R;
}

void Splay_Tree::printBTree(){
    for(int i = 0 ; i < 50; i++)cout<<'_';
    cout<<endl;
    printNode(this->root);
    cout<<endl;
    for(int i = 0 ; i < 50; i++)cout<<'_';
    cout<<endl;
}



int main(){
    Splay_Tree t;

    while(true){
        cout<<"1. insert 2.look up 3. delete 4 print 5. size 6.exit "<<endl;
        int n;
        cin>>n;
        if(n==1){
            int num;
            cin>>num;
            t.insert(num);
        }
        else if(n==2){
            int num;
            cin>>num;
            cout<<(!t.empty() && t.find(num)?"found":"not found")<<endl;
        }
        else if(n==3){
            if(t.empty()){
                cout<<"Tree is empty"<<endl;
                continue;
            }
            int num;
            cin>>num;
            t.remove(num);
        }
        else if(n==4){
            t.printBTree();
        }
        else if(n==5){
            cout<<"Size: "<<t.size()<<endl;
        }
        else if(n==6){
            break;
        }
    }

    return 0;
}