【C++进阶】深度解析AVL树及其简单模拟实现

一，什么是AVL树

之前我们学习了二叉搜索树，但是有时候因为节点插入的问题，可能会退化为单支树，这样会导致查找效率变得底下如顺序表。
因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度

这种树就是AVL树.

二，AVL树的特性

AVL树满足两个条件：

1. 它的左右子树都是AVL树
2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

平衡因子=右子树高度-左子树高度

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$O(lo{g}_{2}n)$，搜索时间复杂度O($lo{g}_{2}n$)

三，模拟实现

1. 基本框架

AVL树是一种平衡二叉树，其内部存储的是pair键值对，我们模拟实现的时候直接用pair来存储即可。
我们先来写AVL的节点定义：
每个节点都要有一个平衡因子用来保证其AVL树特性

template<class K,class V>
struct AVLTreeNode {
	typedef AVLTreeNode<K, V> Node;

	AVLTreeNode(const pair<K,V> &kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
	
	Node* _left;
	Node* _right;
	Node* _parent;//记录当前节点的父亲
	int _bf;//记录节点的平衡因子
	pair<K, V> _kv;//保存记录的key,val

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

然后我们来写AVL的框架：

template<class K,class V>
class AVLTree {
	typedef AVLTreeNode<K, V> Node;
public:
	//...
private:
	Node* _root = nullptr;

};
1
2
3
4
5
6
7
8
9

2. 插入（不带旋转）

下面我们来实现AVL树的插入：
插入分为两步：

1. 按照二叉搜索树那样插入节点
2. 调整平衡因子

---

插入节点的部分和二叉搜索树的代码一样，主要是修改平衡因子的部分

当插入新节点后，这个新节点的双亲节点的平衡因子会发生变化:
1.新插入的节点cur在其双亲节点parent的左孩子时，parent的平衡因子-1
2. 新插入的节点在parent的右孩子时，parent的平衡因子+1

代码如下：

bool insert(const pair<K,V> &kv) {
		if (_root == nullptr) {
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if (kv.first > cur->_kv.first) {
				parent = cur;
				cur = cur->_right;
				
			}
			else if (kv.first < cur->_kv.first) {
				parent = cur;
				cur = cur->_left;
				
			}
			else {
				return false;
			}
		}
		//找到了插入位置
		cur = new Node(kv);
		if (kv.first > parent->_kv.first) {
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		cur->_parent = parent;

		//修改平衡因子
		while (parent) {
			if (cur == parent->_left) {//如果加在左边，则父节点的平衡因子--
				parent->_bf--;
			}
			else {
				parent->_bf++;//右边则++
			}
			//调整平衡因子
			//...

		}
		return 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

修改后这里有三种情况：

1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功
2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新
3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理

我们先来说前两种情况，第三种我们在旋转中讲解

---

第一种情况：
修改后parent的平衡因子为0，这里就不用再进行调整了

第二种情况：
修改后平衡因子为1，则以parent为根的这颗树的高度发生了变化，则要继续向上调整平衡因子

代码：

bool insert(const pair<K,V> &kv) {
		if (_root == nullptr) {
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if (kv.first > cur->_kv.first) {
				parent = cur;
				cur = cur->_right;
				
			}
			else if (kv.first < cur->_kv.first) {
				parent = cur;
				cur = cur->_left;
				
			}
			else {
				return false;
			}
		}
		//找到了插入位置
		cur = new Node(kv);
		if (kv.first > parent->_kv.first) {
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		cur->_parent = parent;

		//修改平衡因子
		while (parent) {
			if (cur == parent->_left) {//如果加在左边，则父节点的平衡因子--
				parent->_bf--;
			}
			else {
				parent->_bf++;//右边则++
			}
			//增加节点后有三种情况，
			if (parent->_bf == 0) {
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1) {
				cur = cur->_parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2) {
				//旋转
				
			}
			else {
				assert(false);//说明插入之前就有问题
			}
		}
		return 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
49
50
51
52
53
54
55
56
57
58
59

2. AVL树的旋转

上面的两种情况，更新parent的平衡因子后AVL树的特性还保持着，但是第三种情况更新后，双亲的平衡因子为2/-2，破坏了平衡二叉搜索树的特性，所以就要进行以parent为根的树的旋转

AVL树的旋转也分为四种情况

1. 新节点插入较高左子树的左侧：右单旋
2. 新节点插入较高右子树的右侧：左单旋
3. 新节点插入较高左子树的右侧—左右双旋：先左单旋再右单旋
4. 新节点插入较高右子树的左侧—右左双旋：先右单旋再左单旋

下面我们来依次解释：

---

右单旋：

右单旋是新插入的节点在左子树中，使其整棵树右高左低，所以要旋转右子树来降低高度差使这棵树变得平衡

具体过程看下图：

这里我们来看一下具体当各子树高度的情况：

下面我们来编写一下右单璇的代码：
首先我们定义两个节点用来标记当前需要旋转的节点。

对于右单旋，我们找当前parent的左孩子 subL 和该左孩子的右孩子 subLR

然后我们在旋转时还要注意一下：
（1） 30这个节点的右子树可能存在也可能不存在
不存在时我们就不能直接将subL的parent指针直接指向60

void RotateR(Node* parent) {//右单旋
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		
		parent->_left = subLR;
		if (subLR) {//当subLR存在时，subLR的parent才指向parent
			subLR->_parent = parent;
		}
		//...
}

1
2
3
4
5
6
7
8
9
10
11

（2） 60这个节点可能是根也可能不为根。
不为根时，我们还需要一个 ppnode 节点来标记parent的双亲节点，用来将新的’根’节点去链接到原来的树上。

void RotateR(Node* parent) {//右单旋
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		
		parent->_left = subLR;
		if (subLR) {//当subLR存在时，subLR的parent才指向parent
			subLR->_parent = parent;
		}
		if (parent == _root) {//如果p是根,则subL更新为根
			_root = subL;
			subL->_parent = nullptr;
		}
		else {//将旋转后的子树的根节点链接到原来的树上
			if (ppnode->_left == parent) {
				ppnode->_left = subL;
			}
			else {
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
		//...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

最后一步就是修改平衡因子，旋转后的节点不用再调整，因为旋转后子树的两端高度都相等，达到平衡。

void RotateR(Node* parent) {//右单旋
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;
	if (subLR) {//当subLR存在时，subLR的parent才指向parent
		subLR->_parent = parent;
	}

	subL->_right = parent;
	Node* ppnode = parent->_parent;//保存p的parent指向
	parent->_parent = subL;

	if (parent == _root) {//如果p是根,则subL更新为根
		_root = subL;
		subL->_parent = nullptr;
	}
	else {//将旋转后的子树的根节点链接到原来的树上
		if (ppnode->_left == parent) {
			ppnode->_left = subL;
		}
		else {
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
	//更新节点的平衡因子
	parent->_bf = 0;
	subL->_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

---

现在来看左单旋：

左单旋和右单旋相反，左边高右边低，所以进行左单旋来降低高度差

这里的情况都和右单旋转相反，我们直接上代码：

void RotateL(Node* parent) {//左单旋
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if (subRL) {//当subRL存在时，subRL的parent才指向parent
		subRL->_parent = parent;
	}

	subR->_left = parent;
	Node* ppnode = parent->_parent;//保存p的parent指向
	parent->_parent = subR;

	if (parent == _root) {//如果p是根,则subR更新为根
		_root = subR;
		subR->_parent = nullptr;
	}
	else {//将旋转后的子树的根节点链接到原来的树上
		if (ppnode->_left == parent) {
			ppnode->_left = subR;
		}
		else {
			ppnode->_right = subR;
		}
		subR->_parent = ppnode;
	}
	//更新节点的平衡因子
	parent->_bf = 0;
	subR->_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

---

我们现在来看左右双旋，先左单旋再右单旋

这里的左右双旋其实就是相当右单旋的那种场景下，将b子树拆分成两颗子树，再将新增节点加在拆分后的子树上

我们以加在左子树为例讲解：
对新增节点后的树进行旋转，先以subL为根进行左旋，

再对parent为根进行右旋

加在右子树的过程和这个相反，希望大家可以自己去推导…

知道了大概的过程，我们现在来写代码：
和单旋一样，我们定义变量来协助我们旋转

void RotateRL(Node* parent) {//双旋（先左单旋，再右单旋）
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		//..
}
1
2
3
4
5
6

这里需要注意：新增节点所加的位置有三种情况
（1） 加在拆分后的左子树上
（2） 加在拆分后的右子树上
（3） 上图的60这个位置本身是空的

那么我们如何区分这三种情况呢，
我们可以用subLR的平衡因子来区分，subLR的因子为-1时，说明左高，则加在了左子树上，为1时，说明右高，则加在了右子树，为0时说明这个位置原来是空的。

void RotateLR(Node* parent) {
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	int bf = subLR->_bf;
	RotateL(subL);
	RotateR(parent);

	subLR->_bf = 0;
	if (bf == -1) {
		parent->_bf = 1;
		subL->_bf = 0;
	}else if (bf == 1) {
		parent->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == 0) {
		parent->_bf = 0;
		subL->_bf = 0;
	}
	else {
		assert(false);
	}
	subLR->_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

---

右左双旋
右左双旋和左右双旋相反，各位老铁可以参考左右双旋来自己去画出图来理解

代码：

void RotateRL(Node* parent) {//双旋（先右单旋，再左单旋）
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	int bf = subRL->_bf;//以subRL的因子为标准判断所加的子树的位置
	RotateR(subR);
	RotateL(parent);

	//修改平衡因子
	//增加节点后有三种情况
	subRL->_bf = 0;
	if (bf == -1) {//加在左子树上
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 1) {
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == 0) {
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else {
		assert(false);
	}
}
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的插入讲完了，我们来看看如何证明咋们模拟实现的就是AVL树
一棵树如果是AVL树，那么首先它是一个二叉搜索树，其次他的每个子树的高度差不能超过1

这里我们做了一点小优化，我们在判断时先传入高度，判断高度差时类似于后序遍历的方式，从下往上去计算高度差

代码如下：

bool IsBalance() {
	int height = 0;
	return _IsBalance(_root, height);
}


bool _IsBalance(Node* root,int &height) {
	if (root == nullptr) {
		height = 0;
		return true;
	}
	int leftHeight = 0, rightHeight = 0;
	if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight)) {
		return false;
	}
	if (abs(rightHeight - leftHeight) >= 2) {
		cout <<root->_kv.first<< "不平衡" << endl;
		return false;
	}
	if (rightHeight - leftHeight != root->_bf) {
		cout << root->_kv.first << "平衡因子异常" << endl;
		return false;
	}
	height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	return 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

四，总结

我们今天终于讲完了AVL树，我们的C++部分也开始上了难度，希望大家可以跟上我们的讲解，下一节我们要来开始手撕红黑树！！！
在此之前我们要熟悉前面的二叉搜索树和AVL树的内容，希望大家都能学好C++。