AVL平衡二叉树如何旋转

前置知识：二叉搜索树 BST

1. AVL 树的性质

1. 任一结点的左、右子树均为 AVL 树
2. 根节点左、右子树高度差的绝对值不超过1

2. AVL 树的自平衡

在插入或删除结点时，会引起子树的高度变化，当破坏了性质2时，就需要进行一次局部的“旋转调整”，这个过程分为两步：

1. 找到失衡点
2. 进行旋转

2.1 平衡因子

首先引入平衡因子（Balance Factor，BF）的概念

平衡因子的定义为：对于二叉树中的任一结点 T，其平衡因子 BF(T) = h_L - h_R

对于叶子结点，BF(T) 总为 0

根据性质2可以得知，一棵 AVL 树中任一结点的平衡因子只能在集合{-1, 0, 1}中取值。这就是平衡的量化标准。

当一个结点的平衡因子绝对值超过 1 时，也就意味着 AVL 树的平衡被破坏

2.2 不平衡的四种形态

2.3 旋转

2.3.1 RR

如图是 RR 失衡，省略了 A、B、C 三个结点的子树。

这里没有标出 A 结点的平衡因子，是因为引起失衡的情况复杂：

1. A 是叶子结点，则 BF(A) = 0
2. A 含有子树，则根据情况不同，BF(A) 可能为 1 或 -1

应对这种失衡，我们需要将 C 逆时针旋转，恰好与 RR 的方向相反，逆时针是向左，切记不要搞混了，RR 描述的仅仅是失衡方向，

为了方便讲解，我将对 RR 失衡的旋转简单地定义为 RR(X)

右单旋的步骤很简单，RR(X) 只需要以 X 结点的右子结点为轴，将 X 向左旋转即可

如下图中 RR(C) 以 C 的右子结点 B 为轴，将 C 向左旋转

当然上图中这是没有子树的理想情况。

如果 A、B、C 三个结点含有子树，那么：

1. A 的子树保持不变，毕竟 A 都没参与旋转

2. C 的左子树保持不变，因为也跟旋转无关

3. 唯一需要变化的就是 B 的左子树了，因为把 C 拉下来之后，C 就成为了 B 的左子树，这和 B 原本的左子树冲突了。

   根据 BST 的性质，旋转前，B 的左子树中任一结点的值都大于 C 结点，而当 C 被旋转下来之后就失去了原本的右子树 B，所以左旋之后我们要做的只剩下将 B 结点的左子树变成 C 结点的右子树，如下图

既然这次左旋成功地把结点 B 的根结点 C 给转了下来，那么总得有人顶上根结点的缺失漏洞，没错就是 B 结点。

至此，AVL 树又恢复了平衡

2.3.2 LL

LL 失衡与 RR 同理，只不过刚好对称，不再详细介绍

2.3.3 RL

在学习 RL 前，请先熟练掌握上面两种情况中的左旋与右旋操作

RL 叫右—左双旋，顾名思义，就是进行两次旋转

但是需要注意的是，和单旋的名称一样，右—左双旋这个名词中的两个方向并不是旋转方向，他们指代的仅仅是失衡的路径方向：

以结点 X 为根，向它的右子树的左子树中插入结点时失衡，那么这种情况就是 RL，如下图所示

与 2.3.1 RR 一样，上图省略了三个结点的子树。结点 A 不标出平衡因子的原因也不再叙述

右—左双旋按顺序分别是左单旋和右单旋。当然两次旋转的并不是同一个结点

以下图为例，RL(C) = LL(B) + RR(C)

具体步骤

经过一次 LL 右旋后，又回到了熟悉的 RR

流程简化——一步到位

熟悉以上的两步旋转操作后，可以将它们合为一步

1. 将 A 的左子树变成 C 的右子树（下图红色部分）
2. 将 A 的右子树变成 B 的左子树（下图绿色部分）
3. 最后再将 A 变为根节点，左结点为 C，右节点为 B

2.3.4 LR

LR 与 RL 同理

3. AVL 旋转的算法实现

3.0 结构体与公共方法

结点的结构体

// 结构体，需要有四个属性，自身的值、左子结点、右子结点、自身的高度
// 其他语言如 java 可以使用类来代替结构体
struct Node {
	int val;
	Node* left = nullptr;
	Node* right = nullptr;
	int h;
    // 构造器，可以不写然后手动赋值
	Node(int v, int h):val(v), h(h){}
};

公共方法

// 获取一个结点的高度
int getH(Node* node) {
    // 如果结点是空指针，那当然高度是0
	if (nullptr == node) {
		return 0;
	}
    // 否则返回结点的高度
	return node->h;
}

3.1 RR

// 示意图在下方
Node* RR(Node* C) {
    // 旋转结点
	Node* B = C->right;
	C->right = B->left;
	B->left = C;
    // 更新高度
	C->h = std::max(getH(C->left), getH(C->right)) + 1;
	B->h = std::max(getH(C), getH(B->right)) + 1;
    // 返回这棵子树新的根节点
	return B;
}

3.2 LL

与 RR 相同，这里只给出代码不在贴图（实际上是因为懒）

Node* LL(Node* C) {
	Node* B = C->left;
	C->left = B->right;
	B->right = C;
	C->h = std::max(getH(C->left), getH(C->right)) + 1;
	B->h = std::max(getH(C), getH(B->left)) + 1;
	return B;
}

3.3 RL

在 2.3.3 RL 中我提到了：RL 可以分为两次旋转，也可以一步到位

这两种方法各有优势，两次旋转的代码实现简单，一步到位在打草稿的时候速度快

两次旋转

Node* RL(Node* C) {
	C->right = LL(C->right);
	return RR(C);
}

一步到位

仔细看代码的话也会发现，这仅仅是把上面两次旋转调用的方法里的代码合并了而已。所以这个方法还是适用于打草稿

Node* RL(Node* C) {
	Node* B = C->right;
	Node* A = B->left;
	B->left = A->right;
	C->right = A->left;
	A->left = C;
	A->right = B;
	C->h = std::max(getH(C->left), getH(C->right)) + 1;
	B->h = std::max(getH(B->left), getH(B->right)) + 1;
	A->h = std::max(getH(C), getH(B)) + 1;
	return A;
}

3.4 LR

两次旋转

Node* LR(Node* C) {
	C->left = RR(C->left);
	return LL(C);
}

一步到位

Node* LR(Node* C) {
	Node* B = C->left;
	Node* A = B->right;
	B->right = A->left;
	C->left = A->right;
	A->left = B;
	A->right = C;
	C->h = std::max(getH(C->left), getH(C->right)) + 1;
	B->h = std::max(getH(B->left), getH(B->right)) + 1;
	A->h = std::max(getH(C), getH(B)) + 1;
	return A;
}

3.5 题目

光旋转部分的算法没办法体验，所以用这道简单的插入来介绍旋转算法

题目详情 - 1066 Root of AVL Tree (25 分) (pintia.cn)

虽然题目是英文的，但是不难理解。

题目给出 AVL 树中依次插入的结点值，要你给出最后平衡后的根节点值

---

这篇文章只介绍 AVL 树的旋转，所以不再介绍插入或删除的实现。

下面给出这道题的 AC 代码

#include<bits/stdcpp.h>

struct Node {
	int val;
	Node* left = nullptr;
	Node* right = nullptr;
	int h;
	Node(int v, int h):val(v), h(h){}
};
int getH(Node* node) {
	if (nullptr == node) {
		return 0;
	}
	return node->h;
}
Node* LL(Node* A) {
	Node* B = A->left;
	A->left = B->right;
	B->right = A;
	A->h = std::max(getH(A->left), getH(A->right)) + 1;
	B->h = std::max(getH(A), getH(B->left)) + 1;
	return B;
}
Node* RR(Node* A) {
	Node* B = A->right;
	A->right = B->left;
	B->left = A;
	A->h = std::max(getH(A->left), getH(A->right)) + 1;
	B->h = std::max(getH(A), getH(B->right)) + 1;
	return B;
}
Node* LR(Node* A) {
	A->left = RR(A->left);
	return LL(A);
}
Node* RL(Node* A) {
	A->right = LL(A->right);
	return RR(A);
}
Node* insert(Node* T, int val) {
	if (nullptr == T) {
		return new Node(val, 1);
	} else if (val < T->val) {
		T->left = insert(T->left, val);
		if (abs(getH(T->left) - getH(T->right)) == 2) {
			if (val < T->left->val) {
				T = LL(T);
			} else {
				T = LR(T);
			}
		}
	} else {
		T->right = insert(T->right, val);
		if (abs(getH(T->left) - getH(T->right)) == 2) {
			if (val > T->right->val) {
				T = RR(T);
			} else {
				T = RL(T);
			}
		}
	}
	T->h = std::max(getH(T->left), getH(T->right)) + 1;
	return T;
}
int main() {
	int n;
	std::cin >> n;
	Node* root = nullptr;
	for (int i = 0; i < n; i++) {
		int x;
		std::cin >> x;
		root = insert(root, x);
	}
	std::cout << root->val;
}