rendered paste body#include <cstdlib> // for NULLclass 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;};