online compiler and debugger for c/c++

#include <iostream> template<class S, class T> class node { public: S key; T value; node<S, T> *right_node = nullptr, *left_node = nullptr, *nearest_right_node = nullptr, *nearest_left_node = nullptr; int height; public: template<typename, typename> friend class avl_tree; node() = default; node(const S &key, const T &value, node<S, T> *right_node = nullptr, node<S, T> *left_node = nullptr, node<S, T> *nearest_right_node = nullptr, node<S, T> *nearest_left_node = nullptr) : key(key), value(value), right_node(right_node), left_node(left_node), nearest_right_node( nearest_right_node), nearest_left_node( nearest_left_node), height(0) { } ~node() = default; }; template<class S, class T> class avl_tree { public: int get_height(const node<S, T> *ptr); node<S, T> *rotate_right(node<S, T> *ptr); node<S, T> *rotate_left(node<S, T> *ptr); node<S, T> *maximum_node(node<S, T> *ptr); node<S, T> *internal_remove(node<S, T> *ptr, const S &key); node<S, T> *internal_insert(node<S, T> *ptr, const S &key, const T &value); node<S, T> *nearest_left(node<S, T> *ptr, const S &key); node<S, T> *nearest_right(node<S, T> *ptr, const S &key); void update_minimum(); void clear_tree(node<S, T> *ptr); node<S, T> *root = nullptr; node<S, T> *minimal_node = nullptr; avl_tree(); ~avl_tree(); node<S, T> *search(const S &key); void remove(const S &key); void insert(const S &key, const T &value); }; template<class S, class T> avl_tree<S, T>::avl_tree() { root = nullptr; minimal_node = nullptr; } template<class S, class T> int avl_tree<S, T>::get_height(const node<S, T> *ptr) { if (ptr == nullptr) { return 0; } return ptr->height + 1; } template<class S, class T> node<S, T> *avl_tree<S, T>::rotate_right(node<S, T> *ptr) { if (ptr == nullptr) { return nullptr; } node<S, T> *tmp_ptr = ptr->left_node; ptr->left_node = tmp_ptr->right_node; tmp_ptr->right_node = ptr; /* tmp_ptr->parent_node = nullptr; ptr->parent_node = tmp_ptr; if (ptr->left_node != nullptr) ptr->left_node->parent_node = ptr; */ ptr->height = std::max(get_height(ptr->left_node), get_height(ptr->right_node)); tmp_ptr->height = std::max(get_height(tmp_ptr->left_node), get_height(tmp_ptr->right_node)); return tmp_ptr; } template<class S, class T> node<S, T> *avl_tree<S, T>::rotate_left(node<S, T> *ptr) { node<S, T> *tmp_ptr = ptr->right_node; ptr->right_node = tmp_ptr->left_node; tmp_ptr->left_node = ptr; /* tmp_ptr->parent_node = nullptr; ptr->parent_node = tmp_ptr; if (ptr->right_node != nullptr) ptr->right_node->parent_node = ptr; */ ptr->height = std::max(get_height(ptr->left_node), get_height(ptr->right_node)); tmp_ptr->height = std::max(get_height(tmp_ptr->left_node), get_height(tmp_ptr->right_node)); return tmp_ptr; } template<class S, class T> node<S, T> *avl_tree<S, T>::search(const S &key) { node<S, T> *ptr = root; while (ptr != nullptr) { if (key == ptr->key) { break; } if (key < ptr->key) { ptr = ptr->left_node; } else { ptr = ptr->right_node; } } return ptr; } template<class S, class T> node<S, T> *avl_tree<S, T>::internal_insert(node<S, T> *ptr, const S &key, const T &value) { //Standard BST Insert if (ptr == nullptr) { return ptr = new node<S, T>(key, value); } if (key == ptr->key) { return ptr; } if (key < ptr->key) { ptr->left_node = internal_insert(ptr->left_node, key, value); /* ptr->left_node->parent_node = ptr; */ } else { ptr->right_node = internal_insert(ptr->right_node, key, value); /* ptr->right_node->parent_node = ptr; */ } //One node has been inserted int left_node_height = get_height(ptr->left_node); int right_node_height = get_height(ptr->right_node); ptr->height = std::max(left_node_height, right_node_height); int balance_factor = left_node_height - right_node_height; if (balance_factor == 2) { if (key < ptr->left_node->key) { //BF(V_l)>=0 return ptr = rotate_right(ptr); } else { //BF(V_l)==-1 ptr->left_node = rotate_left(ptr->left_node); return ptr = rotate_right(ptr); } } if (balance_factor == -2) { if (key < ptr->right_node->key) { //BF(V_r)==1 ptr->right_node = rotate_right(ptr->right_node); return ptr = rotate_left(ptr); } else { //BF(V_r)<=0 return ptr = rotate_left(ptr); } } return ptr; } template<class S, class T> void avl_tree<S, T>::insert(const S &key, const T &value) { node<S, T> *tmp1 = nearest_right(root, key); node<S, T> *tmp2 = nearest_left(root, key); root = internal_insert(root, key, value); update_minimum(); node<S, T> *new_node = search(key); new_node->nearest_right_node = tmp1; new_node->nearest_left_node = tmp2; if (tmp1 != nullptr) { tmp1->nearest_left_node = new_node; } if (tmp2 != nullptr) { tmp2->nearest_right_node = new_node; } } template<class S, class T> node<S, T> *avl_tree<S, T>::internal_remove(node<S, T> *ptr, const S &key) { //Standard BST Remove if (ptr == nullptr) { return nullptr; } if (key == ptr->key) { if (ptr->left_node == nullptr && ptr->right_node == nullptr) { if (ptr->left_node!= nullptr) ptr->left_node->right_node=ptr->right_node; if (ptr->right_node!= nullptr) ptr->right_node->left_node=ptr->left_node; delete ptr; return nullptr; } else if (ptr->left_node == nullptr && ptr->right_node != nullptr) { node<S, T> *right_tree = ptr->right_node; delete ptr; return right_tree; } else if (ptr->left_node != nullptr && ptr->right_node == nullptr) { node<S, T> *left_tree = ptr->left_node; delete ptr; return left_tree; } else //if (ptr->left_node != nullptr && ptr->right_node != nullptr) { node<S, T> *left_tree = maximum_node(ptr->left_node); /****/ ptr->key = left_tree->key; ptr->value = left_tree->value; ptr->nearest_left_node = left_tree->nearest_left_node; ptr->nearest_right_node = left_tree->nearest_right_node; /****/ ptr->left_node = internal_remove(ptr->left_node, left_tree->key); } } else if (key < ptr->key) { ptr->left_node = internal_remove(ptr->left_node, key); } else //key>ptr->key { ptr->right_node = internal_remove(ptr->right_node, key); } //One node has been removed int left_node_height = get_height(ptr->left_node); int right_node_height = get_height(ptr->right_node); ptr->height = std::max(left_node_height, right_node_height); int balance_factor = left_node_height - right_node_height; if (balance_factor == 2) { if (get_height(ptr->left_node->left_node) > get_height(ptr->left_node->right_node)) { return ptr = rotate_right(ptr); } else { ptr->left_node = rotate_left(ptr->left_node); return ptr = rotate_right(ptr); } } if (balance_factor == -2) { if (get_height(ptr->right_node->left_node) > get_height(ptr->right_node->right_node)) { ptr->right_node = rotate_right(ptr->right_node); return ptr = rotate_left(ptr); } else { return ptr = rotate_left(ptr); } } return ptr; } template<class S, class T> void avl_tree<S, T>::remove(const S &key) { root = internal_remove(root, key); update_minimum(); node<S, T> *tmp1 = nearest_right(root, key); node<S, T> *tmp2 = nearest_left(root, key); if (tmp1 != nullptr) { tmp1->nearest_left_node = tmp2; } if (tmp2 != nullptr) { tmp2->nearest_right_node = tmp1; } } template<class S, class T> node<S, T> *avl_tree<S, T>::maximum_node(node<S, T> *ptr) { if (ptr->right_node == nullptr) { return ptr; } return maximum_node(ptr->right_node); } template<class S, class T> void avl_tree<S, T>::update_minimum() { minimal_node = root; if (root == nullptr) { return; } while (minimal_node->left_node != nullptr) { minimal_node = minimal_node->left_node; } } template<class S, class T> node<S, T> *avl_tree<S, T>::nearest_left(node<S, T> *ptr, const S &key) { node<S, T> *res = nullptr; while (ptr) { if (key < ptr->key) { ptr = ptr->left_node; } else { res = ptr; ptr = ptr->right_node; } } return res; } template<class S, class T> node<S, T> *avl_tree<S, T>::nearest_right(node<S, T> *ptr, const S &key) { node<S, T> *res = nullptr; while (ptr) { if (key < ptr->key || key == ptr->key) { res = ptr; ptr = ptr->left_node; } else { ptr = ptr->right_node; } } return res; } using namespace std; int main() { avl_tree<int, int> *tree = new avl_tree<int, int>(); tree->insert(6, 17); tree->insert(4, 6); tree->insert(3, 10); tree->insert(1, 7); tree->insert(2, 8); tree->insert(5, 99); cout<<tree->search(3)->nearest_right_node->key <<endl; cout<<tree->minimal_node->nearest_right_node->nearest_right_node->nearest_right_node->key<<endl; tree->remove(4); cout<<tree->search(3)->nearest_right_node->key <<endl; cout<<tree->minimal_node->nearest_right_node->nearest_right_node->nearest_right_node->key<<endl; return 0; }