AVL tree

AVL.c

#include<iostream>
#include<algorithm>
using namespace std;

typedef struct Node
{
	Node*left;
	Node*right;
	int value;
	int height;
	Node() { height=value = 0; left = right = NULL; }
}Node;

int Height(Node*p)
{
	if (p == NULL)
		return -1;
	return p->height;
}

void outputre(Node*p, int dep)
{
	if (p == NULL)
		return;
	
	for (int i = 0; i < dep; i++) cout << " ";
	printf("%d (%d) left:%d(%d)  right:%d(%d)\n",p->value,p->height, p->left ? p->left->value : -1, p->left ? p->left->height : -1, 
		p->right ? p->right->value : -1, p->right ? p->right->height : -1);
	outputre(p->left, dep + 1);
	outputre(p->right, dep + 1);
}

void output(Node*p)
{
	cout << "=========" << endl;
	outputre(p, 0);
	cout << "=========" << endl;
}


Node* LLRotate(Node* p)
{
	Node*lr = p->left->right;
	Node*l = p->left;
	p->left = lr;
	l->right = p;

	p->height = max(Height(p->left), Height(p->right)) + 1;
	l->height = max(Height(l->left), Height(l->right)) + 1;
	return l;
}
Node* RRRotate(Node* p)
{
	Node*rl = p->right->left;
	Node*r=p->right;

	p->right = rl;
	r->left = p;

	p->height = max(Height(p->left), Height(p->right)) + 1;
	r->height = max(Height(r->left), Height(r->right)) + 1;

	return r;
}


Node*LRRotate(Node*p)
{
	p->left = RRRotate(p->left);
	return LLRotate(p);
}

Node*RLRotate(Node*p)
{
	p->right = LLRotate(p->right);
	return RRRotate(p);
}

Node* insert(Node*p, int val)
{
	if (p == NULL)
	{
		p = new Node();
		p->value = val;
		return p;
	}

	if (val < p->value)
	{
		p->left = insert(p->left, val);
		if (Height(p->left) - Height(p->right) == 2)
		{
			if (val < p->left->value) // LL
			{
				p=LLRotate(p);
			}
			else // LR
			{
				p=LRRotate(p);
			}
		}
	}
	else
	{
		p->right = insert(p->right, val);
		if (Height(p->right) - Height(p->left) == 2)
		{
			if (val < p->right->value) // RL
			{
				p = RLRotate(p);
			}
			else //RR
			{
				p = RRRotate(p);
			}
		}
	}
	p->height = max(Height(p->left), Height(p->right)) + 1;
	return p;
}
int main()
{
	Node*root = NULL;
	for (int i = 0; i < 30; i++)
	{
		root = insert(root, rand() % 100);
		output(root);
	}
		
	return 0;
}