#include <cstdlib> // for NULL

class not_found_exception {};

template <typename T, typename V>
class Node
{
    public:
        Node (const T& key, const V& value);
        
        ~Node ()
        {
            if (left) delete left;
            if (right) delete right;
        }
        
        Node* clone ()
        {
            Node* cln = new Node(key, value);
            cln->left = left->clone();
            cln->right = right->clone();
            cln->height = height;
            cln->deleted = deleted;
        }
        
        Node* insert (Node*);
        void remove() {deleted = true;}
        const Node* find (const T& search_key) const;
        void print () const;
        void print_level (const int) const;
        
        const int getHeight () const;
        V getValue () const {return value;};
    private:
        Node* rot_l ();
        Node* rot_r ();
        Node* rot_rl ();
        Node* rot_lr ();
        int balance () const;
        void calc_height ();
        
        T key;
        V value;
        Node* left;
        Node* right;
        int height;
        bool deleted;
};

template <typename T, typename V>
class Tree
{
    private:
        Node<T, V>* root;
        Tree (Node<T, V>* rt): root(rt) {};
    public:
        Tree (): root(NULL) {};
        ~Tree () {delete root;}
        
        Tree clone ()
        {
            return Tree(root->clone());
        }
        
        void insert (T key, V value);
        V get (const T& key) const;
        void remove (const T& key) {root->find(key)->remove();};
        
        void print () const;
        void print_level () const;
};