数据结构之平衡二叉树(AVL树)

  平衡二叉树(AVL树)定义如下:平衡二叉树或者是一棵空树,或者是具有以下性质的二叉排序树:

  (1)它的左子树和右子树的高度之差绝对值不超过1;

  (2)它的左子树和右子树都是平衡二叉树。

  AVL树避免了平衡二叉树初始序列有序建立的类似单链表情况,提高了查找效率。

  1.AVL树的相关参量定义

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#define DataType int
#define LH 1		//左边高一层
#define EH 0		//左右分支等高
#define RH -1		//右边高一层
const int MAXSIZE = 100;//栈和队列的最大容量
typedef struct BSTNode{
	DataType data;
	int bf;//平衡因子,值为LH、EH、RH
	struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

  2.插入函数

bool InsertAVL(BSTree &T,DataType x,boolean &taller)//插入后是否长高,一处修改处处修改,taller为bool类型
{//插入过程伴随着查找过程,没有则插入
	if (!T)//如果空树,则直接添加新结点
	{
		T = (BSTree)malloc(sizeof(BSTNode));
		T->data = x;
		T->lchild = T->rchild = NULL;
		T->bf = EH;
		taller = true;//长高了
	}
	else
	{
		if (T->data == x)//数据元素已存在,不必插入
		{
			taller = false;
			return false;
		}
		else if (x < T->data)//数据在树根的左分支
		{
			if (!InsertAVL(T->lchild, x, taller))//左分支已存在,但即使不存在也返回了taller的值
				return false;
			if (taller)//如果导致树长高了,则进一步判断及处理
			{
				switch (T->bf)
				{
					case LH://左分支本来就比右分支高一层,又加了一层,当然进行左平衡
						LeftBalence(T);//左调平衡函数
						taller = false;
						break;
					case EH://本来左右等高,修改标志位即可
						T->bf = LH;
						taller = true;
						break;
					case RH://本来右分支高1,修改标志位
						T->bf = EH;
						taller = false;
						break;
				}
			}
		}
		else
		{
			if (!InsertAVL(T->rchild, x, taller))//进行T的右分支,同理
				return false;
			if (taller)
			{
				switch (T->bf)
				{
					case RH:
						RightBalence(T);
						taller = false;
						break;
					case EH:
						T->bf = RH;
						taller = true;
						break;
					case LH:
						T->bf = EH;
						taller = false;
						break;
				}
			}
		}
	}
	return true;
}

  3.着重分析左右调平衡函数

  左调平衡

有且仅有两种情况,一定是原本左边比右边高1层,而且在左边加了1层才要左调平衡的。

(1)

        数据结构之平衡二叉树(AVL树)          数据结构之平衡二叉树(AVL树)         数据结构之平衡二叉树(AVL树)

  这种情况是在原本的根节点T的左孩子L上加了左孩子,显然此时T和L都无右孩子,所以要调整为L为根节点,也就是T根节点右旋(顺时针旋转)。

  调整完显然平衡因子bf变化为  T->bf = L->bf = EH;

(2)另一种是在原本的根节点T的左孩子L上加了右孩子导致失衡(某一结点的做右分支高度相差大于1)产生。

(A)

        数据结构之平衡二叉树(AVL树)    数据结构之平衡二叉树(AVL树)数据结构之平衡二叉树(AVL树)数据结构之平衡二叉树(AVL树) 数据结构之平衡二叉树(AVL树)

  对应(1)的情况,在L加了右孩子Lr,且L无左孩子,T无右孩子。先将L左旋(L逆时针旋转)得到类似(1)的情形,然后将T右旋。

  调整完三个结点平衡因子  T->bf = L->bf =Lr->bf= EH;

(B)此种情况为在L的右孩子Lr上加了左孩子

     数据结构之平衡二叉树(AVL树) 数据结构之平衡二叉树(AVL树)数据结构之平衡二叉树(AVL树)数据结构之平衡二叉树(AVL树) 数据结构之平衡二叉树(AVL树)

  先将L左旋,Lr作为L的双亲结点T的左孩子,L作为Lr的左孩子,Lr的左孩子作为L的右孩子,这也是具体的左旋算法,然后将T右旋。

  调整完三个结点平衡因子    T->bf = RH;   L->bf = EH;   Lr->bf = EH;

(C)此种情况为在L的右孩子Lr上加了右孩子

    数据结构之平衡二叉树(AVL树)数据结构之平衡二叉树(AVL树)数据结构之平衡二叉树(AVL树)数据结构之平衡二叉树(AVL树)数据结构之平衡二叉树(AVL树)

  先将L左旋,然后将T作为Lr的右孩子,且将Lr的右孩子最为T的左孩子,这也是具体的右旋算法。

  调整完三个结点平衡因子 T->bf = EH;  L->bf = LH; Lr->bf = EH;

  注意,此调平衡的规则的代码是递归式的,所以一定是从底层往上层调平衡,也就是说下面先调平衡。

总结(2):具体的也分析了左旋右旋的具体算法,每种情况都有Lr->bf=EH,并且算法都符合平衡二叉树的规则要求。

void R_Rotate(BSTree &T)//右旋,T的左孩子可能有右孩子或者为空,一起整
{
	BSTree p;
	p = T->lchild;
	T->lchild = p->rchild;
	p->rchild = T;
	T=p;
}
void L_Rotate(BSTree &T)//左旋
{
	BSTree p;
	p = T->rchild;
	T->rchild = p->lchild;
	p->lchild = T;
	T = p;
}
void LeftBalence(BSTree &T)//平衡左分支
{
	BSTree L, Lr;
	L = T->lchild;
	switch (L->bf)
	{
		case LH://是在根节点T的左孩子L的左孩子上加了结点导致失衡
			T->bf = L->bf = EH;//调整后的参数变化
			R_Rotate(T);//右旋根节点T
			break;
		case RH://是在根节点T的左孩子L的左孩子上加了结点导致失衡
			Lr = L->rchild;
			switch (Lr->bf)//对L的右孩子Lr的参数bf进行判断及进一步分析
			{
				case LH://Lr的左边加了新结点
					T->bf = RH;
					L->bf = EH;
					break;
				case EH://Lr左右等高
					T->bf = L->bf = EH;
					break;
				case RH://Lr的右边边加了新结点
					T->bf = EH;
					L->bf = LH;
					break;
			}
			//统一改参数,先左旋T的左孩子,再右旋T
			Lr->bf = EH;
			L_Rotate(T->lchild);
			R_Rotate(T);
	}
}

  右调平衡与左调平衡类似的分析方法。

void RightBalence(BSTree &T)//平衡右分支
{
	BSTree R, Rl;
	R = T->rchild;
	switch (R->bf)
	{
		case RH:
			T->bf = R->bf = EH;
			L_Rotate(T);
			break;
		case LH:
			Rl = R->lchild;
			switch (Rl->bf)
			{
				case RH:
					T->bf = LH;
					R->bf = EH;
					break;
				case EH:
					T->bf = R->bf = EH;
					break;
				case LH:
					T->bf = EH;
					R->bf = RH;
					break;
			}
		Rl->bf = EH;
		R_Rotate(T->rchild);
		L_Rotate(T);
	}
}

  4.创建函数及其他函数

void CreatAVL(BSTree &T,int n)//创建AVL树,用到了插入函数
{
	printf("请输入%d个数据:\n", n);
	int a;
	boolean taller = 0;//初始化
	for (int i = 0; i < n; i++)//循环添加
	{
		scanf("%d", &a);
		InsertAVL(T, a,taller);
	}
}
void InOrder(BSTree &T)//中序遍历看是否是递增序列
{
	if (T)
	{
		InOrder(T->lchild);
		printf("%3d", T->data);
		InOrder(T->rchild);
	}
}
void TreeDispNode(BSTree bt)//括号表示法,用来看树的构造情况
{
	if (bt != NULL)
	{
		printf("%d", bt->data);
		if (bt->lchild != NULL || bt->rchild != NULL)
		{
			printf("(");
			TreeDispNode(bt->lchild);
			if (bt->rchild != NULL)printf(",");
			TreeDispNode(bt->rchild);
			printf(")");
		}
	}
}

  5.测试代码

int main()//测试代码
{
	BSTree mytree=NULL;
	CreatAVL(mytree, 10);
	InOrder(mytree);
	printf("\n");
	TreeDispNode(mytree);
	printf("\n");
	system("pause");
	return 0;
}

  注意:代码的相关函数要调整位置,使得被调用的函数在调用其的函数之前,分析调整代码应数形结合。

上一篇:hdu A计划


下一篇:Swift-3-字符串和字符