你还不会AVL树吗？

AVL树概念

🚀AVL树是一颗平衡的二叉搜索树，所谓平衡是指左右子树的高度差的绝对值不超过1。所以一颗AVL树（如果不是空树）有以下性质：
左右子树都是AVL树
左右子树的高度差的绝对值不超过1
🚀为了维护左右子树高度差的绝对值不超过1，引入了平衡因子-bf（balance factor）的概念，bf的值为右子树的高度减去左子树的高度。

AVL树的插入

结点定义

namespace gy_AVL
{
	template<class K, class V>
	struct TreeNode
	{
		TreeNode<K,V>(const pair<K,V>& kv)
			:_kv(kv)
		{}
		pair<K, V> _kv;
		int _bf = 0;
		TreeNode<K, V>* _left = nullptr;
		TreeNode<K, V>* _right = nullptr;
		TreeNode<K, V>* _parent = nullptr;
	};
	template<class K,class V>
	class AVLTree
	{
	public:
		typedef TreeNode<K, V> node;
	private:
		node* _root = nullptr;
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

插入流程

🚀AVL树的插入总体分为三步：
1，找到要插入的位置
2，将新结点插入，更新平衡因子
3，更新平衡因子时，查看是否需要旋转操作

更新平衡因子

如果新插入的结点是其parent结点的右子树，那么parent结点的bf++，相反如果是左子树那么parent结点的bf–。如果平衡因子调整完为0，不用继续向上调整。如果平衡因子调整完为-1或1，那么需要继续向上调整。如果平衡因子调整完为-2或2，那么需要进行旋转操作，旋转完后需要继续向上调整。

解释是否需要继续向上调整的原因

1.调整完bf = 0
调整完后bf = 0，说明调整前的bf为1或-1，调整完为0的原因是在左右子树较短的那颗树上插入了新的结点，所以这颗树的高度并没有发生变化，所以不需要继续向上调整平衡因子。
2.调整完bf = 1 或 = -1
调整完平衡因子为-1或1，说明调整前平衡因子为0，插入新的节点后增加了做左右子树的某一的高度，使得此树的高度加1，所以需要继续向上调整。
3.调整完bf = 2 或 = -2
调整完平衡因子为2或-2，说明调整前平衡因子为-1或1，而此插入的新结点位于高度较高的那颗子树上，使得此树不再平衡需要进行旋转处理，旋转的本质就是降低高度重新达到平衡，旋转完的高度与插入新节点之前的高度是一样的，所以旋转处理后不需要继续向上调整平衡因子。

🚀代码实现：

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new node(kv);
		return true;
	}
	//找到要插入的位置
	node* cur = _root;
	node* prev = nullptr;
	while (cur)
	{
		if (cur->_kv.first > kv.first)
		{
			prev = cur;
			cur = cur->_left;
		}
		else if (cur->_kv.first < kv.first)
		{
			prev = cur;
			cur = cur->_right;
		}
		else
		{
			return false; //存在相同值，插入失败
		}
	}
	node* newnode = new node(kv);
	if (kv.first < prev->_kv.first)
	{
		prev->_left = newnode;
	}
	else
	{
		prev->_right = newnode;
	}
	node* parent = prev;
	cur = newnode;
	while (parent)
	{
		//调整平衡因子
		if (parent->_left == cur)
		{
			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)
		{
			if (parent->_bf == 2 && parent->_right->_bf == 1) //左单旋
			{
				RotateL(parent);
			}
			else if (parent->_bf == -2 && parent->_left->_bf == -1) //右单旋
			{
				RotateR(parent);
			}
			else if (parent->_bf == -2 && parent->_left->_bf == 1) //左右双旋
			{
				RotateLR(parent);
			}
			else if (parent->_bf == 2 && parent->_right->_bf == -1) //右左双旋
			{
				RotateRL(parent);
			}
			else
			{
				assert(false);
			}
		}
		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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

左单旋

🚀对于上图中这种情况，只要在90的右子树插入新的结点那么就会使90结点的bf为1，60的bf为2，从而导致60这颗树就要进行旋转来降低高度维持平衡状态。
对于上图的这种画法解释：
上面这种图为抽象图，并不是指的某一种情况而是代表一类情况，下面将抽象图具体化一下：
1，h = 0

2，h = 1

3，h = 3

🚀左旋过程
1，首先统一结点名称：60为parent，90为subR，90的左子树为subRL。
2，subRL连接到parent的右子树位置。
3，parent连接到subR的左子树位置。

注意： 我们定义结点的时候都是定义的三指针结构，不要忘记对_parent指针做修改，同时左旋完成后subR的平衡因子与parent的平衡因子都是0。

🚀左单旋代码：

void RotateL(node* parent)
{
	node* subR = parent->_right;
	node* subRL = subR->_left;
	parent->_right = subRL;
	if (subRL)
	{
		subRL->_parent = parent;
	}
	subR->_left = parent;
	node* ppnode = parent->_parent;
	parent->_parent = subR;
	if (ppnode == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else if (ppnode->_left == parent)
	{
		ppnode->_left = subR;
		subR->_parent = ppnode;
	}
	else
	{
		ppnode->_right = subR;
		subR->_parent = ppnode;
	}

	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
30

右单旋

🚀对于上面这种情况，如果在50的左子树插入新的结点，会使50的bf为-1，60的bf为-2，从而导致需要进行旋转来降低高度维持平衡。

🚀右旋过程
1，首先统一结点名称：60为parent结点，50为subL结点，50的右子树为subLR结点。
2，subL结点的右子树连接到60的左子树位置。
3，parent结点连接到subL的右子树位置。

🚀右单旋代码：

void RotateR(node* parent)
{
	node* subL = parent->_left;
	node* subLR = subL->_right;
	parent->_left = subLR;
	if (subLR)
	{
		subLR->_parent = parent;
	}
	subL->_right = parent;
	node* ppnode = parent->_parent;
	parent->_parent = subL;

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

	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

左右双旋

🚀像上面这种情况，如果在55结点的左或者右子树的位置插入新的结点，都会使50的bf为1，60的bf为-2，从而导致左右双旋来降低高度维持平衡。

1，h = 0
当h = 0的时候55结点就是新插入的结点。

2，h = 1

3，h = 2

🚀左右双旋过程
1，首先统一名称：60为parent，50为subL结点，55为subLR结点。
2，对subL为根的子树进行左单旋。
3，对parent为根结点的树进行右单旋。

🚀注意 左右双旋完成后要对平衡因子做修正，subLR结点的平衡因子为0，单parent结点的bf值与subL结点的bf值，要根据最开始subLR结点的平衡因子确定（即新结点时插入在subLR的左子树还是右子树）

情况1：

情况2：

特殊情况 当subLR结点就是新插入的结点的时候，最终subL ，parent，subLR结点的平衡因子都是0。

🚀左右双旋代码：

void RotateLR(node* parent)
{
	node* subL = parent->_left;
	node* subLR = subL->_right;
	int bf = subLR->_bf;
	RotateL(subL);
	RotateR(parent);
	if (bf == 0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == 1)
	{
		subLR->_bf = 0;
		parent->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == -1)
	{
		subLR->_bf = 0;
		parent->_bf = 1;
		subL->_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
28
29
30

右左双旋

🚀像上图这样，如果在80结点的左子树或者右子树插入新的结点，会使60结点的bf值为2，90结点的bf为1，那么就要通过右左双旋的方式来降低树的高度从而维持平衡。

🚀右左双旋的过程：
1，首先统一名称：60结点为parent结点，90结点为subR结点，80结点为subRL结点。
2，对subR结点为根节点的子树做右单旋。
3，对parent结点为根结点的树做左单旋。

🚀平衡因子的修正
与左右双旋相同，右左双旋完成后仍然要对平衡因子做修正，针对的结点为subR，subRL，parent，主要分为以下情况。

情况1：

情况2：

🚀特殊情况，subRL结点为新插入结点

🚀右左双旋代码：

void RotateRL(node* parent)
{
	node* subR = parent->_right;
	node* subRL = subR->_left;
	int bf = subRL->_bf;
	RotateR(subR);
	RotateL(parent);
	if (bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = -1;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 0;
		subR->_bf = 1;
		subRL->_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
28
29
30

验证AVL树

🚀验证AVL树需要验证两点：
1，是搜索树，即中序遍历是有序的。
2，是平衡树，即左右子树高度差绝对值不超过1，与结点的bf匹配。

bool isBalanceTree()
{
	return _isbalanceTree(_root);
}

int _Height(node* root)
{
	if (root == nullptr)
		return 0;
	int hL = _Height(root->_left);
	int hR = _Height(root->_right);
	return max(hL, hR) + 1;
}
bool _isbalanceTree(node* root)
{
	if (root == nullptr)
		return true;
	int leftH = _Height(root->_left);
	int rightH = _Height(root->_right);
	int diff = rightH - leftH;
	if (diff != root->_bf)
	{
		cout << root->_kv.first<<  " : 平衡因子异常" << endl;
	}
	if ((diff > 1 || diff < -1))
		return false;
	return _isbalanceTree(root->_left) && _isbalanceTree(root->_right);
}
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

🚀通过上面的代码就可以验证一颗AVL树是否正确。