Red Black Tree Insert

#include "stdafx.h"
#include <iostream>
using namespace std;
 
enum color {red, black};
 
class Node
{
    friend class RBTree;
private:
    color color;
    int data;
    Node* left;
    Node* right;
    Node* parent;
public:
    Node() : color(black), data(NULL), left(NULL), right(NULL), parent(NULL) {} // nil
    Node(int data) : color(red), data(data), left(NULL), right(NULL), parent(NULL) {} // node
};
 
class RBTree
{
private:
    Node* nil;
    Node* root;
    Node* newNode;
public:
    RBTree()
    {
        nil = new Node();
        root = nil;
    }
    
    ~RBTree()
    {
        
    }
 
    int getColor(int key)
    {
        Node* temp = root;
        while(temp->data != key) {
            if(key >= temp->data) {
                temp = temp->right;
            }
            else {
                temp = temp->left;
            }
        }
        return temp->color;
    }
 
    void getData(int key)
    {
        Node* temp = root;
        while(temp->data != key) {
            if(key >= temp->data) {
                temp = temp->right;
            }
            else {
                temp = temp->left;
            }
        }
        cout << temp->data << endl;
    }
 
    void insert(int data) // function for inserting new node
    {
        Node* current = root;
        Node* parent = NULL;
        // find empty node
        while(current != nil) {
            parent = current;
            if(data >= current->data) {
                current = current->right;
            }
            else {
                current = current->left;
            }
        }
 
        // create new node
        Node* newNode = new Node(data);
        newNode->parent = parent;
        newNode->left = newNode->right = nil;
 
        // insert node in tree
        if(parent) {
            if(data >= parent->data) {  // if current data more than parent
                parent->right = newNode;// go right
            }
            else {
                parent->left = newNode; // if current data less than parent, go left
            }
        }
        else { // if root empty
            root = newNode;
            root->color = black;
        }
        insertFix(newNode);
    }
 
    Node* parent(Node* node) { // parent of new node
        return node->parent;
    }
 
    Node* grandpa(Node* node) { // grandpa of new node
        return node->parent->parent;
    }
 
    Node* uncle(Node* node) { // uncle of new node
        if(parent(node)->parent != NULL) {
            if(parent(node)->parent == grandpa(node) && grandpa(node)->left == parent(node)) {
                return grandpa(node)->right;
            }
            else if(parent(node)->parent == grandpa(node) && grandpa(node)->right == parent(node)) {
                return grandpa(node)->left;
            }
        }
    }
 
    void insertFix(Node* node)
    {
        if(node != root && parent(node) != root) {
            if(parent(node)->color == red) {
                while(parent(node)->color == red) {
                    if(uncle(node)->color == red) {
                        node = recolor(node);
                    }
                    else if(uncle(node)->color == black) {
                        if(parent(node)->left == node) {
                            node = rightRotate(node);
                        }
                        else if(parent(node)->right == node) {
                            node = leftRotate(node);
                        }
                    }
                }
            }
        }
    }
 
    Node* recolor(Node* node) { // recolor nodes
        Node* p = parent(node);
        Node* g = grandpa(node);
        Node* u = uncle(node);
        p->color = black;
        u->color = black;
        if(grandpa(node) == root) {
            g->color = black;
            cout << "recolor" << endl;
            return node;
        }
        else if(grandpa(node)->parent != NULL && grandpa(node)->parent->color == red) {
            return grandpa(node);
            cout << "recolor" << endl;
        }
        else if(grandpa(node)->parent != NULL && grandpa(node)->parent->color == black) {
            grandpa(node)->color = red;
            cout << "recolor" << endl;
            return node;
        }
    }
 
    Node* leftRotate(Node* node) { // left rotate
        if(parent(node)->right == node) {
            // left right case
            if(grandpa(node)->left == parent(node) && parent(node)->parent == grandpa(node)) {
                Node* p = parent(node);
                Node* g = grandpa(node);
                Node* p_left = parent(node)->left;
 
                p_left = p;
                p_left->right = nil;
                p = node;
                p_left->parent = p;
                p->left = p_left;
                p->parent = g;
                g->left = p;
                cout << "left right case" << endl;
                return p_left;
            }
 
            // right right case
            if(grandpa(node)->right == parent(node) && parent(node)->parent == grandpa(node)) {
                if(grandpa(node) == root) {
                    Node* p = parent(node);
                    Node* g = grandpa(node);
                    p->left = g;
                    g->parent = p;
                    g->right = nil;
                    p->parent = NULL;
                    p->color = black;
                    g->color = red;
                    root = p;
                    return node;
                }
                else if(grandpa(node)->parent != NULL && grandpa(node)->parent->left == grandpa(node)) {
                    Node* p = parent(node);
                    Node* g = grandpa(node);
 
                    p->left = g;
                    g->parent = p;
                    g->right = nil;
                    p->parent = g->parent;
                    g->parent->left = p;
                    p->color = black;
                    g->color = red;
                    return node;
                }
                else if(grandpa(node)->parent != NULL && grandpa(node)->parent->right == grandpa(node)) {
                    Node* p = parent(node);
                    Node* g = grandpa(node);
 
                    p->left = g;
                    g->parent = p;
                    g->right = nil;
                    p->parent = g->parent;
                    g->parent->right = p;
                    p->color = black;
                    g->color = red;
                    return node;
                }
                cout << "right right case" << endl;
            }
        }
    }
 
    Node* rightRotate(Node* node) { // right rotate
        if(parent(node)->left == node) {
            // right left case
            if(grandpa(node)->right == parent(node) && parent(node)->parent == grandpa(node)) {
                Node* p = parent(node);
                Node* g = grandpa(node);
                Node* p_right = parent(node)->right;
 
                p_right = p;
                p_right->left = nil;
                p = node;
                p_right->parent = p;
                p->right = p_right;
                p->parent = g;
                g->right = p;
                cout << "right left case" << endl;
                return p_right;
            }
 
            // left left case
            if(grandpa(node)->left == parent(node) && parent(node)->parent == grandpa(node)) {
                if(grandpa(node) == root) {
                    Node* p = parent(node);
                    Node* g = grandpa(node);
 
                    p->right = g;
                    g->parent = p;
                    g->left = nil;
                    p->parent = NULL;
                    p->color = black;
                    g->color = red;
                    root = p;
                    cout << "left left case" << endl;
                    return node;
                }
                else if(grandpa(node)->parent != NULL && grandpa(node)->parent->left == grandpa(node)) {
                    Node* p = parent(node);
                    Node* g = grandpa(node);
 
                    p->right = g;
                    g->parent = p;
                    g->left = nil;
                    p->parent = g->parent;
                    g->parent->left = p;
                    p->color = black;
                    g->color = red;
                    cout << "left left case" << endl;
                    return node;
                }
                else if(grandpa(node)->parent != NULL && grandpa(node)->parent->right == grandpa(node)) {
                    Node* p = parent(node);
                    Node* g = grandpa(node);
 
                    p->right = g;
                    g->parent = p;
                    g->left = nil;
                    p->parent = g->parent;
                    g->parent->right = p;
                    p->color = black;
                    g->color = red;
                    cout << "left left case" << endl;
                    return node;
                }
            }
        }
    }
 
    void printColor(int key)
    {
        int color = getColor(key);
        if(color == 0) {
            cout << key << " is red" << endl;
        }
        if(color == 1) {
            cout << key << " is black" << endl;
        }
    }
 
    int getRootData()
    {
        return root->data;
    }
 
    int getRootColor()
    {
        return root->color;
    }
 
    int getNodeData(Node* node) {
        Node* t = root;
        while(t != node) {
            if(node->data >= t->data) {
                t = t->right;
            }
            else {
                t = t->left;
            }
        }
        return t->data;
    }
 
};
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    RBTree tree;
 
    tree.insert(30);
    tree.insert(21);
    tree.insert(27);
    tree.insert(45);
    tree.insert(46);
 
    tree.printColor(30);
    tree.printColor(21);
    tree.printColor(27);
    tree.printColor(45);
    tree.printColor(46);
 
    cout << "root color: " << tree.getRootColor() << endl;
    cout << "root data: " << tree.getRootData() << endl;
 
    system("pause");
    return 0;
}