gistfile1.cpp

#include <iostream>

using namespace std;

class LDNode
{
public:

    LDNode();
    int key;
    LDNode *left;
    LDNode *right;
    LDNode *parent;
    int level;
};

LDNode::LDNode()
{
    left = NULL;
    right = NULL;
    parent = NULL;
    key = 0;
}

class LDBSTree
{
    /*
        * root means start element of an action *
        * tRoot Whole Tree Roots *
    */

public:
    LDNode *search(LDNode *root,int key) {
        while(root != NULL && key != root->key) {
            if(key < root->key) {
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return root;
    }
    void print(LDNode *root) {
        if(root != NULL) {
            print(root->left);
            cout<<root->key<<" ";
            print(root->right);
        }
    }
    LDNode *min(LDNode *root) {
        while(root->left != NULL) {
            root = root->left;
        }
        return root;
    }

    LDNode *max(LDNode *root) {
        while(root->right != NULL) {
            root = root->right;
        }
        return root;
    }

    LDNode *succsesor(LDNode *root) {
        if(root->right != NULL) {
            return min(root->right);
        }
        LDNode *temp = root->parent;
        while(temp != NULL && root == temp->right) {
            root = temp;
            temp = temp->parent;
        }
        return temp;
    }

    int myRand(int low, int high) {
        srand(time(NULL));
        return rand() % (high - low + 1) + low;
    }

    bool probability(int rEdge) {
        int rand = myRand(1,rEdge);
        return rand == 1;
    }



    void transplant(LDNode *tRoot,LDNode *u,LDNode *v) {
        if(u->parent == NULL) {
            tRoot = v;
        } else if(u == u->parent->left) {
            u->parent->left = v;
        } else {
            u->parent->right = v;
        }
        if(v == NULL) {
            v->parent = u->parent;
        }
    }

    void remove(LDNode *tRoot,LDNode *node) {
        if(node->left == NULL) {
            transplant(tRoot,node,node->right);
        } else if(node->right == NULL) {
            transplant(tRoot,node,node->left);
        } else {
            LDNode *temp = min(node->right);
            if(temp->parent != node) {
                transplant(tRoot,temp,temp->right);
                temp->right = node->right;
                temp->right->parent = temp;
            }
            transplant(tRoot,node,temp);
            temp->left = node->left;
            temp->left->parent = temp;
        }
    }

    void leftRotate(LDNode *tRoot,LDNode *node) {
        LDNode *temp = node->right;
        node->right = temp->left;
        if(temp->left != NULL) {
            temp->left->parent = node;
        }
        temp->parent = node->parent;
        if(node->parent == NULL) {
            tRoot = temp;
        } else if(node == node->parent->left) {
            node->parent->left = temp;
        } else {
            node->parent->right = temp;
        }
        temp->left = node;
        node.p = temp;
    }

    void rightRotate(LDNode *tRoot,LDNode *node) {
        LDNode *temp = node->left;
        node->left = temp->right;
        if(temp->right != NULL) {
            temp->right->parent = node;
        }
        temp->parent = node->parent;
        if(node->parent == NULL) {
            tRoot = temp;
        } else if(node == node->parent->right) {
            node->parent->right = temp;
        } else {
            node->parent->left = temp;
        }
        temp->right = node;
        node.p = temp;
    }

    void rotateToDeath(LDNode *tRoot,LDNode *node,int rotateLeft,int rotateRight) {
        for(int i = 0;i < rotateLeft;i++) {
            leftRotate(tRoot,node);
        }
        for(int i = 0;i < rotateLeft;i++) {
            rightRotate(tRoot,node);
        }
    }

    void insert(LDNode *tRoot,int nKey) {//nNode = new Node, nKey = new key
        LDNode *temp = NULL;
        LDNode *nNode = new LDNode();
        nNode->key = nKey;

        bool rotation = false;
        int rotateLeft = 0,rotateRight = 0;

        LDNode *x = tRoot;
        while(x != NULL) {
            temp = x;

            if(!rotation) {
                rotation = probability(x->level);
            }

            if(nNode->key < x->key) {
                x = x->left;

                if(rotation) {
                    rotateRight++;
                }

            } else {
                x = x->right;

                if(rotation) {
                    rotateLeft++;
                }

            }
            x.parent.parent.level++;
        }

        nNode->parent = temp;
        if(temp == NULL) {
            tRoot = nNode;
        } else if(nNode->key < temp->key) {
            temp->left = nNode;
        } else {
            temp->right = nNode;
        }

        rotateToDeath(tRoot,temp,rotateLeft,rotateRight);
    }
};

int main()
{
    LDNode *tRoot = new LDNode();
    tRoot->key = 32;
    LDBSTree *tree = new LDBSTree();
    tree->insert(tRoot,23);

    tree->insert(tRoot,2);
    tree->insert(tRoot,44);
    tree->insert(tRoot,321);
    tree->insert(tRoot,1);
    tree->print(tRoot);
    return 0;
}