RBTree

#include <iostream>
#include <vector>

class RBTree
{
public:
    RBTree() : root(0){}
    ~RBTree();

    bool Add(int x);
    bool Delete(int x);
    bool Find(int x) { return (find(root, x) != 0); }
private:
    struct Node{
        int key;
        int color; // 0 - red, 1 - black
        Node* left;
        Node* right;
        Node* parent;

        Node(int key) : key(key), color(0), left(0), right(0), parent(0){}
    };

    Node* root;

    const Node* find(const Node* node, int key) const;
    bool insert(Node*& node, int Key);

    void left_turn(Node*& node);
    void right_turn(Node*& node);

    Node* grandparent(Node* node);
    Node* uncle(Node* node);

    void insert_case1(Node*& node);
    void insert_case2(Node*& node);
    void insert_case3(Node*& node);
    void insert_case4(Node*& node);
    void insert_case5(Node*& node);

    void deleteNode(Node*& node);
};

RBTree::~RBTree()
{
    deleteNode(root);
    root = 0;
}

void RBTree::deleteNode(Node*& node)
{
    if (node == 0)
        return;
    deleteNode(node->left);
    deleteNode(node->right);

    delete node;
}

RBTree::Node* RBTree::grandparent(Node* node)
{
    if (node != 0 && node->parent != 0)
        return node->parent->parent;
    else
        return 0;
}

RBTree::Node* RBTree::uncle(Node* node)
{
    Node*g = grandparent(node);
    if (g == 0)
        return 0;
    if (node->parent == g->right)
        return g->left;
    else
        return g->right;
}

const RBTree::Node* RBTree::find(const Node* node, int Key) const
{
    if (node == 0)
        return 0;
    if (node->key == Key)
        return node;
    return node->key > Key ? find(node->left, Key) : find(node->right, Key);
}

void RBTree::left_turn(Node*& node)
{
    int fl = (node->parent == 0) ? 1 : 0;
    Node* a = node;
    Node* b = node->right;
    a->right = b->left;
    if (a->right != 0)
        a->right->parent = a;
    b->parent = a->parent;
    if (!fl)
    {
        if (a->parent->key > a->key)
            a->parent->left = b;
        else if (a->parent->key < a->key)
            a->parent->right = b;
    }
    b->left = a;
    a->parent = b;
    if (fl)
        root = b;
}

void RBTree::right_turn(Node*& node)
{
    Node* b = node->left;
    node->left = b->right;
    if (b->right != 0)
        b->right->parent = node;
    b->parent = node->parent;
    if (node->parent)
    {
        if (node == node->parent->right)
            node->parent->right = b;
        else
            node->parent->left = b;
    }
    else
        root = b;
    b->right = node;
    node->parent = b;
}

void RBTree::insert_case1(Node*& node)
{
    if (node->parent == NULL) // node is root
    {
        node->color = 1; // paint node to black
        return;
    }
    else
        insert_case2(node);
}

void RBTree::insert_case2(Node*& node)
{
    if (node->parent->color == 1) // parent is black
        return; // all right
    else
        insert_case3(node);
}

void RBTree::insert_case3(Node*& node)
{
    Node *g = grandparent(node), *u = uncle(node);
    if ((u != 0) && (u->color == 0) && (node->parent->color == 0)) //parent and uncle are red
    {
        node->parent->color = 1; //paint parent to black
        u->color = 1; // paint uncle to black
        g->color = 0; // paint grandfather to red
        insert_case1(g);
    }
    else
        insert_case4(node);

}

void RBTree::insert_case4(Node*& node)
{
    Node *g = grandparent(node); // in fact, parent is red and uncle is black
    if ((node == node->parent->right) && (node->parent == g->left))
    {
        left_turn(node->parent);
        node = node->left;
    }
    else if ((node == node->parent->left) && (node->parent == g->right))
    {
        right_turn(node->parent);
        node = node->right;
    }
    insert_case5(node);
}

void RBTree::insert_case5(Node*& node)
{
    Node *g = grandparent(node);
    node->parent->color = 1; // paint parent to black
    g->color = 0; // paint grandfather to red
    if ((node == node->parent->left) && (node->parent == g->left))
        right_turn(g);
    else
        left_turn(g);
}

bool RBTree::Add(int Key)
{
    if (!root)
    {
        root = new Node(Key);
        root->color = 1;
        return true;
    }

    Node* cur_node = root;
    while (true)
    {
        if (cur_node->key > Key && cur_node->left != 0)
            cur_node = cur_node->left;
        else if (cur_node->key < Key && cur_node->right != 0)
            cur_node = cur_node->right;
        else if (cur_node->key == Key)
            return false;
        else
            break;
    }
    if (cur_node->key > Key)
    {
        cur_node->left = new Node(Key);
        cur_node->left->parent = cur_node;
        insert_case1(cur_node->left);
    }
    else if (cur_node->key < Key)
    {
        cur_node->right = new Node(Key);
        cur_node->right->parent = cur_node;
        insert_case1(cur_node->right);
    }

    return true;
}

int main()
{
    RBTree T;
    std::vector<int> arr = { 1, 8, 6, 11, 13, 17, 15, 25, 22, 27 };
    for (int i = 0; i < 10; i++)
        T.Add(arr[i]);
    return 0;
}