Dutor

typedef int Type; //~ 节点数据类型
typedef struct Node
{
	Type data;
	int bf;
	Node *left, *right;
	Node(){ bf = 0; left = right = 0; }
} AVLNode, *AVLTree; //~ 平衡树及其节点
 
void RRotate(AVLTree & T) //~ 右旋处理,T的左孩子成为新子树根
{
	AVLNode * tmp = T->left;
	T->left = tmp->right;
	tmp->right = T;
	T = tmp;
}
 
void LLotate(AVLTree & T) //~ 左旋处理,T的右孩子成为新子树根
{
	AVLNode * tmp = T->right;
	T->right = tmp->left;
	tmp->left = T;
	T = tmp;
}
 
void LBalance(AVLTree & T) //~ 左平衡处理
{
	AVLNode * l = T->left;
	switch(l->bf)
	{
		case 1: //~ LL,单右旋转
			RRotate(T);
			T->bf = l->bf = 0; //~ 更新平衡因子
			return ;
		case -1: //~ LR双旋转
			AVLNode * lr = l->right;
			switch(lr->bf) //~ 更新平衡因子
			{
				case 1:
					l->bf = 0;
					T->bf = -1;
					break;
				case -1:
					T->bf = 0;
					l->bf = 1;
					break;
			}// switch
			lr->bf = 0;
			LLotate(l);
			RRotate(T);
	}// switch
}
 
void RBalance(AVLTree & T) //~ 右平衡处理
{
	AVLNode * r = T->right;
	switch(r->bf)
	{
		case -1: //~ RR,单左旋转
			LLotate(T);
			T->bf = r->bf = 0;
			return ;
		case 1: //~ RL双旋转
			AVLNode * rl = r->left;
			switch(rl->bf)//~ 更新平衡因子
			{
				case 1:
					r->bf = -1;
					T->bf = 0;
					break;
				case -1:
					T->bf = 1;
					r->bf = 0;
					break;
			}// switch
			rl->bf = 0;
			RRotate(r);
			LLotate(T);
	}// switch
}
bool Insert(AVLTree & T, Type & data) //~ 通过插入操作构建AVL树
{
	bool taller = true; //~ 标识此次插入操作是否使该树长高
	if(!T) //~ 该子树为空树，长高
	{
		T = new AVLNode;
		T->data = data;
		return taller;
	} // if
	if(data == T->data) return false; //~ 该数据已存在，不重复插入
	if(data < T->data) //~ 需要将该数据插入左子树
	{
		if(!Insert(T->left, data)) return false; //~ 左子树未长高
		switch(T->bf) //~ 左子树长高，判断是否需要调整
		{
			case 1: //~ 失衡，许进行左平衡调整
				LBalance(T);
				return false;
			case 0: //~ 未失衡，只需调整当前节点的平衡因子
				T->bf = 1;
				return true;
			case -1: //~ 未失衡，只需调整当前节点的平衡因子
				T->bf = 0;
				return false;
		} // switch
	} // if
	else
	{
		if(!Insert(T->left, data)) return false;
		switch(T->bf)
		{
			case 1: //~ 未失衡，只需调整当前节点的平衡因子
				T->bf = 0;
				return false;
			case 0: //~ 未失衡，只需调整当前节点的平衡因子
				T->bf = -1;
				return true;
			case -1: //~ 失衡，许进行右平衡调整
				RBalance(T);
				return false;
		} // switch
	} // if
}