// exam1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

#define LH -1
#define EH 0
#define RH 1

typedef struct BSTNode
{
	int data;
	int bf;
	struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

void R_Rotate(BSTree &p)
{
	BSTree lc;

	lc=p->lchild;
	p->lchild=lc->rchild;
	lc->rchild=p;
	p=lc;

	return;
}

void L_Rotate(BSTree &p)
{
	BSTree rc;

	rc=p->rchild;
	p->rchild=rc->lchild;
	rc->lchild=p;
	p=rc;

	return;
}

void LeftBalance(BSTree &T)
{
	BSTree lc;
	lc=T->lchild;

	switch(lc->bf)
	{
		case LH:
			T->bf=EH;
			lc->bf=EH;
			R_Rotate(T);
			break;
		case RH:
			BSTree rd;
			rd=lc->rchild;
			switch(rd->bf)
			{
				case LH:
					T->bf=RH;
					lc->bf=EH;
					break;
				case EH:
					T->bf=lc->bf=EH;
					break;
				case RH:
					lc->bf=LH;
					T->bf=EH;
					break;
			}
			rd->bf=EH;
			L_Rotate(lc);
			R_Rotate(T);
	}
}

void RightBalance(BSTree &T)
{
	BSTree rc;

	rc=T->rchild;
	switch(rc->bf)
	{
		case RH:
			T->bf=EH;
			rc->bf=EH;
			L_Rotate(T);
			break;
		case LH:
			BSTree ld;
			ld=rc->lchild;
			switch(ld->bf)
			{
				case LH:
					T->bf=EH;
					rc->bf=RH;
					break;
				case EH:
					T->bf=rc->bf=EH;
					break;
				case RH:
					T->bf=LH;
					rc->bf=EH;
					break;
			}
			ld->bf=EH;
			R_Rotate(rc);
			L_Rotate(T);
	}
}

int InsertAVL(BSTree &T,int e,bool &taller)
{
	if(!T)
	{
		T=(BSTree)malloc(sizeof(BSTNode));
		T->data=http://www.mamicode.com/e;>