#include <iostream>
#include <vector>
#ifndef AVL_TREE_HPP
#define AVL_TREE_HPP
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
template <class T>
struct AVLNode {
T data;
int height = 0;
AVLNode<T>* left = nullptr, * right = nullptr, * parent = nullptr;
AVLNode(T t) : data(t) {}
AVLNode(T t, AVLNode<T>* p) : data(t), parent(p) {}
};
template <class T> class AVLTree {
public:
AVLNode<T>* root = nullptr;
void insert(AVLNode<T>*, T);
int update_height(AVLNode<T>*);
int check_balance(AVLNode<T>*);
AVLNode<T>* left_rotate(AVLNode<T>*);
AVLNode<T>* right_rotate(AVLNode<T>*);
void double_left_rotate(AVLNode<T>*);
void double_right_rotate(AVLNode<T>*);
void serialize(AVLNode<T>*, std::stringstream&);
void clear();
void remove(int);
void insert(T);
std::string serialize(); // helper that calls a recursive
public:
AVLTree() {}
~AVLTree() {}
private:
AVLNode<T>* removeUtil(AVLNode<T>* ,int);
AVLNode<T>* maxValueNode(AVLNode<T>* node);
void clearUtil(AVLNode<T>* n);
};
template <class T>
void AVLTree<T>::remove(int key) {
root=removeUtil(root,key);
return;
}
template <class T>
AVLNode<T>* AVLTree<T>::maxValueNode(AVLNode<T>* node)
{
AVLNode<T>* current = node;
/* loop down to find the leftmost leaf */
while (current->right != NULL)
current = current->right;
return current;
}
template <class T>
AVLNode<T>* AVLTree<T>::removeUtil(AVLNode<T>* root,int key){
if (root == NULL)
return root;
// If the key to be deleted is smaller than the
// root's key, then it lies in left subtree
if ( key < root->data )
root->left= removeUtil(root->left, key);
// If the key to be deleted is greater than the
// root's key, then it lies in right subtree
else if( key > root->data )
root->right= removeUtil(root->right, key);
// if key is same as root's key, then This is
// the node to be deleted
else
{
// node with only one child or no child
if( (root->left == NULL) || (root->right == NULL) )
{
AVLNode<T>* temp = root->left ? root->left :
root->right;
// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
return NULL;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
delete temp;
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
AVLNode<T> *temp = maxValueNode(root->left);
// Copy the inorder successor's data to this node
root->data = temp->data;
// Delete the inorder successor
root->left = removeUtil(root->left, temp->data);
}
}
// If the tree had only one node then return
if (root == NULL)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = 1 + std::max(update_height(root->left),
update_height(root->right));
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to
// check whether this node became unbalanced)
int balance = check_balance(root);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && check_balance(root->left) >= 0)
return right_rotate(root);
// Left Right Case
if (balance > 1 && check_balance(root->left) < 0)
{
root->left = left_rotate(root->left);
return right_rotate(root);
}
// Right Right Case
if (balance < -1 && check_balance(root->right) <= 0)
return left_rotate(root);
// Right Left Case
if (balance < -1 && check_balance(root->right) > 0)
{
root->right = right_rotate(root->right);
return left_rotate(root);
}
return root;
}
template <class T>
void AVLTree<T>::clear() {
while(root!=NULL){
clearUtil(root);
}
}
template <class T>
void AVLTree<T>::clearUtil(AVLNode<T>* n) {
if (n!= NULL)
{
clearUtil(n->left);
clearUtil(n->right);
remove(n->data);
}
return;
}
template <class T>
int AVLTree<T>::update_height(AVLNode<T>* n) {
if (!n)
return 0;
n->height = 1 + std::max(n->left ? n->left->height : -1, n->right ? n->right->height : -1);
return n->height;
}
template <class T>
int AVLTree<T>::check_balance(AVLNode<T>* n) {
return (n->left ? n->left->height : -1) - (n->right ? n->right->height : -1);
}
template <class T>
AVLNode<T>* AVLTree<T>::left_rotate(AVLNode<T>* n) {
AVLNode<T>* p = n;
AVLNode<T>* m = n->right;
p->right = m->left;
if (m->left)
m->left->parent = p;
m->parent = n->parent;
m->left = p;
p->parent = m;
if (!m->parent)
root = m;
else
m->data < m->parent->data ? m->parent->left = m : m->parent->right = m;
update_height(p);
update_height(m);
return m;
}
template <class T>
AVLNode<T>* AVLTree<T>::right_rotate(AVLNode<T>* n) {
AVLNode<T>* p = n;
AVLNode<T>* m = n->left;
p->left = m->right;
if (m->right)
m->right->parent = p;
m->parent = n->parent;
m->right = p;
p->parent = m;
if (!m->parent)
root = m;
else
m->data < m->parent->data ? m->parent->left = m : m->parent->right = m;
update_height(p);
update_height(m);
return m;
}
template <class T>
void AVLTree<T>::double_left_rotate(AVLNode<T>* n) {
right_rotate(n->right);
left_rotate(n);
}
template <class T>
void AVLTree<T>::double_right_rotate(AVLNode<T>* n) {
left_rotate(n->left);
right_rotate(n);
}
template <class T>
void AVLTree<T>::insert(T t) {
if (!root) {
root = new AVLNode<T>(t);
return;
}
insert(root, t); // recursive function call
}
template <class T>
void AVLTree<T>::insert(AVLNode<T>* n, T t) {
if (n->data == t)
return;
if (n->data > t) {
if (n->left) {
insert(n->left, t);
} else {
n->left = new AVLNode<T>(t, n);
}
} else {
if (n->right) {
insert(n->right, t);
} else {
n->right = new AVLNode<T>(t, n);
}
}
update_height(n);
int bf = check_balance(n);
if (bf < -1) {
if (check_balance(n->right) > 0) {
double_left_rotate(n);
} else {
left_rotate(n);
}
} else if (bf > 1) {
if (check_balance(n->left) < 0) {
double_right_rotate(n);
} else {
right_rotate(n);
}
}
}
template <class T>
std::string AVLTree<T>::serialize() {
std::stringstream ret;
serialize(root, ret);
return ret.str();
}
template <class T>
void AVLTree<T>::serialize(AVLNode<T>* n, std::stringstream& s) {
if (!n) {
s << "[/]";
return;
}
s << "[" << n->data << "]";
serialize(n->left, s);
serialize(n->right, s);
}
#endif
using namespace std;
int main() {
AVLTree<int> avl;
std::cout << "----------------------------------------------------" << std::endl;
for (auto x : { 1, 2, 3, 4, 5, 6, 7 })
{
avl.insert(x);
}
std::cout << avl.serialize() << std::endl;
std::cout << "----------------------------------------------------\n" << std::endl;
avl.clear();
std::cout << "----------------------------------------------------" << std::endl;
for (auto x : { 30, 10, 50, 48, 20 })
{
avl.insert(x);
}
std::cout << avl.serialize() << std::endl;
std::cout << "----------------------------------------------------\n" << std::endl;
avl.clear();
std::cout << "----------------------------------------------------" << std::endl;
for (auto x : { 1, 2, 3, 4, 5, 6, 7 })
avl.insert(x);
for (auto x : { 4, 3 })
avl.remove(x);
std::cout << avl.serialize() << std::endl;
std::cout << "----------------------------------------------------\n" << std::endl;
avl.clear();
std::cout << "----------------------------------------------------" << std::endl;
for (auto x : { 10, 5, 15, 9, 8, 7, 6 })
{
avl.insert(x);
}
for (auto x : { 10, 9 })
{
avl.remove(x);
}
for (auto x : { 30, 10, 11, 12 })
{
avl.insert(x);
}
std::cout << avl.serialize() << std::endl;
std::cout << "----------------------------------------------------\n" << std::endl;
avl.clear();
}