//file tree_item.h
#ifndef TREE_ITEM_H
#define TREE_ITEM_H

template <class T>
struct Tree_item
{
    T value;
    Tree_item * parent;
    Tree_item * left;
    Tree_item * right;

    Tree_item(const T &i)
    {
        parent = 0;
        left = 0;
        right = 0;
        value = i;
    }
};

#endif
------------------------------
//file tree.h


#ifndef TREE_H
#define TREE_H

#include "tree_item.h"
#include <math.h>
#include <algorithm>

template <class T>
class Tree
{
private:
    Tree_item<T> *root;

    Tree_item<T>* find(int a) const;
    Tree_item<T>* find(int a, Tree_item<T> *r) const;
    void delete_tree(Tree_item<T> *a);

    Tree_item<T>* insert(T a, Tree_item<T> *r);
    void delete_key(T a, Tree_item<T> *r);
    Tree_item<T>* sift_down(Tree_item<T> *a);
    Tree_item<T>* make_tree(const Tree_item<T> *a);

    static const int INF = 1 << 30;
public:
    Tree();
    ~Tree();

    Tree(const Tree<T> &t);
    Tree<T> & Tree<T>::operator = (const Tree<T> &t);

    void insert(T a);
    bool exists(T a) const;
    void delete_key(T a);
    void swap(Tree<T> &t);
    T next(T a, Tree_item<T> *x) const;
    T prev(T a, Tree_item<T> *x) const;
};

template <class T>
Tree<T>::Tree()
{
    root = 0;
}

template <class T>
Tree<T>::~Tree()
{
    Tree<T>::delete_tree(root);
}

template <class T>
Tree<T>::Tree(const Tree<T> &t)
{
    root = make_tree(t.root);
}

template <class T>
Tree_item<T>* Tree<T>::make_tree(const Tree_item<T> *a)
{
    if (a == 0) {return 0;}
    Tree_item<T> *x = new Tree_item<T>(a->value);
    x->right = make_tree(a->right);
    x->left = make_tree(a->left);
    return x;
}

template <class T>
Tree<T> & Tree<T>::operator = (const Tree<T> &t)
{
    Tree<T> temp(t);
    swap(temp);
    return(*this);
}

template <class T>
Tree_item<T>* Tree<T>::find(int a) const
{
    return find(a, root);
}

template <class T>
Tree_item<T>* Tree<T>::find(int a, Tree_item<T> *r) const
{
    if (r == 0) return 0;
    if (a < r->value) return find(a, r->left);
    else if (r->value < a) return find(a, r->right);
    else return r;
}

template <class T>
void Tree<T>::insert(T a)
{
    root = insert(a, root);
}

template <class T>
Tree_item<T>* Tree<T>::insert(T a, Tree_item<T> *r)
{
    if (r == 0)
    {
        Tree_item<T> *x  = new Tree_item<T>(a);
        return x;
    }

    if (a < r->value)
    {
        r->left = insert(a, r->left);
        r->left->parent = r;
    }
    else
    if (r->value < a)
    {
        r->right = insert(a, r->right);
        r->right->parent = r;
    }
    return r;
}

template <class T>
bool Tree<T>::exists(T a) const
{
    if (Tree<T>::find(a) != 0) return true;
    else return false;
}

template <class T>
void Tree<T>::delete_key(T a)
{
    Tree_item<T> *x = find(a, root);
    delete_key(a, x);
}

template <class T>
void Tree<T>::delete_key(T a, Tree_item<T> *r)
{
    if (r == 0) return;
    if (r->value == a)
    {
        Tree_item<T> *x = sift_down(r);
        if (x == 0)
        {
            if (r->parent)
            {
                if(r->parent->left == r) {r->parent->left = 0;}
                else {r->parent->right = 0;}
            }
            else
            {
                root = 0;
            }
            delete r;
            return;
        }
        r->value = x->value;
        delete_key(x->value, x);
    }
}

template <class T>
Tree_item<T>* Tree<T>::sift_down(Tree_item<T> *a)
{
    if (a->left)
    {
        Tree_item<T> *x = a->left;
        while (x->right != 0) x = x->right;
        return x;
    }
    if(a->right)
    {
        Tree_item<T> *x = a->right;
        while (x->left != 0) x = x->left;
        return x;
    }
    return 0;
}

template <class T>
void Tree<T>::delete_tree(Tree_item<T> *a)
{
    if (a == 0) {return;}
    Tree<T>::delete_tree(a->left);
    Tree<T>::delete_tree(a->right);
    delete a;
}

template <class T>
T Tree<T>::next(T a, Tree_item<T> *x) const
{
    if (x == 0) {return INF;}
    if (x->value <= a) {return Tree<T>::next(a, x->right);}
    return min(x->value, next(a, x->left));
}

template <class T>
T Tree<T>::prev(T a, Tree_item<T> *x) const
{
    if (x == 0) {return -INF;}
    if (x->value >= a) {return prev(a, x->left);}
    return max(a->value, prev(a, x->right));

}

template <class T>
void Tree<T>::swap(Tree<T> &t)
{
    std::swap(root, t.root);
}

#endif