Splay_Tree

#include <iostream>
#include <cassert>
#include <vector>

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

    bool Add(int Key);
    bool Delete(int Key)
    {
        Node* node = const_cast<Node*>(find(root, Key));
        splay(node);
        return(erase(Key));
    }
    bool Find(int Key)
    {
        Node* node = const_cast<Node*>(find(root, Key));
        if (!node)
            return false;
        splay(node);
        return true;
    }

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

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

    Splay_Tree(Node* node) : root(node) {}

private:

    Node* root;

    void deleteNode(Node*& node);

    void splay(Node* node);

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

    const Node* find(const Node* node, int key) const;

    Node* getNext(Node* node);
    void detach(Node* node);
    bool erase(int key);
};

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

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

    delete node;
}

void Splay_Tree::left_turn(Node* node)
{
    Node* b = node->right;
    node->right = b->left;
    if (b->left != 0)
        b->left->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->left = node;
    node->parent = b;
}

void Splay_Tree::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 Splay_Tree::splay(Node* x)
{
    while (x != root)
    {
        Splay_Tree::Node* g = x->parent->parent;
        if (x->parent == root)
        {
            if (x == x->parent->left)
                right_turn(x->parent);
            else
                left_turn(x->parent);
            return;
        }
        else if (x->parent->left == x && g->left == x->parent)
        {
            right_turn(g);
            right_turn(x->parent);
        }
        else if (x->parent->right == x && g->right == x->parent)
        {
            left_turn(g);
            left_turn(x->parent);
        }
        else if (x->parent->right == x && x->parent->parent->left == x->parent)
        {
            left_turn(x->parent);
            right_turn(g);
        }
        else
        {
            right_turn(x->parent);
            left_turn(g);
        }
    }
}

const Splay_Tree::Node* Splay_Tree::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);
}

bool Splay_Tree::Add(int Key)
{
    if (!root)
    {
        root = new Node(Key);
        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;
        splay(cur_node->right);
    }
    else if (cur_node->key < Key)
    {
        cur_node->right = new Node(Key);
        cur_node->right->parent = cur_node;
        splay(cur_node->right);
    }

    return true;
}

bool Splay_Tree::erase(int key)
{
    Node* node = const_cast<Node*>(find(root, key));
    if (node == 0)
        return false;
    if (node == root && node->left == 0 && node->right == 0)
    {
        delete node;
        root = 0;
        return true;
    }
    if (node->left == 0 || node->right == 0)
    {
        detach(node);
        delete node;
        return true;
    }

    Node* next = getNext(node);
    node->key = next->key;

    detach(next);
    delete next;
    return true;
}

Splay_Tree::Node* Splay_Tree::getNext(Node* node)
{
    Node* candidate = node->right;
    while (candidate->left != 0)
        candidate = candidate->left;
    return candidate;
}

void Splay_Tree::detach(Node* node)
{
    assert(node->left == 0 || node->right == 0);

    Node* child = node->left == 0 ? node->right : node->left;

    if (child != 0)
    {
        child->parent = node->parent;
        if (child->parent == 0)
        {
            root = child;
        }
    }
    if (node->parent != 0)
    {
        node->parent->left == node
            ? node->parent->left = child
            : node->parent->right = child;
    }

    node->left = 0;
    node->right = 0;
    node->parent = 0;
}

int main()
{
    Splay_Tree 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]);
    T.Find(6);
    T.Delete(27);
    return 0;
}