查找算法【平衡二叉树】 - 原理 AVL树详解

查找算法【平衡二叉树】 - 原理 AVL树详解

平衡二叉查找树，简称平衡二叉树，由苏联数学家Adelson-Velskii和Landis提出，所以又被称为AVL树。

平衡二叉树或为空树，或为具有以下性质的平衡二叉树：

• ①左右子树高度差的绝对值不超过1；
• ②左右子树也是平衡二叉树。

节点左右子树的高度之差被称为平衡因子。在二叉查找树中，每个节点的平衡因子的绝对值不超过1即平衡二叉树。

例如，一棵平衡二叉树及其平衡因子如下图所示。

那么在这棵平衡二叉树中插入20，结果会怎样？如下图所示，

插入20之后，从该叶子到树根路径上的所有节点，平衡因子都有可能改变，出现不平衡，有可能有多个节点的平衡因子的绝对值超过1。**从新插入的节点向上，找离新插入节点最近的不平衡节点，以该节点为根的子树被称为最小不平衡子树。**只需将最小不平衡子树调整为平衡二叉树即可，其他节点不变。

平衡二叉树除了具有适度平衡性，还具有局部性：

• ①在单次插入、删除后，至多有O (1)处出现不平衡；

• ②总可以在O (logn )时间内，使这O (1)处不平衡重新调整为平衡。

对平衡二叉树在动态修改后出现的不平衡，只需局部（最小不平衡子树）调整平衡即可，不需要对整棵树进行调整。

【如何进行局部调整平衡？】

【1】调整平衡的方法

以插入操作为例，调整平衡可以分为4种情况：LL型、RR型、LR型、RL型。

① LL型

插入新节点x 后，从该节点向上找到最近的不平衡节点A，如果最近不平衡节点到新节点的路径前两个都是左子树L，就是LL型。也就是说，**将节点x 插入A的左子树的左子树中，A的左子树因插入新节点而高度增加，造成A的平衡因子由1增加为2，失去平衡。**需要进行LL旋转（顺时针）调整平衡。

LL旋转：A顺时针旋转到B的右子树，B原来的右子树T3 被抛弃，A旋转后正好左子树空闲，将这个被抛弃的子树T3 放到A的左子树中即可，如下图所示。

进行每一次旋转时，总有一个子树被抛弃，一个指针空闲，它们正好配对。旋转之后，是否平衡呢？旋转之后，A、B两个节点的左右子树高度之差均为0，满足平衡条件，C的左右子树未变，仍然平衡。

AVLTree LL_Rotation(AVLTree &T){ //LL旋转
	AVLTree temp = T->lchild;  //T为指向不平衡节点的指针
	T->lchild = temp->rchild;
	temp->rchild = T;
	updateHeight(T); //更新高度
	updateHeight(temp);
	
	return temp;
}
1
2
3
4
5
6
7
8
9

② RR 型

插入新节点x 后，从该节点向上找到最近不平衡节点A，如果最近不平衡节点到新节点的路径前两个都是右子树R，就是RR型。需要进行RR旋转（逆时针）调整平衡。

【将节点x 插入A的右子树的右子树中，A的右子树因插入新节点而高度增加，造成A的平衡因子由1增加为2，失去平衡】

RR旋转：A逆时针旋转到B的左子树，B原来的左子树T2 被抛弃，A旋转后正好右子树空闲，将这个被抛弃的子树T2 放到A右子树中即可，如下图所示。

旋转后，A、B的左右子树高度之差均为0，满足平衡条件，C的左右子树未变，仍然平衡。

AVLTree RR_Rotation(AVLTree &T){ //RR旋转
	
	AVLTree temp = T->rchild;
	T->rchild = temp->lchild;
	temp->lchild = T;
	updateHeight(T); //更新高度
	updateHeight(temp);
	return temp;
}
1
2
3
4
5
6
7
8
9

③ LR 型

插入新节点x 后，从该节点向上找到最近不平衡节点A，如果最近不平衡节点到新节点的路径前两个依次是左子树L、右子树R，就是LR型。【先左后右，插入】

LR旋转：分两次旋转。C逆时针旋转到A、B之间，C原来的左子树T2被抛弃，B正好右子树空闲，将这个被抛弃的子树T2 放到B右子树中；这时已经转变为LL型，进行LL旋转即可，如下图所示。实际上，也可以看作C固定不动，B进行RR旋转，然后进行LL旋转。

旋转后，A、C的左右子树高度之差均为0，满足平衡条件，B的左右子树未变，仍然平衡。

AVLTree LR_Rotation(AVLTree &T){ //LR旋转
	T->lchild = RR_Rotation(T->lchild);
	return LL_Rotation(T);
}
1
2
3
4

④ RL 型

插入新节点x 后，从该节点向上找到最近不平衡节点A，如果最近不平衡节点到新节点的路径前两个依次是右子树R、左子树L，就是RL型。

RL旋转：分两次旋转。C顺时针旋转到A、B之间，C原来的右子树T3被抛弃，B正好左子树空闲，这个被抛弃的子树T3 放到B左子树；这时已经转变为RR型，做RR旋转即可，如下图所示。实际上，也可以看作C固定不动，B进行LL旋转，然后进行RR旋转。

旋转后，A、C的左右子树高度之差均为0，满足平衡条件，B的左右子树未变，仍然平衡。

AVLTree RL_Rotation(AVLTree &T){ //RL旋转
	T->rchild = LL_Rotation(T->rchild);
	return RR_Rotation(T);
}
1
2
3
4