#pragma once
#include <iostream>
#include <vector>
using namespace std;

class avl
{
private:
	class node
	{
	public:
		double data;
		node* left;
		node* right;

		int height; //height in tree

		node(double x)
		{
			data = x;
			left = nullptr;
			right = nullptr;
			height = 0;
		}
	};

	node* root;

	//return height of node p
	int height(node* p)
	{
		if (p == nullptr)
			return -1;
		else
			return p->height;
	}

	void updateHeight(node* p)
	{
		p->height = 1 + max(height(p->left), height(p->right));
	}

	void leftRotation(node*& p)
	{
		//Give some names to keep sanity
		node* A = p;
		node* B = p->right;
		node* bleft = B->left;

		A->right = bleft;
		B->left = A;
		p = B;

		//heights got SUS, fix them
		updateHeight(A);
		updateHeight(B);
	}


	void rightRotation(node*& p)
	{
		//Give some names to keep sanity
		node* A = p;
		node* B = p->left;
		node* bright = B->right;

		A->left = bright;
		B->right = A;
		p = B;

		//heights got SUS, fix them
		updateHeight(A);
		updateHeight(B);
	}

	void rightLeftDouble(node*& p)
	{
		rightRotation(p->right);
		leftRotation(p);
	}

	void leftRightDouble(node*& p)
	{
		leftRotation(p->left);
		rightRotation(p);
	}

	//Uh oh! p's balance is SUS! check if it is AVL balanced,
	//if not, apply the proper rotation.
	void checkBalanceRotate(node*& p)
	{
		//check the 4 cases for imbalance
		if (height(p->right) > height(p->left) + 1)
		{
			if (height(p->right->right) > height(p->right->left))
			{
				leftRotation(p);
			}
			else
			{
				rightLeftDouble(p);
			}
		}
		else if (height(p->left) > height(p->right) + 1)
		{
			if (height(p->left->left) > height(p->left->right))
			{
				rightRotation(p);
			}
			else
			{
				leftRightDouble(p);
			}
		}
		else
		{
			//cool, node is not SUS.
		}
	}

	//print all items in tree rooted
	//at node p
	//in-order traversal
	void recInsert(node*& p, double x)
	{
		if (p == nullptr)
			p = new node(x);
		else
		{
			if (x < p->data)
				recInsert(p->left, x);
			else
				recInsert(p->right, x);

			updateHeight(p);
			checkBalanceRotate(p);
		}
	}

	//print all items in tree rooted
	//at node p
	//in-order traversal
	void recDisplay(node* p)
	{
		if (p == nullptr) //base case
		{
			//do nothing! no items to print!!!
			//saveing so much programming time!!!
		}
		else //recursive case
		{
			recDisplay(p->left);
			cout << p->data << endl;
			recDisplay(p->right);
		}
	}

public:
	avl()
	{
		root = nullptr;
	}


	void insert(double x)
	{
		recInsert(root, x);
	}

	void display()
	{
		recDisplay(root);
	}

	int height()
	{
		return height(root);
	}
};