数据结构-AVL树_平衡二叉树的高度为4 平衡因子为1

一：AVL树的概念

普通的二叉搜索树有一个致命的缺陷，就是如果将有序序列插入树中，树的高度会不断增大，我们知道二叉搜索树树的高度将直接决定搜索效率。

极端情况下将退化为单支树

因此如果能保证每个结点的左右子树的高度之差的绝对值不超过1，就能降低树的高度，从而提高搜索效率，我们把这种结构称之为高度平衡搜索树，简称为AVL树

下面的这棵树就是一棵AVL树，每个结点的平衡因子（平衡因子就是该结点左右子树高度值差的绝对值）

二：AVL树实现

（1）AVL树结点的定义

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;//可以有
	pair<K, V> _kv;

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)//刚创建的结点平衡因子为0
	{}
	int bf;//平衡因子

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（2）AVL树的插入

AVL树本质也是一个二叉搜索树，所以在插入上，其逻辑和二叉搜索树的并无很大区别

pair<Node*, bool> insert(const pair<K, V>& kv)
{

	//1：AVL树插入

	if (_root == nullptr)
	{
		_root = new Node(kv);
		return pair(_root, true);
	}
	
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (kv.first > cur->_kv.first)//插入的结点大于该结点，向右寻找
		{
			cur = cur->_right;
			if (cur == nullptr)//如果某次寻找中cur为空，表示找到插入位置
			{
				parent->_right = new Node(kv);//cur的父节点申请结点
				cur = parent->_right;
				cur->_parent = parent;//然后把该结点的父节点指针指向父节点
			}
			parent = cur;
		}
		else if (kv.first < cur->_kv.first)
		{
			cur = cur->_left;
			if (cur == nullptr)
			{
				parent->_left = new Node(kv);
				cur = parent->_left;
				cur->_parent = parent;
			}
			parent = cur;
		}
		else//没有找到，返回false及相同的值的位置
		{
			return pair<cur, false>;
		}
	}

	//2:AVL树平衡因子调整
	//见下面

	return pair<cur, true>;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

A：平衡因子更新

由于是AVL树，所以在插入时要时刻保证树的平衡，对于每个新插入的结点，由于左右子树为空，所以对于这个单个结点的树来说它肯定是平衡的，其平衡因子是0，但是如果它作为了其他结点的子树，就有可能影响其他结点的平衡因子，这种影响甚至有可能一直传达至祖先结点

新增结点会影响它的祖先的平衡因子

• 1：如果新增结点cur作为了parent结点的左子树，那么parent的平衡因子-1
  

• 上图中在结点8的左子树处插入了一个结点，导致结点8的平衡因子-1变为了0，此时本应该继续向上调整（因为8的改变有可能会影响到它的祖先），但是它变化为了0，所以这种变化恰好“抵消了”，因此可以停止更新而不用继续判断祖先是否受影响

• 2：如果新增结点cur作为了parent结点的右子树，那么parent的平衡因子+1
  

• 上图在9这个结点的右子树处插入了一个结点，因此9这个节点的平衡因子+1，变为1，此时结点9的平衡因子没有变成0，代表它的改变对上层可能会产生影响，因此要继续向上判断，对于结点8，其原来的平衡因子是1，所以此时对于它来说就应该调整为2，而当平衡因子大于等于2时，代表此树不平衡，所以要立即进行旋转操作，以保证树的平衡

除旋转代码外，平衡因子的调整代码如下，其中平衡因子为0和平衡因子为1或-1的情况就分别对应上面图中的例子。

	//1：AVL插入
	//见上面

	Node* ret = cur;//保存cur，因为下面的调整过程，会改变cur

	//2:AVL树调整平衡因子
	while (parent)//最厉害，调整到根节点。和堆的向上调整算法有点类似
	{
		//首先需要判断cur这个结点的插入对parent的影响
		if (cur == parent->_right)
			parent->_bf++;//如果插入到了右面，平衡因子+1
		else
			parent->_bf--;//如果插入到了左面，平衡因子-1

		if (parent->_bf == 0)//如果插入之后平衡因子为0，表示原来可能平衡因子1或-1，但是插入后抵消了变化
			break;//如果这样就不需要调整了

		else if (abs(parent->_bf) == 1)//如果插入后平衡因子为1或-1，表示原来是0，但是插入后变化了
		{
			cur = parent;
			parent = parent->_parent;//如果这样，这个结点有可能影响其父节点，所以要迭代判断父节点的情况
		}
		else if (abs(parent->_bf) == 2)//如果为2，表示树已经不平衡了，需要进行旋转
		{
			//旋转代码
		}
		else
			assert("平衡因子非法");

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

B：AVL树的旋转

AVL树的旋转共分为两类四种。另外旋转方式的命名可能从感觉上来讲有点别扭，其实旋转方式的命名时对不平衡状态的描述而不是对调整过程的描述

第一类：单旋

1：右单旋转调整（LL）：新节点插入到了较高左子树的左侧

下图中为抽象树，三角形表示的树为高度平衡的二叉树搜索树。在下面这个情况中，结点A的平衡因子绝对值为1，左子树较高

现在进行插入，来了一个新的结点恰好插入到了B结点的左树，导致A结点的平衡因子变为2，树不平衡，需要进行调整

调整时：将结点A下移一个高度，B上移一个高度。也就是将B从A的左子树处取下，然后将B的右子树挂在a的左子树处（为什么这样做？因为这样做是符合二叉搜索树的特性的），最后将A挂在B的右子树处

整个过程似乎很简单，但是其代码却有很多需要注意的地方，一旦不注意极易写出bug，我们这里使用的是三叉链，首先代码的大题逻辑如下

• 即把30（30作为的60的左结点）的右节点挂在60的左节点处，然后把60结点挂在30结点右节点处

因此首先定义两个节点subL和subLR，含义如下

Node* subL = parent->_left;//parent的左孩子
Node* subLR = subL->_right;//parent的左孩子的右孩子
1
2

接着60的left指向subLR，注意判空，因为subLR可能为空

parent->_left = subLR;//parent的左孩子此时要指向subLR
if (subLR)
	subLR->_parent = parent;//更新_parent，需要注意判断，因为subLR有可能是空的
1
2
3

接着对于parent来说，它也有自己的父节点，调整之后，parent的父节点的孩子将不再是parent，而是subL了，因此首先用一个结点保存parent的父节点

Node* parent_parent = parent->_parent;//用来保存parent的parent结点
1

此时30将作为新的parent，那么它的right就会指向60,也就是parent

subL->_right = parent;//subL的right指向parent
parent->_parent = subL;//更新_parent
1
2

注意判断一个特殊情况，因为60也就是parent有可能就是根节点，如果是这样的话直接改变将导致树丢失

if (parent == _root)//一个非常特殊的情况，假如parent就是根节点
	{
		//subL成为了新的根节点
		_root = subL;
		_root->_parent = nullptr;
	}
	else//正常情况
	{
	}
1
2
3
4
5
6
7
8
9

如果是正常情况，那么就修改parent的父节与新的parent(也就是subL)的关系即可

	if (parent == _root)//一个非常特殊的情况，假如parent就是根节点
	{
		//subL成为了新的根节点
		_root = subL;
		_root->_parent = nullptr;
	}
	else//正常情况
	{
		//如果parent是parent的父节点的左孩子
		if (parent_parent->_left = parent)
			parent_parent->_left = subL;//那么parent的left就要指向新的parent（subL）
		else
			parent_parent->_right = subL;

		subL->_parent = parent_parent;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

因此完整代码如下

void LL(Node* parent)//右单旋转调整
{
	Node* subL = parent->_left;//parent的左孩子
	Node* subLR = subL->_right;//parent的左孩子的右孩子
	
	parent->_left = subLR;//parent的左孩子此时要指向subLR
	if (subLR)
		subLR->_parent = parent;//更新_parent，需要注意判断，因为subLR有可能是空的

	Node* parent_parent = parent->_parent;//用来保存parent的parent结点
	subL->_right = parent;//subL的right指向parent
	parent->_parent = subL;//更新_parent

	if (parent == _root)//一个非常特殊的情况，假如parent就是根节点
	{
		//subL成为了新的根节点
		_root = subL;
		_root->_parent = nullptr;
	}
	else//正常情况
	{
		//如果parent是parent的父节点的左孩子
		if (parent_parent->_left = parent)
			parent_parent->_left = subL;
		else
			parent_parent->_right = subL;

		subL->_parent = parent_parent;
	}
	subL->_bf = parent->_bf = 0;//处理平衡因子
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2：左单旋转调整（RR）：新节点插入到了较高右子树的右侧

RR调整和LL调整情况恰好相反，调整时节点B上移，节点A下移，让节点A做节点B的左子树，让节点B的左子树做节点A的右子树

左单旋转调整和右单旋转调整代码基本一致，只是逻辑相反

void RR(Node* parent)//左单旋转调整
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;

	Node* parent_parent = parent->_parent;
	subR->_left = parent;
	parent->_parent = subR;

	if (parent == _root)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent_parent->_left = parent)
			parent_parent->_left = subR;
		else
			parent_parent->_right = subR;

		subR->_parent = parent_parent;
	}
	subR->_bf = parent->_bf = 0;//处理平衡因子
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

第二类：双旋

1：先左后右双旋转调整（LR）：新节点插入到了较高左子树的右侧

首先是旋转的基本过程

在LL调整中，新的结点插入到了较高左子树的左侧，调整后可以使树平衡

但是如果此时将新节点插入到较高左子树的右侧

如果继续使用LL调整，会发现怎么也调整不过去，依然不平衡

在这种情况下就要使用到双旋转调整了

我们先把较高左子树的右子树拆分一下，拆分为两棵树

大家会发现此时如果要在B的右侧插入一个节点就有两个选择——要么插入到C的左侧要么插入到C的右侧
这里我以插入到C的右侧为例

接着进行双旋转调整：先对B树进行左单旋转

形成了这样一颗树

然后对这颗树进行右单旋转调整，树就平衡了

• 本例是插入到了C的右侧，如果插入到了C的左侧，调整也是一样的
  

接着是代码部分

根据之前的描述，代码部分的逻辑也应该是先左旋后右旋即可，也就是直接调用前面的接口。

但是这里面最难处理的是平衡因子的问题，因为在上面的例子中虽然插入到C左侧和右侧采用的都是LR调整，但是调整完成之后，大家也发现了，新插入的结点会对平衡因子产生不同的影响

如下是不同插入情况下，平衡因子值的不同情况。其中C由于一定会到“根节点”位置，所以它的平衡因子始终为0

所以这份代码中我们首先依然要定义subL和subLR，还要实现保存subLR的平衡因子，然后让其LR调整

Node* subL = parent->_left;
Node* subLR = parent->_left->_parent;
int bf = subLR->_bf;

RotateL(parent->_left);
RotateR(parent);
1
2
3
4
5
6

左单和右单旋转调整接口中我们最终都干了这样的一个操作

subL->_bf = parent->_bf = 0;//处理平衡因子
subR->_bf = parent->_bf = 0;//处理平衡因子
1
2

所以在LR调整结束之后，根据之前保存的平衡因子，修改为上图中所展示的情况即可

• 如果是插入到了C的右面
  
• 如果是插入到了C的左面
  
• 如果subLR的平衡因子为0，说明subLR本身就是新增的结点，直接归0即可（其实这个操作不用也行，因为在两个接口中也会处理）

代码如下

void LR(Node* parent)//先左后右双旋转调整
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RR(parent->_left);
	LL(parent);//先左后右
	if (bf == 1)//subLR插入到了右面
	{
		subLR->_bf = 0;
		parent->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == -1)//subLR插入到了左面
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else//subLR本身就是新增结点
	{
		subLR->_bf = subL->_bf = parent->_bf = 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2：先右后左双旋转调整（RL）：新节点插入到了较高左子树的左侧

在左单（RR）旋转调整中，面对的情况是新节点插入到了较高右子树的右侧，而如果新节点插入到了较高右子树的左侧，那么就要使用先右后左双旋转调整

所以在这种情况下，先对右子树进行右单旋转调整，然后再进行左单旋转调整

代码逻辑也会前面的完全相反，这里就不过多阐述了

void RL(Node* parent)//先右后左双旋转调整
{
	Node* subR = parent->_left;
	Node* subRL = subL->_right;
	int bf = subRL->_bf;

	LL(parent->_right);
	RR(parent);//先右后左
	if (bf == 1)//subRL插入到了右面
	{
		subRL->_bf = 0;
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)//subRL插入到了左面
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else//subLR本身就是新增结点
	{
		subRL->_bf = subR->_bf = parent->_bf = 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

至此，写完这四种调整之后，我们就可以通过平衡因子，在插入代码中进行判断，去选择相应的旋转方式

代码如下

if (parent->_bf == -2)
{
	if (cur->_bf == -1)
	{
		RotateR(parent);
	}
	else // cur->_bf == 1
	{
		RotateLR(parent);
	}
}
else //parent->_bf == 2
{
	if (cur->_bf == 1)
	{
		RotateL(parent);
	}
	else // cur->_bf == -1
	{
		RotateLR(parent);
	}
}

	break;//注意跳出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 注意不要忘记再调整完成之后要跳出，因为调整最终的结果就是平衡

C：判断是否是平衡二叉树

代码如下

int Height(Node* root)//求树的高度
{
	if (root = nullptr)
		return 0;
	int left = Height(root->_left);
	int right = Height(root->_right);

	return left > right ? left + 1 : right + 1;
}

bool _Isbalance(Node* root)
{
	if (root == nullptr)
		return true;
	int left_high = Height(root->_left);
	int right_high = Height(root->_right);
	if (right_high - left_high != root->_bf)
	{
		cout << "平衡因子错误：" << root->_kv.first << endl;
	}
	
	return abs(left_high - right_high) < 2 && _Isbalance(root->_left) && _Isbalance(root->right);
}
bool _Isbalance()//判断是否是平衡树，顺便检查平衡因子更新的是否正确
{
	return _Isbalance(_root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

（3）AVL树删除

了解即可。AVL树的删除遵从二叉搜索树删除的细则，但是需要注意的是删除时也要更新平衡因子，以及不平衡时进行旋转。
具体相关细则可以