【C++】AVL树和红黑树（插入和测试详解）_红黑树测试

了解AVL树是为了了解红黑树，了解红黑树是为了更好的理解set和map。

1、AVL树

AVL树是在二叉搜索树的基础上进行了严格的平衡，能做到平衡的关键是通过平衡因子以及旋转。
AVL树有以下特性：

1. 任何根的左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。
2. 其中平衡因子是用右子树高度减去左子树高度。
3. 任何子树都是AVL树。

下面实现的AVL树还是KV结构的。

AVL树节点定义

#include <iostream>
#include <assert.h>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	//三叉链结构方便访问父节点
	struct AVLTreeNode<K, V>* _left;
	struct AVLTreeNode<K, V>* _right;
	struct AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv; //键值对 里面存储key和value
	int _bf; //平衡因子

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
};

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
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

 

1.1 AVL树的插入

1、AVL树的插入首先一开始和二叉搜索树的插入一样，先确定插入的位置，再和父节点链接。
 
2、插入完后，可能会破坏AVL树结构，所以要判断平衡因子。
插入新结点后，平衡因子会出现三种情况。

 
3、当平衡因子出现了-2或2的情况，这个时候就需要对parent进行旋转。
旋转有以下情况。

bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* cur = _root;
		Node* parent = _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 = new Node(kv);
		//只能用kv值来确定parent和cur的指向
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		
		//判断平衡因子
		while (parent)
		{
			if (parent->_left == cur)
			{
				//根节点左边插入节点，根的平衡因子-1
				parent->_bf--;
			}
			else
			{
				//根节点右边插入节点，根的平衡因子+1
				parent->_bf++;
			}

			//说明之前是-1或1，变为平衡
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//下面子树高度差也影响了上面的根结点，所以需要向上调整
				cur = parent;
				parent = cur->_parent;
			}
			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)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
				
				//旋转完后，结构平衡，退出
				break;

			}
			else
			{
				//如果平衡因子出现其它情况，说明错了
				assert(false);
			}
		}//while

		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
98
99
100
101
102
103

旋转：

	//右旋转
	void RotateR(Node* parent)
	{
		//从下到上依次修改
		Node* sub = parent->_left;
		Node* subR = sub->_right;
		
		//先改变最下面的subR结点
		parent->_left = subR;
		if (subR)
		{
			subR->_parent = parent;
		}
		
		//再改变parent结点
		sub->_right = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = sub;
		
		//最后改变sub结点
		if (ppnode == nullptr)
		{
			_root = sub;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = sub;
			}
			else
			{
				ppnode->_right = sub;
			}
			sub->_parent = ppnode;
		}

		parent->_bf = sub->_bf = 0;

	}
	
	//左旋和右旋类似
	void RotateL(Node* parent)
	{
		Node* sub = parent->_right;
		Node* subL = sub->_left;

		parent->_right = subL;
		if (subL)
		{
			subL->_parent = parent;
		}
		sub->_left = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = sub;

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

		parent->_bf = sub->_bf = 0;

	}

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		//保存subLR的平衡因子，为了知道从subLR哪边插入
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);
		if (bf == -1) // subLR左子树新增
		{
			subL->_bf = 0;
			parent->_bf = 1;
			subLR->_bf = 0;
		}
		else if (bf == 1) // subLR右子树新增
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == 0) // subLR自己就是新增
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	
	//和上面类似
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);
		if (bf == -1) // subRL左子树新增
		{
			subR->_bf = 1;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1) // subRL右子树新增
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0) // subRL自己就是新增
		{
			parent->_bf = 0;
			subR->_bf = 0;
			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
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

可能会有的问题解释（以下是自己的理解）：

1、如何想到旋转的情况？
其实从所有情况看就这两个情况以及他们的翻转，记住它们两个就好了。

 
2、如何看左右旋？
拿上图举例，左边是一个右旋能平衡的场景，只需要将最高的结点往右放就行。
右边是一个双选的场景，先将中间结点左旋，就成了图左边的场景，再右旋就行。

 

1.2 总结与测试AVL树

AVL树重点关注的是其平衡因子和选择如何使得AVL树平衡，通过插入了解就足够了。
下面是如何测试结果是AVL树：
1、通过每个结点的左右子树的高度判断平衡因子是否符合要求。
2、通过小和大的测试用例测试是不是AVL树

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	struct AVLTreeNode<K, V>* _left;
	struct AVLTreeNode<K, V>* _right;
	struct AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _bf;

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

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool insert(const pair<K, V>& kv){}

	void RotateR(Node* parent){}

	void RotateL(Node* parent){}

	void RotateLR(Node* parent){}

	void RotateRL(Node* parent){}

	int Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		int leftHight = Height(root->_left);
		int rightHight = Height(root->_right);

		return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
	}

	bool IsBalanceTree()
	{
		return  _IsBalanceTree(_root);
	}

	bool _IsBalanceTree(Node* parent)
	{
		if (parent == nullptr)
		{
			return true;
		}

		int leftHight = Height(parent->_left);
		int rightHight = Height(parent->_right);

		int diff = rightHight - leftHight;
		if (diff != parent->_bf || (diff > 1 || diff < -1))
		{
			cout << "有错" << endl;
			return false;
		}

		return _IsBalanceTree(parent->_left) && _IsBalanceTree(parent->_right);

	}

	void Inorder()
	{
		_Inorder(_root);
	}

	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_Inorder(root->_right);
	}
private:
	Node* _root = nullptr;
};

//出错用小用例调
void test1()
{
	int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	int arr2[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	AVLTree<int, int> t;
	for (auto& e : arr)
	{
		if(e == 18)
		{	
			//调试断点
			int a = 0;
		}
		t.insert(make_pair(e, e));
		t.IsBalanceTree();
	}
	t.Inorder();
}

//没错用多数据看看能不能过
#include <cstdlib>
void test2()
{
	srand(time(NULL));
	AVLTree<int, int> t;
	for (int i = 0; i < 100000; ++i)
	{
		int num = rand() % 10000;
		t.insert(make_pair(num, num));
	}
	t.IsBalanceTree();
}
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

 

2、红黑树

AVL树因为其严格的平衡导致它因为大量的旋转导致效率相较红黑树低。

红黑树不要求严格平衡，它为每个结点加上颜色区分，使得它趋向于平衡。它有着以下规定。

1. 根节点必须是黑色。
2. 根节点颜色要么是红色，要么是黑色。
3. 红色结点不能连续。（也就是如果一个结点是红的，其两个子结点都是黑的）
4. 每条路径下的黑色结点树要一样。
5. 叶子结点都是黑色结点（这里叶子结点代表NULL结点）

可能概念理解起来很抽象，我们通过代码一步步来。

首先搭建红黑树的框架。
大致和AVL树一样，只不过没有平衡因子，换成了颜色。

#include <iostream>
#include <assert.h>
using namespace std;

enum Color { RED, BLACK };

template<class K, class V>
struct RBTreeNode
{
	struct RBTreeNode<K, V>* _left;
	struct RBTreeNode<K, V>* _right;
	struct RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Color _col;

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(BLACK)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
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
24
25
26
27
28
29
30
31
32

2.1 红黑树的插入

1、首先如果根是空，新建的结点一定是黑色结点。这很好理解。
2、那么如果是后面创建的结点，是黑色还是红色呢？
 2.1 如果是黑色结点，那么想象一下，给某个路径添加一个黑色结点，使得这个路径的黑结点数量和其他路径不同，直接导致整个树不满足红黑树条件，直接破坏整个红黑树。
 2.2 如果是红色结点，最差只会出现两个红色结点相连的情况，只影响这个子树。
 
 所以综上选择影响最少的，选择创建红色结点。
3、插入前面和搜索树一样，得先确认插入的位置，以及和父节点链接。
4、调整红黑树


除此以外当然还有翻转的另一类情况。

bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = _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 = new Node(kv);
		cur->_col = RED;
		if (parent->_kv.first < cur->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		
		//调整
		//parent为红，代表插入的子节点也为红，需要调整。
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;
			//首先是第一类父亲结点在祖父结点左边，叔叔结点在右边的一类情况。
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					//第一种情况 叔叔结点存在且为红色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandparent->_col = RED;
					
					//向上调整，根节点的情况可以跑完整个调整，再设置_root->_col = BLACK;
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					//这一类是叔叔结点不存在以及存在为黑色
					//因为处理方法都是一样的，所以只要再区分直线型和折线型。
					if (parent->_right == cur)
					{
						//折线的情况
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						//直线的情况
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					break;
				}
			}
			else
			{
				//这一类是上面翻转，一样的处理，但注意方向
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandparent->_col = RED;

					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_right == cur)
					{
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					break;
				}

			}
		}
		
		//最后确保根节点为黑。
		_root->_col = BLACK;
		return true;
	}

//剩下左右旋转的代码和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
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

如果记忆红黑树的情况？（个人方式）
首先要记得红黑树的特性，根一定是黑结点，想清楚为什么插入要插红结点，这样能更情况红黑树的特性。
 
像情况一的推理一样，先插入黑色的根节点，再插入红结点，层序插入直到出现问题，此时面对第一个情况，叔叔结点存在并且为红色。
 
然后考虑叔叔结点为黑和不存在的情况，因为要旋转，再根据AVL树中记忆的两个情况，推出除了直线型情况，还有折线型情况。

2.2 红黑树的测试

在测试中，需要判断的

1. 根要为黑结点。
2.判断父子结点不能都为红
3.确保每条路径的黑结点数相同（这里通过先计算一条路径的黑结点数，再和每一条路径比对）

bool Check(Node* proot, int count, int ref)
	{
		if (proot == nullptr)
		{
			//检查黑结点
			if (count != ref)
			{
				cout << "出现路径黑结点树不同" << endl;
				return false;
			}
			return true;
		}

		Node* parent = proot->_parent;
		if (parent && (parent->_col == RED && proot->_col == RED))
		{
			cout << "出现了连续的红结点" << endl;
			return false;
		}

		if (proot->_col == BLACK)
		{
			count += 1;
		}

		return Check(proot->_left, count, ref) && Check(proot->_right, count, ref);

	}

	bool IsRBTree()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (RED == _root->_col)
		{
			cout << "根节点不能为红色" << endl;
			return false;
		}

		int ref = 0;
		Node* checkblack = _root;
		while (checkblack)
		{
			if (BLACK == checkblack->_col)
			{
				ref++;
			}
			checkblack = checkblack->_left;
		}

		return Check(_root, 0, ref);
	}
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

本节完~