search_tree

#include <assert.h>

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

    bool Insert(int Key);
    bool Delete(int Key);
    bool Find(int Key);

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

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

    Node* root;

    Node* find(Node* node, int key);
    Node* getNext(Node* node);
    void detach(Node* node);
};


Tree::~Tree()
{
    if (root != 0)
        delete root;
}

Tree::Node::~Node()
{
    if (left != 0)
        delete left;
    if (right != 0)
        delete right;
}

bool Tree::Insert(int Key)
{
    if (!root)
    {
        root->key = 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->key = Key;
        cur_node->left->parent = cur_node;
    }
    else if (cur_node->key < Key)
    {
        cur_node->right->key = Key;
        cur_node->left->parent = cur_node;
    }
    return true;
}

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

bool Tree::Find(int Key)
{
    return find(root, Key);
}

bool Tree::Delete(int Key)
{
    Node* to_del = find(root, Key);

    if (to_del == 0)
        return false;

    if (to_del->left == 0 || to_del->right == 0)
    {
        detach(to_del);
        delete to_del;
        return true;
    }

    Node* next = getNext(to_del);

    to_del->key = next->key;

    detach(next);

    delete next;
    return true;
}

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

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

    if (node->parent == 0)
        return;

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

    if (child != 0)
    {
        child->parent = node->parent;
    }

    node->parent->left == node
        ? node->parent->left = child
        : node->parent->right = child;

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

int main()
{
    Tree tree;
    int array[] = { 5, 1, 5, 6, 2, 7, 8, 12, 21, 4, 0 };
    for (int i = 0; i < 10; i++)
    {
        tree.Insert(array[i]);
    }

    tree.Delete(7);
    return 0;
}