定义：

平衡二叉树(AVL)：是一种平衡的二叉搜索树。
平衡因子：将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)，|BF|<=1。

性质：

1. 空二叉树是一个 AVL 树
2. 如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且|h(ls)-h(rs)| <= 1 ，h 是其左右子树的高度
3. 树高为O(log n)
4. 它必须是二叉搜索树。

插入节点：

与 BST（二叉搜索树）中类似，先进行一次失败的查找来确定插入的位置，插入节点后根据平衡因子来决定是否需要调整。

参考代码

//获取高度
int getHeight(Node *root)
{
	if (root == NULL)
		return 0;
	return max(getHeight(root->l), getHeight(root->r)) + 1;
}
//获取平衡因子
int getBalance(Node *root)
{
	return getHeight(root->l) - getHeight(root->r);
}

//节点插入
void insert(Node *&root, int x)
{
	if (root == NULL)
	{
		root = new Node();
		root->data = x;
		root->l = root->r = NULL;
		return;
	}
	if (x <= root->data)
	{
		//插入完成后
		insert(root->l, x);
		//进行平衡调整
		if (getBalance(root) == 2)
		{
			// LL型，右旋
			if (getBalance(root->l) == 1)
			{
				R(root);
			}
			// LR型，先对左子树左旋，再整体右旋
			else if (getBalance(root->l) == -1)
			{
				LR(root);
			}
		}
	}
	else
	{
		insert(root->r, x);
		if (getBalance(root) == -2)
		{
			// RR型，左旋
			if (getBalance(root->r) == -1)
			{
				L(root);
			}
			// RL型，先对右子树右旋再整体左旋
			else if (getBalance(root->r) == 1)
			{
				RL(root);
			}
		}
	}
}

删除节点（未实现，待补）：

1. 删除和 BST 类似，将结点与后继交换后再删除。
2. 删除会导致树高以及平衡因子变化，这时需要沿着被删除结点到根的路径来调整这种变化。

平衡的维护：

主要分以下4种平衡维护情况：
1.LL型
由于在A的左子树（L）的左子树（L）上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1增至2。下图是LL型的最简单形式,显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B顺时针旋转一样。（这里我们称为右旋）

一般形式如下图所示，表示在A的左孩子B的左子树BL(不一定为空)中插入结点C而导致不平衡( h 表示子树的深度)。
这种情况调整如下：
a.将A的左孩子B提升为新的根结点；
b.将原来的根结点A降为B的右孩子；
c.各子树按大小关系连接(BL和AR不变，BR调整为A的左子树)。

参考代码

//右旋
void R(Node *&root)
{
	Node *tmp = root->l;
	root->l = tmp->r;
	tmp->r = root;
	root = tmp;
}

2.RR型
由于在A的右子树（R）的右子树（R）上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。下图是RR型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B逆时针旋转一样。(这里我们称为左旋）

RR型调整的一般形式如下图所示，表示在A的右孩子B的右子树BR(不一定为空)中插入结点C而导致不平衡( h 表示子树的深度)。
这种情况调整如下：
a.将A的右孩子B提升为新的根结点；
b.将原来的根结点A降为B的左孩子
c.各子树按大小关系连接(AL和BR不变，BL调整为A的右子树)。

参考代码

//左旋
void L(Node *&root)
{
	Node *tmp = root->r;
	root->r = tmp->l;
	tmp->l = root;
	root = tmp;
}

3.LR型
由于在A的左孩子（L）的右子树（R）上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1变为2。下图是LR型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。

LR型调整的一般形式如下图所示，表示在A的左孩子B的右子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。
这种情况调整如下：
将B的左孩子C提升为新的根结点；
将原来的根结点A降为C的右孩子；
各子树按大小关系连接(BL和AR不变，CL和CR分别调整为B的右子树和A的左子树)。

示例操作：

参考代码

//先左旋再右旋
void LR(Node *&root)
{
	L(root->l);
	R(root);
}

4.RL型
由于在A的右孩子（R）的左子树（L）上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。下图是RL型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。

RL型调整的一般形式如下图所示，表示在A的右孩子B的左子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。
这种情况调整如下：
将B的左孩子C提升为新的根结点；
将原来的根结点A降为C的左孩子；
各子树按大小关系连接(AL和BR不变，CL和CR分别调整为A的右子树和B的左子树)。

示例操作：

参考代码

//先右旋再左旋
void RL(Node *&root)
{
	R(root->r);
	L(root);
}

例题：PAT-甲级 1123 Is It a Complete AVL Tree（板子题）

Question:

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤ 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print YES if the tree is complete, or NO if not.

Sample Input 1:

5
88 70 61 63 65

Sample Output 1:

70 63 88 61 65
YES

Sample Input 2:

8
88 70 61 96 120 90 65 68

Sample Output 2:

88 65 96 61 70 90 120 68
NO

参考代码：

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define PIII pair<int, PII>
#define PSI pair<string, int>
#define PIIS pair<int, pair<int, string>>
#define PDD pair<double, double>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 5;
const int M = 1e5;
const int mod = 1e9 + 7;

struct Node
{
	int data, pos;
	Node *l, *r;
};
//获取高度
int getHeight(Node *root)
{
	if (root == NULL)
		return 0;
	return max(getHeight(root->l), getHeight(root->r)) + 1;
}
//获取平衡因子
int getBalance(Node *root)
{
	return getHeight(root->l) - getHeight(root->r);
}
//左旋
void L(Node *&root)
{
	Node *tmp = root->r;
	root->r = tmp->l;
	tmp->l = root;
	root = tmp;
}
//右旋
void R(Node *&root)
{
	Node *tmp = root->l;
	root->l = tmp->r;
	tmp->r = root;
	root = tmp;
}
// LR型
void LR(Node *&root)
{
	L(root->l);
	R(root);
}
// RL型
void RL(Node *&root)
{
	R(root->r);
	L(root);
}
void insert(Node *&root, int x)
{
	if (root == NULL)
	{
		root = new Node();
		root->data = x;
		root->l = root->r = NULL;
		return;
	}
	if (x <= root->data)
	{
		//插入完成后
		insert(root->l, x);
		//进行平衡调整
		if (getBalance(root) == 2)
		{
			// LL型，右旋
			if (getBalance(root->l) == 1)
			{
				R(root);
			}
			// LR型，先对左子树左旋，再整体右旋
			else if (getBalance(root->l) == -1)
			{
				L(root->l);
				R(root);
			}
		}
	}
	else
	{
		insert(root->r, x);
		if (getBalance(root) == -2)
		{
			// RR型，左旋
			if (getBalance(root->r) == -1)
			{
				L(root);
			}
			// RL型，先对右子树右旋再整体左旋
			else if (getBalance(root->r) == 1)
			{
				R(root->r);
				L(root);
			}
		}
	}
}
int n;
int main()
{
	// io;
	cin >> n;
	Node *root = NULL;
	for (int i = 0, x; i < n; i++)
	{
		cin >> x;
		insert(root, x);
	}

	queue<Node *> heap;
	root->pos = 1;
	heap.push(root);
	int m = 0;
	while (heap.size())
	{
		auto tmp = heap.front();
		heap.pop();
		if (tmp->pos == 1)
			cout << tmp->data;
		else
			cout << " " << tmp->data;
		m = max(m, tmp->pos);

		if (tmp->l != NULL)
		{
			tmp->l->pos = (tmp->pos) * 2;
			heap.push(tmp->l);
		}
		if (tmp->r != NULL)
		{
			tmp->r->pos = (tmp->pos) * 2 + 1;
			heap.push(tmp->r);
		}
	}
	if (m <= n)
		cout << "\nYES";
	else
		cout << "\nNO";
	// system("pause");
	return 0;
}
/*

*/

✅作者简介：大家好，我是小鱼儿，大家可以叫我鱼儿

📒博客首页：是小鱼儿哈

🔥系列专栏：一起刷好题

🌻每日一句：勤奋这把可能变成现实，懒惰者把甜作苦受

💖博主也在学习阶段，如发现问题请告知，非常感谢💖

再解答平衡二叉树这个问题前，我们先来看这样一个题目

​

📝这个问题我们可以转换为子问题求解，如果我们知道了该二叉树的左子树和右子树的最大深度就相当于知道了该二叉树的深度，同样左子树和右子树也有各自他们所对应的左子树和右子树，这样我们还需要求他们各自的左右子树的深度，这就是一个从上到下的递归过程。

把一个大规模的问题，拆分为多个小规模的子问题
🌰要求3为根节点的二叉树深度：
🌰以9为根节点的二叉树的深度x
🌰以20为根节点的二叉树的深度y
答案=Max(9为根节点的二叉树的深度x,20为根节点的二叉树的深度y)+1

 

 

public int maxDepth(TreeNode root) {
        if (root == null) return 0; // 递归结束的条件，root节点为null,深度自然为0
        int leftHeight = maxDepth(root.left); // 求左子树的高度
        int rightHeight = maxDepth(root.right);  // 求右子树的高度
        //单层逻辑
        //左子树的深度和右子树的深度最大的值+1就是二叉树的深度
        return Math.max(leftHeight, rightHeight) + 1;
    }

有了上面的基础，我们回过头来看我们的平衡二叉树问题

 
分析：

二叉树的每个节点的左右子树的高度差的绝对值不超过 1，则二叉树是平衡二叉树。高度差的绝对值不超过1好办（我们上面那个题不就是求高度的吗？）但问题是怎样确保每个结点的左右子树高度差都不超过1呢？

我们不妨换一种思路，如果一个树是平衡二叉树，那么他的左子树和右子树也都必须是平衡二叉树才行。然后如果左子树想是一个平衡二叉树，那么该左子树他的左右子树是不是也必须是平衡二叉树呀！

这样从上往下递归下去，在递归的过程中我们一定是通过求当前结点的左右子树的高度来进行是否是平衡树的判断的，那么在递归过程中我们其实就完成了对每个结点左右子树高度的判断。

 

class Solution {
    // 求当前结点高度的函数
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
    // 一个树既然是平衡二叉树，那么他的所有子树都是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int left = maxDepth(root.left); // 递归求当前树左右子树的深度
        int right = maxDepth(root.right);
        if (left - right < -1 || left - right > 1) return false; // 如果差的绝对值大于一就返回false
        return isBalanced(root.left) && isBalanced(root.right); 
        // 递归判断每个节点是否是平衡二叉树,就该结点的左子树和右子树是否为平衡二叉树
        // 只有当左子树和右子树都是平衡二叉树时，该树才是平衡二叉树
    }
}

上面我们对每个结点其实都算了他的左右子树的高度，但很多情况下对每个结点都判断其实是没必要的，比如：

🌰 在这个二叉树中，很明显就不是一个平衡二叉树，比如结点9他的左子树的高度是2，右子树高度是0，这明显就不符合题目中平衡二叉树的定义啊！那么我们能不能在求高度的时候，如果遇到高度差的绝对值大于1了，就直接说明该二叉树不平衡呢？

📝所以我们可以对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1（仅仅只是把不平衡的子树标记起来，只要他与正常的高度返回值不同就行也可以是-100）。如果存在一棵子树不平衡，即返回了负数，则整个二叉树一定不平衡。

class Solution {
    // 求当前结点高度的函数
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        // 在求高度的过程中其实也进行了平衡二叉树的判断，
        // 如果返回值为负数说明已经有一个子树不是平衡二叉树了，即整个树已经不是平衡二叉树了
        int leftHeight = maxDepth(root.left);  // 所以接下来if里要加上leftHeight >= 0 && rightHeight >= 0这样的判断
        int rightHeight = maxDepth(root.right);  // 如果为-1，已经不是正常情况，所以不能进入到接下来的if语句里
        if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {
            return Math.max(leftHeight, rightHeight) + 1; // 正常情况下返回的一定大于0的
        }
        else {
            return -1;  // 说明该子树的不是平衡二叉树，即整个树就不是平衡二叉树
        }
    }
    // 一个树既然是平衡二叉树，那么他的所有子树都是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root)>=0; // 只有每个子树都是平衡二叉树，该数才是平衡二叉树
        // 如果每个子树都是平衡的，累加的返回值不可能为负数（因为每个相加的高度都是整数）
        // 如果一个子树返回了-1，及时其他的子树是正常的但因为我们再maxDepth的if语句里加了
        // leftHeight >= 0 && rightHeight >= 0，所以正常的高度也不会返回，也不会把负数冲掉
    }
}

 

再回顾一下就是：

• 一是我们需要先处理子树的深度再进行 比较
• 二是如果我们在处理子树时发现其已经不平衡了，则可以返回一个-1，使得所有其长辈节 点可以避免多余的判断  

定义：平衡二叉树是一棵二叉排序树，或者为空，或者满足以下条件：

           (1)左右子树高度差的绝对值不大于1；

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

平衡因子：对于二叉树中任一结点T，其平衡因子（Balance Factor，简称 BF）定义为BF(T) = hL-hR，其中hL和hR分别为T的左、右子树的高度。

平衡化旋转：如果在一棵 AVL 树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。我们称此调整平衡的过程为平衡旋转。

平衡化旋转的类别

• LL型：新插入结点在A的左孩子(L)的左子树(L)中；
• LR型：新插入结点在A的左孩子(L)的右子树(R)中；
• RL型：新插入结点在A的右孩子(R)的左子树(L)中；
• RR型：新插入结点在A的右孩子(R)的右子树(R)中。

构造平衡二叉树（AVL）

例题1：输入关键字序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，构成一棵平衡二叉排序树。

①插入16        ②插入3                     ③插入7   ----->          LR双旋                 

④插入11                             ⑤插入9       -------->   LL单旋

⑥插入26                            -------->      RR单旋

 ⑦插入18                                         -------->        RL双旋

 ⑧插入14                                                ⑨插入15                -------->        LR双旋

 例题2：给出如下平衡树，平衡二叉树中删除结点22，展示输出后的结果。

 答案：