2020-09-18 16:01 已编辑门头沟学院 Java

关注

数据结构---平衡二叉树

文章目录

一、为什么引入平衡二叉树

二、平衡二叉树：（AVL树）

三、平衡二叉树的分析与调整

四、平衡二叉树的实现

一、为什么引入平衡二叉树

效率高！

对比：

二、平衡二叉树：（AVL树）

空树，或者任一结点左、右子树高度差的绝对值不超过1

平衡二叉树，也被称为高度平衡树。相比于”二叉查找树”，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。
平衡二叉树的高度是末尾结点到根节点的路径，即边数。高度为0时，总结点数为1.
设高度为h的平衡二叉树的最少结点数为n（h）。结点数最少时：

三、平衡二叉树的分析与调整

1.分析

当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现平衡因子绝对值大于一的结点

2.平衡调整的四种类型

原则：

降低高度
保持二叉排序树的性质

1. LL型

B结点带左子树一起上升
A结点成为B的右孩子
原来B结点的右子树作为A的左子树

2. RR型

B结点带右子树一起上升
A结点成为B的左孩子
原来B结点的左子树作为A的右子树

图例：

调整后：

3. LR型

C结点穿过A、B结点上升
B结点成为C的左孩子
A结点成为C的右孩子
原来C结点的左子树作为B的右子树
原来C结点的右子树作为A的左子树
C原来的左子树变成上升后的左子树的右子树；原来的右子树变成上升后的右子树的左子树

4. RL型

图例：

调整后：

9原来的左子树变成了上升后的左子树的右子树

四、平衡二叉树的实现

1. 平衡二叉树的结构

与二叉树大致相同，多了节点的高度

typedef struct BinNode
{
   
	int data;
    int height;  //当前节点的高度
	struct BinNode* lchild;
	struct BinNode* rchild;
}BinNode, * BinTree;
//获取当前节点的高度

2. 平衡二叉树的调整

前置函数：

int GetHeight(BinTree tree)          。
{
   
    if(tree == NULL) 
	{
   
		return 0;
	}
    return tree->height;
}
//判断是否平衡 
bool IsBalanced(BinTree tree)         
{
   
    int BF = GetHeight(tree->lchild) - GetHeight(tree->rchild);
    return abs(BF) < 2;
}

int max(int a,int b)
{
   
	return a > b ? a : b;
}

RR型：

BinTree Rotate_RR(BinTree tree)
{
   
    BinTree temp = tree->rchild;
    tree->rchild = temp->lchild;
    temp->lchild = tree;
 
    //更新高度,先更新node再更新temp。
    tree->height = max(GetHeight(tree->lchild),GetHeight(tree->rchild))+1;
    temp->height = max(GetHeight(temp->lchild),GetHeight(temp->rchild))+1;
 
    return temp;
}

LL型：

BinTree Rotate_LL(BinTree tree)
{
   
    BinTree temp = tree->lchild;
    tree->lchild = temp->rchild;
    temp->rchild = tree;
 
    //更新高度,先更新node再更新temp。
    tree->height = max(GetHeight(tree->lchild),GetHeight(tree->rchild))+1;
    temp->height = max(GetHeight(temp->lchild),GetHeight(temp->rchild))+1;
 
    return temp;
}

LR型：

BinTree Rotate_LR(BinTree tree)
{
   
    BinTree temp = tree->lchild;
    tree->lchild = Rotate_RR(temp);
    return Rotate_LL(tree);
}

RL型：

BinTree Rotate_RL(BinTree tree)
{
   
    BinTree temp = tree->rchild;
    tree->rchild = Rotate_LL(temp);
    return Rotate_RR(tree);
}

3. 平衡二叉树的插入

BinTree Insert(BinTree T, char X)//将X插入到AVL树中，并且返回调整后的AVL树
{
   
	if (!T)  //若插入空树，则新建包含一个结点的树
	{
   
		T = (BinTree)malloc(sizeof(BinNode));
		T->data = X;
		T->height = 0;
		T->lchild = T->rchild = NULL;
	}
	else if (X<T->data)    //插入T的左子树 
	{
   
		T->lchild = Insert(T->lchild, X);
		if (GetHeight(T->lchild) - GetHeight(T->rchild) == 2)  //如果需要右旋
		{
   
			if (X<T->lchild->data)
			{
   
				T = Rotate_LL(T); //右单旋
			}
			else
			{
   
 				T = Rotate_LR(T);//左右双旋
 			}
		}
	}
	else if (X>T->data)    //插入T的左子树 
	{
   
		T->rchild = Insert(T->rchild, X);
		if (GetHeight(T->rchild) - GetHeight(T->lchild) == 2)//如果需要左旋
		{
   
			if (X>T->rchild->Data)
			{
   
				T = Rotate_RR(T);//左单旋
			}
			else
			{
   
				T = Rotate_RL(T);//左右双旋
			}
		}
	}
	T->height = max(GetHeight(T->lchild), GetHeight(T->rchild)) + 1;//更新树高
 
	return T;
}