【C++笔记】AVL树的模拟实现

一、AVL树的概念

二叉搜索树虽然在一般情况下可以提高查找的效率，但如果插入数据的顺序接近有序或有序，那二叉搜索树就会变成一个类似“单链表”的结构：

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

一棵AVL树要么是空树，要么就是具有以下性质的一棵二叉搜索树：

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

比如下面这棵树就是一棵AVL树：

二、AVL树的模拟实现

2.1、定义节点

定义AVL树的节点除了传统的左右指针和值之外还需要定义两个成员——parent指针和平衡因子，因为我们后面在调整平衡的时候必须要用到它们：

// 定义AVL树节点
template <class K, class V>
struct AVLTreeNode {
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _val;
	int _bf; // 平衡因子
	// 构造
	AVLTreeNode(const pair<K, V>& key)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_val(key)
		,_bf(0)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

然后同样的，我们只需要在AVLTree类里面封装一个根节点的指针即可：

// AVL树
template <class K, class V>
class AVLTree {
public:
	typedef AVLTreeNode<K, V> Node;
	// ……
private :
	Node* _root = nullptr;
};
1
2
3
4
5
6
7
8
9

2.2、插入

因为AVL树其实结构和普通二叉树没什么区别，只是规则不一样，所以我们这里就只需要实现与其他数不同的插入即可。

AVL树的插入也实现要找到插入位置，但是在插入成功之后还需要调整平衡因子，并判断是否需要进行调整，以确保满足AVL树的规则。

最容易的情况就是在插入新节点后，左右高度差并没有超出范围，这样就不需要调整了(调整到根节点为止，如果没有一个节点的平衡因子超出范围就不需要调整)，例如在下面这AVL树中我们要插入一个值为9的节点：

当我们找到插入位置后就需要一直向上调整平衡因子：

当我们调整完后发现并么有平衡因子出现异常，因此也就不需要调整了，所执行的操作和二叉搜索树的插入一样了。

这里先给出不需要调整的代码实现：

// 插入
bool insert(const pair<K, V>& key) {
	if (nullptr == _root) {
		_root = new Node(key);
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	
	// 先插入节点
	while (cur) {
		if (key.first > cur->_val.first) {
			parent = cur;
			cur = cur->_right;
		}
		else if (key.first < cur->_val.first) {
			parent = cur;
			cur = cur->_left;
		}
		else {
			return false;
		}
	}

	// 准备插入
	cur = new Node(key);
	if (key.first > parent->_val.first) {
		parent->_right = cur;
		cur->_parent = parent;
	}
	else {
		parent->_left = cur;
		cur->_parent = parent;

	}
	// 检查平衡因子，看看是否需要旋转调整
	while (parent) {
		//  先做第一步调整
		if (cur == parent->_left) {
			parent->_bf--;
		}
		else {
			parent->_bf++;
		}


		if (parent->_bf == 0) {
			return true;
		}
		else if (parent->_bf == 1 || parent->_bf == -1) { // 继续向上检查
			cur = parent;
			parent = parent->_parent;
		} 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

2.3、旋转

2.3.1、左单旋

而一旦我们的插入导致平衡因子超出了范围，这时候就需要调整了，比如我们想要在下面这棵AVL中在插入一个值为10的节点：

更新平衡因子的过程中，我们发现8这个节点的平衡因子超出了范围，这时候我们该怎样调整呢？

如果我们将8看做需要调整的这棵子树的根，那么对根为8的这棵子树进行 “左单旋” 就能解决问题。

像这样在右子树的右子树（右右）中插入新节点的情况，处理的方法称为左单旋，下面介绍具体步骤：

如上图所示，将节点8设置为parent，parent的parent设置成parent_parent，parent的右孩子设置成subRight，将subRight的左孩子设置成subRightL。
左单旋我们需要做的就是让subRight成为parent的右孩子，再让parent成为subRight的左孩子，然后让subRight成为这棵子树新的根，并让parent_parent连接上subRight。

相信大家看上面的图示都会感到眼花缭乱，所以我这里转化出了一个抽象图：

这里其实并不用关心子树的高度h具体是多高，因为h取任何值都是一样的。
从图中我们也可以观察的出，这里的本质其实是通过将subRight改成新的根节点，从而将整棵子树的高度降低了一个高度。
做完这些后不要忘了调整平衡因子，由图中我们可以很形象的看出直接把subRight和parent的平衡因子调整成0即可。
(图中省略了parent指针的处理，但是在实际实现中，parent指针是一定要处理的)

那这样做为什么正确呢？

通过之前对搜索二叉树规律的分析，我们可以得出另一个规律：对于一个根，它的左子树的所有节点一定是小于根节点的，右子树的所有节点一定是大于根的。
所以我们这里的subRightL也一定是大于parent的，所以它可以成为pareng的右子树，而subRight也一定是大于parent的，所以parent就可以成为subRight的根，所以经过上面的操作之后，这棵子树还是满足二叉搜索树的规律的。

那怎么判断什么情况下我们要进行左单旋呢？
我们可以通过平衡因子来判断，因为平衡因子的定义是右子树与左子树的高度差，所以如果一个根它的平衡因子是2并且它的右子树的平衡因子是1，则说明是在右子树的右子树中插入新节点导致的不平衡。

所以一棵子树要进行左单旋判断条件是：

root->_bf == 2 && root->_right->_bf == 1;

接下来就是左单旋的代码实现：

// 左单旋
void RotateL(Node* parent) {
	Node* subRight = parent->_right;
	Node* subRightL = subRight->_left;
	Node* parent_parent = parent->_parent;

	parent->_right = subRightL;
	if (subRightL) {
		subRightL->_parent = parent;
	}
	subRight->_left = parent;
	parent->_parent = subRight;

	if (parent == _root) { // 如果当前的parent是根
		_root = subRight;
		subRight->_parent = nullptr;
	}
	else {
		// 如果当前的parent还不是根
		if (parent == parent_parent->_left) {
			parent_parent->_left = subRight;
		}
		else {
			parent_parent->_right = subRight;
		}
		subRight->_parent = parent_parent;
	}


	// 调整平衡因子
	parent->_bf = 0;
	subRight->_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

2.3.2、右单旋

右单旋和做单旋在逻辑上是一样的，基本就是左单旋改一下方向就可以了。
当我们在左子树的左子树（左左）中插入节点导致不平衡的时候，就需要用到右单旋：

处理过程的抽象图也和左单旋的差不多：

然后这是右单旋的代码实现：

	// 右单旋
	void RotateR(Node* parent) {
		Node* subLeft = parent->_left;
		Node* subLeftR = subLeft->_right;
		Node* parent_parent = parent->_parent;

		parent->_left = subLeftR;
		if (subLeftR) {
			subLeftR->_parent = parent;
		}
		subLeft->_right = parent;
		parent->_parent = subLeft;

		if (parent == _root) { // 如果当前的parent为根
			_root = subLeft;
			subLeft->_parent = nullptr;
		}
		else {
			// 如果当前的parent不为根
			if (parent == parent_parent->_left) {
				parent_parent->_left = subLeft;
			}
			else {
				parent_parent->_right = subLeft;
			}
			subLeft->_parent = parent_parent;
		}

		// 调整平衡因子
		subLeft->_bf = 0;
		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
32

2.3.3、左右双旋

然后还有一些情况是单纯的左单旋和右单旋不能解决的，因为它们并不是单纯的“左左”或“右右”，比如在左子树的右子树中插入一个节点导致不平衡：

如果这时候只是单纯的对90这个根进行右单旋的话就会变成下面这样子：

我们会返现调整后30节点的平衡因子还是超出了范围，所以这样是不能解决问题的。

其实这里的主要问题是插入的位置变了，我们简单的分析一下单纯的右单旋就能的出问题的出处：

通过观察我们发现，右边单旋我们是通过把高的那颗子树（a）“往上层移动”来达到减少整体高度的，而矮的那颗子树(b)所在的层数不变。
而如果是在b这棵子树中插入：

其实就变成了，减少左子树的一个高度，去增加右子树的一个高度，但是还是不平衡，而且转化后也不是一个单纯的左单旋。

那该怎样解决呢？
其实我们可以先通过对30这棵子树进行左单旋，从而使旋转后的整棵子树变成左高右低的形式：

这样就可以把90这棵子树变成单纯的右单旋了。
然后再对90进行右单旋就变平衡了：

但是平衡因子又该怎么更新呢？
对于平衡因子更新的处理，我们可以先来看看双旋后的对比：

从中我们可以看得出，双旋其实还可以这样处理：
让subLeft成为新的根，然后subLeft成为subLeftR的左子树，parent成为subLeftR的右子树，子树b成为subLeft的右子树，子树c成为parent的左子树。

所以平衡因子的更新，的关键点就在于subLeftR的平衡因子，或者说是看subLeftR这棵子树的左子树高还是右子树高，即子树b高还是子树c高。

如果subLeftR的平衡因子为0，则说明subLeft本身就是新加入的节点，此时a，b，c，d这四棵子树都是空，所以subLeftR、subLeft和parent的平衡因子都为0。

如果subLeftR的平衡因子为1，则表示子树c要比子树b高1，所以更新后parent的平衡因子为0，subLeft的平衡因子为-1。

如果subLeftR的平衡因子为1，则表示子树b要比子树c高1，所以更新后subLeft的平衡因子为0，parent的平衡因子为1。

然后这是左右双旋的代码实现：

// 左右双旋
void RotateLR(Node* parent) {
	Node* subLeft = parent->_left;
	Node* subLeftR = subLeft->_right;
	int bf = subLeftR->_bf;
	RotateL(parent->_left);
	RotateR(parent);

	// 调整平衡因子
	if (0 == bf) {
		parent->_bf = 0;
		subLeft->_bf = 0;
		subLeftR->_bf = 0;
	}
	else if (-1 == bf) {
		subLeft->_bf = 0;
		parent->_bf = 1;
		subLeftR->_bf = 0;
	}
	else if (1 == bf) {
		subLeft->_bf = 0;
		parent->_bf = 0;
		subLeftR->_bf = -1;
	}
	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

2.3.4、右左双旋

右左双旋的分析逻辑其实和左右双旋一样，只是方向不同罢了。

然后这是右左双旋的代码实现，基本和左右双旋的一样：

// 右左双旋
void RotateRL(Node* parent) {
	Node* subRight = parent->_right;
	Node* subRightL = subRight->_left;
	int bf = subRightL->_bf;
	RotateR(parent->_right);
	RotateL(parent);
	
	// 调整平衡因子
	if (0 == bf) {
		// subRightL自己就是新增节点
		parent->_bf = 0;
		subRightL->_bf = 0;
		subRight->_bf = 0;
	}
	else if (1 == bf) {
		// subRight的右边新增
		parent->_bf = -1;
		subRight->_bf = 0;
		subRight->_bf = 0;
	}
	else if (-1 == bf) {
		// subRight的左边新增
		parent->_bf = 0;
		subRightL->_bf = 0;
		subRight->_bf = 1;
	}
	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
31

2.3.5、插入接口的整体代码实现

// 插入
bool insert(const pair<K, V>& key) {
	if (nullptr == _root) {
		_root = new Node(key);
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	
	// 先插入节点
	while (cur) {
		if (key.first > cur->_val.first) {
			parent = cur;
			cur = cur->_right;
		}
		else if (key.first < cur->_val.first) {
			parent = cur;
			cur = cur->_left;
		}
		else {
			return false;
		}
	}

	// 准备插入
	cur = new Node(key);
	if (key.first > parent->_val.first) {
		parent->_right = cur;
		cur->_parent = parent;
	}
	else {
		parent->_left = cur;
		cur->_parent = parent;

	}
	// 检查平衡因子，看看是否需要旋转调整
	while (parent) {
		//  先做第一步调整
		if (cur == parent->_left) {
			parent->_bf--;
		}
		else {
			parent->_bf++;
		}


		if (parent->_bf == 0) {
			return true;
		}
		else if (parent->_bf == 1 || parent->_bf == -1) { // 继续向上检查
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2) {
			if (parent->_bf == 2 && cur->_bf == 1) { // 左单旋
				RotateL(parent);
				return true;
			}
			else if (parent->_bf == -2 && cur->_bf == -1) { // 右单旋
				RotateR(parent);
				return true;
			}
			else if (parent->_bf == 2 && cur->_bf == -1) { // 右左双旋
				RotateRL(parent);
				return true;

			}
			else if (parent->_bf == -2 && cur->_bf == 1) { // 左右双旋
				RotateLR(parent);
				return true;
			}
		}
		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

三、验证AVL树

3.1、验证

验证AVL树我们需要验证两个方面，一个是左右高度差，另一个是平衡因子，因为有时候就算左右高度差就算正常，平衡因子在更新的时候也有可能会出错。而平衡因子一旦出错，就很有可能会带出更多的错误。

所以我们可以写一个判断是否平衡的函数：

// 检查是否平衡
bool isBalance() {
	return _isBalance(_root);
}

bool _isBalance(Node* root) {
	if (nullptr == root) {
		return true;
	}
	int leftH = _height(root->_left);
	int rightH = _height(root->_right);
	// 顺便检查一些平衡因子是否异常
	if (rightH - leftH != root->_bf) {
		cout << root->_val.first << " 平衡因子异常" << endl;
		return false;
	}
	return abs(rightH - leftH) < 2 && _isBalance(root->_left) && _isBalance(root->_right);
}

// 计算高度
int _height(Node* root) {
	if (nullptr == root) {
		return 0;
	}
	return max(_height(root->_left), _height(root->_right)) + 1;
}

// 中序遍历
void Inorder() {
	_Inorder(_root);
	cout << endl;
}

// 中序遍历子函数
void _Inorder(Node* root) {
	if (nullptr == root) {
		return;
	}
	_Inorder(root->_left);
	cout << "(" << root->_val.first << ", " << root->_bf << ") ";
	_Inorder(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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

然后我们就可以来跑几个测试看一下：