编者序

bug：==
subtree：子树的意思
balance factor ：平衡系数/平衡因子

AVL树的特征

• 二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
  
• 两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法，对二叉搜索树高度的严格管控：
• 当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
• 这样可以保证查询时高效的时间复杂度，即logN。
  
• 如果要对AVL树做一些结构修改的操作，性能非常低下：
  • 插入时要维护其绝对平衡，旋转的次数比较多
  • 在删除时，有可能一直要让旋转持续到根的位置。
• 因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

平衡因子

• 通过对二叉搜索树的每个节点添加一个变量标识位：balance factor（_bf–平衡因子）来控制树的平衡；一个指向双亲的指针：进行平衡因子的更新。
• 新插入一个节点就要更新平衡因子。
• balance factor的几种状态：1，-1，0，2，-2，初始值为0；当在根节点右边插入时，balance factor++，左边插入时balance factor–；
• 平衡因子的更新：
  • 如果双亲节点的balance factor变成了0，说明原来的balance factor是 1 或者 -1，新插入节点把矮的一边补齐了；
  • 如果双亲节点的balance factor变成了-1，说明是在双亲的左边插入，整个树高度发生变化，需要继续往上更新balance factor；一直更新到根节点为止，右边插入同理。
  • 更新途中，如果双亲结点的balance factor变成了 0 ，则停止更新。
  • 如果双亲节点的balance factor变成了2或-2，则需要进行旋转调整。

更新平衡因子代码

基建

#include<iostream>
#include<assert.h>
template<class K,class V>
struct AVLNode
{
	AVLNode* _left;
	AVLNode* _right;
	AVLNode* _parent;   //用来更新双亲的balance factor
	std::pair<K, V> _kv;  

	int _bf;//balance factor = 右子树高度减去左子树

	AVLNode(const std::pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_bf(0)
	{

	}
};

template<class K,class V>
class AVLTree
{
	typedef AVLNode<K, V> Node;
public:
	AVLTree()
		:_root(nullptr)
	{
	}
	......
private:
	Node* _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
28
29
30
31
32
33
34
35
36

---

• 插入前半部分和二叉搜索树的插入一致。
  • 插入值比根节点大，往右走，反之往左走，走到空位置，记录空节点的双亲节点，以便链接到树上。
  • 修改新插入节点（AVLNode* _parent）的指向，还需确定双亲节点的哪一边连接到新节点。
• 随后根据双亲结点balance factor的变化确定是否要继续往上更新节点的balance factor。

bool Insert(const std::pair<K, V>& kv)
	{
		if (_root ==nullptr)
		{
				_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first<kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if(cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		//插入 cur走到空
		 cur = new Node(kv);
		 cur->_parent = parent;
		if (parent->_kv.first>cur->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		
		//更新平衡因子：父亲节点平衡因子更新为 1 或 -1 ，继续往上更新，更新到根为止；
		//或者某一处更新为0，则不需要继续更新，因为是把双亲矮的一边儿补齐了 左边插入平衡因子--，右边++
		while (parent)
		{
			if (cur==parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			//检查父亲的平衡因子
			if (parent->_bf==-1|| parent->_bf == 1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			else if(parent->_bf == 0)
			{
				break;
			}
			else if(parent->_bf == -2 || parent->_bf == 2)//则需要进行旋转处理
			{

				if (parent->_bf == -2 && cur->_bf == -1)
				{
					//左左，向右旋转，把右边往下压
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					//右右，向左旋转，把左边往下压
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					//左右 ， 左孩子左旋，parent右旋
					RotateLR(parent);
				}
				else if(parent->_bf == 2 && cur->_bf == -1)
				{
					//右左，subR右旋，parent 左旋
					RotateRL(parent);
				}
				else
				{
					assert(false);//说明这颗树之前就是不平衡的  2  3  等..
				}
				break;//处理完毕
			}
			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
91
92
93
94
95
96
97

左左类型：右旋

• 此时：parent->_bf == -2 && cur->_bf == -1;右右类型也一致，都是一条直线。

• 以上图的新插入结点1为例，此时需要将 6 作为新的根节点；9 作为 6 的右孩子；7 作为 9 的左孩子；6 的左孩子保持不变。

• 然后更新 6 、9 、7、的（_parent）的指向；同时更新 6 、9 、的balance factor。

• 6 的右孩子一定比 6 大，也一定比 9 小，所以很合适…

• 图解如下：
  
  
  

• 9 可能是根，也可能是上面节点的某一边子树；需要注意处理一下。

• subL作为新的根…

	void RotateR(Node* parent)
	{
		//判断parent是否是根节点
		//是，则更新根节点
		//不是，则看是pparent节点的哪一边
		//以上两种情况都要更新subl的双亲结点
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		//更新换过去节点的双亲结点
		if (subLR)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		//交接父亲节点
		Node* pparent = parent->_parent;
		subL->_parent = pparent;
		parent->_parent = subL;
		//更新根节点
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (pparent->_left==parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
			subL->_parent = pparent;
		}
		//更新平衡因子
		parent->_bf = 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
31
32
33
34
35
36
37
38
39
40
41

右右类型：左旋

• 同左左，原来的6 可能是 根，也可能是 上面子树的某一边，旋转以后需要进行分别处理。
• subR作为新的根…，7 作为 6 的右孩子， 6 变成 9 的 左孩子。更新与其相关的状态变量。

void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		
		parent->_right = subR->_left;
		subR->_left = parent;
		if (subRL)//可能是空 
		{
			subRL->_parent = parent;
		}
		Node* pparent = parent->_parent;//祖父
		if (_root==parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (pparent->_right==parent)//祖父的交接
			{
				pparent->_right = subR;
			}
			else
			{
				pparent->_left = subR;
			}
			subR->_parent = pparent;
		}
		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
31

左右类型：先左旋，再右旋

• 可以看出是一条折线：拐弯的，此时：parent->_bf == -2 && cur->_bf == 1

• 还要注意：可能是在 7 的 左边插入 ，或 7 的右边插入；会影响到subL 和 parent 的 balance factor。

• 图示拆解如下：
  
  

• 此时如果插入的是 8 ，则在7 的右边，会去做 9 的左孩子。

void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		RotateL(parent->_left);
		RotateR(parent);
		 if(subLR->_bf==-1)
		{
          //画图即可  说明在左边插入，左旋之后subl的bf已经更新
			parent->_bf = 1;
		}
		else
		{
			 //说明在右边插入，右旋之后parent的bf已经更新
			subL->_bf = -1;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

右左类型：先右旋，再左旋

• 此时： parent->_bf == 2 && cur->_bf == -1
• 同左右，如果插入的是 10 ，则会在 8 的 右边，最终成为 11 的左孩子。
• 左或右的新插入节点，会影响到subR 和 parent 的 balance factor。分别处理

void RotateRL(Node* parent)
	{
		//先右旋，再左旋
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		RotateR(parent->_right);
		RotateL(parent);
		if (subRL->_bf == -1)
		{
			//画图即可  说明在左边插入，最后parent的bf已经更新0
			subR->_bf = 1;
		}
		else
		{
			//说明在右边插入，右旋之后subR的bf已经更新0
			parent->_bf = -1;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

验证是否是AVL树

• 求左右子树的高度，相减；结合根的balance factor判断；
• 在递归判断我的左子树的左子树 / 右子树的右子树 是否满足…

	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()
	{
		return _IsBalance(_root);
	}
	bool _IsBalance(Node* root)
	{
		if (root==nullptr)
		{
			return true;
		}
		int LeftHigh = Height(root->_left);
		int RightHigh = Height(root->_right);
		int diff = RightHigh - LeftHigh;
		
		//此根的右子树高度减去左子树高度不等于根的平衡因子，就不是AVL树
		if (diff != root->_bf || (diff > 1 || diff < -1)) 
		{
			//std::cout << "平衡因子异常:" << root->_kv.first << std::endl;
			return false;
		}
		return abs(RightHigh-LeftHigh)<2 && //且右高减去左高的绝对值小于2
					_IsBalance(root->_left) && 
			        _IsBalance(root->_right);//是平衡因子就要看我的左和右都满足才是AVL树
	}
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

G.

旋的我腮帮子疼…本文图片来源地是个讲解AVL树视频

• 测试用例

void test3()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int, int> aa;

	/*aa.Insert(make_pair(4, 4));
	aa.Insert(make_pair(2, 2));
	aa.Insert(make_pair(6, 6));
	aa.Insert(make_pair(1, 1));*/
	//aa.Insert(make_pair(3, 3));
	for (auto& i : a)
	{
		aa.Insert(make_pair(i, i));
	}
	cout << aa.IsBalance() << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17