weixin_40725706

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】红黑树_红黑树概念 csdn

作者：weixin_40725706 | 2024-08-23 03:59:23

踩

红黑树概念 csdn

文章目录

1. 红黑树的概念
2. 红黑树的性质
3. 红黑树的实现
4. 红黑树与AVL树的比较
5.完整代码

1. 红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的，不像AVL树那样严格的平衡。
在这里插入图片描述

2. 红黑树的性质

每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的（即不能出现连续的红节点）
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（即每条路径上的黑色节点相等）
每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍(最长路径 <= 最短路径×2 )，为什么会这样呢？-- 如下图
在这里插入图片描述
如果比较AVL树和红黑树的搜索，AVL树的查找效率更高为：logN；

在这里插入图片描述

但是在插入和删除时红黑树的效率更高，它不需要严格的平衡，旋转的次数更少。

3. 红黑树的实现

3.1 节点与树的定义

插入时，我们是插入黑节点好还是红节点好呢？选择破坏性质3还是性质4呢？

如果插入黑色的，每条路径上的黑色节点数量就不相等了，每条路径都得改，非常麻烦。
如果插入红色的，如果它的父亲是黑色的，那就没有破坏任何规则；若父亲是红色，那就存在了连续的红节点，最长路径可能就会超过最短路径的二倍，需要进行调整了。

那我们肯定选择调整次数少的方式，因此新增节点的颜色给红色（注意：当插入节点为根节点时，应该是黑色）

节点的结构

	//颜色
	enum Color
	{
		RED = 0,
		BLACK
	};

	template<class K, class V>
	struct TreeNode
	{
		pair<K, V>  _kv;
		TreeNode<K, V>* _left;
		TreeNode<K, V>* _right;
		TreeNode<K, V>* _parent;//前驱节点
		Color _col;

		TreeNode(const pair<K, V>& kv)
			:_kv(kv)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(RED)//默认新节点为红色的
		{}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

树的结构

	template<class K,class V>
	class RBTree
	{
		typedef TreeNode<K, V> Node;
	public:
		RBTree()
			:_root(nullptr)
		{}
		RBTree(const RBTree<K, V>& tree)
		{
			this->_root = Copy(tree._root);
		}
		RBTree<K, V>& operator=(RBTree<K, V> tree)
		{
			swap(this->_root, tree._root);//现代写法
			return *this;
		}
		~RBTree()
		{
			Destroy(_root);
		}

		bool insert(const pair<K, V>& kv)
		{

		}

		Node* find(const pair<K, V>& kv)
		{

		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

	private:
		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			_root->_left = Copy(root->_left);
			_root->_right = Copy(root->_right);
			return _root;
		}
		
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_kv.first << " ";
			_InOrder(root->_right);
		}

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

3.2 查找

对于查找功能，搜索树都是一样的，非常简单就不赘述了。

		Node* find(const pair<K, V>& kv)
		{
			Node* cur = _root;

			while (cur)
			{
				if (cur->_kv.first < kv.first)
					cur = cur->_right;
				else if (cur->_kv.first > kv.first)
					cur = cur->_left;
				else
					return  cur;
			}
			return nullptr;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.3 插入（重点）

在插入时，我们要先按照搜索树的规则找到插入位置，然后将新节点插入；新节点插入后，要检查红黑树的规则有没有被破坏。注意：如果新插入的节点就是根节点，需要遵守规则2，根节点应为黑色。

		bool insert(const pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				//如果插入的节点是头节点，需要遵守规则2（根是黑的）
				//需要将默认的红色改为黑
				_root->_col = BLACK;
				return true;
			}
			
			Node* cur = _root;
			Node* parent = cur->_parent;
			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->_parent = parent;
			//父亲连孩子
			if (parent->_kv.first < kv.first)
				parent->_right = cur;
			else
				parent->_left = cur;

			//检查是否违反红黑树的规则
			//....
		}
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

检测新节点插入后，红黑树的性质是否造到破坏；因为新节点的默认颜色是红色，因此，

如果其父亲节点的颜色是黑色，没有违反红黑树任何规则，则不需要调整
但当其父亲节点颜色为红色时，就违反了性质三：不能有连在一起的红色节点

此时需要对红黑树分情况来讨论：
在这里插入图片描述

那违反规则后如何调整呢？又分为一下几种情况：

若新增节点为红，父亲为红，爷爷为黑，叔叔存在且为红，需要变色处理

在这里插入图片描述

但是当爷爷节点不是子树而是根时，需要将其变成黑色；若是子树，则保持它的红色，继续向上调整。

在这里插入图片描述

若新增节点为红，父亲为红，爷爷为黑，叔叔不存在或者叔叔存在且为黑，需要旋转+变色处理

右单旋的情况

父亲在爷爷的左边、新增在父亲的左边
如果叔叔不存在，旋转后将父亲变黑，爷爷变红
如果叔叔存在且为黑，旋转后将父亲变黑，爷爷变红

在这里插入图片描述
新增节点为红色的原因如下：

在这里插入图片描述

左右双旋的情况

父亲在爷爷的左边、新增在父亲的右边
如果叔叔不存在，旋转后将新增节点变黑，爷爷变红
如果叔叔存在且为黑，旋转后将新增节点变黑，爷爷变红

在这里插入图片描述

由于旋转的具体代码我们在AVL树种已经写过，这里就不给出具体步骤了。

	private:
		void RotateR(Node* parent)
		{
			Node* SubL = parent->_left;
			Node* SubLR = SubL->_right;

			//降级连兵
			parent->_left = SubLR;
			if (SubLR)
				SubLR->_parent = parent;
			Node* parentParent = parent->_parent;
			//升级连将
			SubL->_right = parent;
			parent->_parent = SubL;

			//将连将
			SubL->_parent = parentParent;
			if (parentParent == nullptr)
			{
				_root = SubL;
			}
			else
			{
				if (parentParent->_left == parent)
					parentParent->_left = SubL;
				else
					parentParent->_right = SubL;
			}
		}

		void RotateL(Node* parent)
		{
			Node* SubR = parent->_right;
			Node* SubRL = SubR->_left;

			//降级连兵
			parent->_right = SubRL;
			if (SubRL)
				SubRL->_parent = parent;
			Node* parentParent = parent->_parent;
			//升级连将
			SubR->_left = parent;
			parent->_parent = SubR;

			//将连将
			SubR->_parent = parentParent;
			if (parentParent == nullptr)
				_root = SubR;
			else
			{
				if (parentParent->_left == parent)
					parentParent->_left = SubR;
				else
					parentParent->_right = SubR;
			}
		}
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

当父亲在爷爷左侧时，大体框架就是这样：

在这里插入图片描述

当父亲在爷爷的右侧时，也是类似的，我们仅给出旋转时的图：

新增在父亲的右侧，构成“直”树，采用左单旋

在这里插入图片描述

右左双旋
新增在父亲的左侧，构成“弯”树，采用右左双旋

在这里插入图片描述

具体的代码实现如下：

				//grandfather->_right == parent
				else
				{
					Node* uncle = grandfather->_left;
					//如果叔叔存在且为红,仅需要变色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						//继续调整
						cur = grandfather;
						parent = cur->_parent;
					}
					//如果叔叔不存在 或者存在且为黑，需要旋转+变色
					else
					{
						//    g
						// u     p
						//           c
						if (parent->_right == cur)
						{
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//      g
						//   u      p
						//	      c
						else
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
						}
						break;
					}
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

那红黑树的插入就实现完了，完整代码如下：

		bool insert(const pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				//如果插入的节点是头节点，需要遵守规则2（根是黑的）
				//需要默认的红色改为黑
				_root->_col = BLACK;
				return true;
			}

			Node* cur = _root;
			Node* parent = cur->_parent;
			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->_parent = parent;
			//父亲连孩子
			if (parent->_kv.first < kv.first)
				parent->_right = cur;
			else
				parent->_left = cur;
			//-----------------------------------------------------------------------
			//检查是否违反红黑树的规则
			//如果父亲存在且为红，则违反规则
			while (parent && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;
				if (grandfather->_left == parent)
				{
					//根据爷爷节点找叔叔
					Node* uncle = grandfather->_right;

					//如果叔叔存在且为红,仅需要变色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						//然后继续向上调整
						cur = grandfather;
						parent = cur->_parent;
					}
					//如果叔叔不存在 或者存在且为黑，需要旋转+变色
					else
					{
						//判断单旋(直树)还是双旋(弯树)
						//单旋
						if (parent->_left == cur)
						{	
							//       g
							//     p   u
							//	c
							RotateR(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//双旋
						else
						{
							//        g
							//     p     u
							//	     c
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;

						}
						break;//旋转后已经符合规则，无需再调整了
					}
				}
				//grandfather->_right == parent
				else
				{
					Node* uncle = grandfather->_left;
					//如果叔叔存在且为红,仅需要变色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						//继续调整
						cur = grandfather;
						parent = cur->_parent;
					}
					//如果叔叔不存在 或者存在且为黑，需要旋转+变色
					else
					{
						//    g
						// u     p
						//           c
						if (parent->_right == cur)
						{
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//      g
						//   u      p
						//	      c
						else
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
						}
						break;
					}
				}
			}
			//父亲不存在，或者父亲为黑时，无需判断，直接将根变黑
			_root->_col = BLACK;
			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
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

3.4 红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)
检测其是否满足红黑树的性质
- 是否存在连续的红节点
- 每条路径黑色节点的个数是否相等

在检查每条路径上黑节点的个数时，首先要有一个黑节点个数的标准值，可以是最左侧或者最右侧；同时还要有一个变量或者容器来存储当前路径中表黑节点的个数。

		bool IsRBTree()
		{
			Node* root = _root;
			if (root == nullptr)//空树也是
				return true;
			
			if (root->_col == RED)
			{
				cout << "根节点为红色，违反规则" << endl;
				return false;
			}

			//先统计最左侧路径上有多少黑节点作为标准
			Node* cur = root;
			int blackNum = 0;
			while (cur)
			{
				if (cur->_col == BLACK)
					blackNum++;
				cur = cur->_left;
			}
			//k用来记录路径中黑节点的个数
			int k = 0;
			//在依据标准黑节点的个数，比较其它路径
			return _IsRBTree(root, blackNum, k);
		}
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

有了黑节点的标准值后，我们才可正式开始比较每条路径黑节点的个数

		bool _IsRBTree(Node* root, int blackNum, int k)
		{
			//一条路径走完，比较黑节点的个数
			if (root == nullptr)
			{
				if (blackNum != k)
				{
					cout << "路径黑节点个数不相等，违反规则" << endl;
					return false;
				}
				return true;
			}
			Node* parent = root->_parent;
			if (parent && root->_col == RED && parent->_col == RED)
			{
				cout << "存在连续的红节点，违反规则" << endl;
				return false;
			}

			//统计黑节点
			if (root->_col == BLACK)
				k++;
			//统计完根，在依次统计左右子树
			return _IsRBTree(root->_left, blackNum, k)
				&& _IsRBTree(root->_right, blackNum, k);
		}
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

4. 红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( $log_2 N$ )，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

5.完整代码

namespace my
{
	//颜色
	enum Color
	{
		RED = 0,
		BLACK
	};

	template<class K, class V>
	struct TreeNode
	{
		pair<K, V>  _kv;
		TreeNode<K, V>* _left;
		TreeNode<K, V>* _right;
		TreeNode<K, V>* _parent;//前驱节点
		Color _col;

		TreeNode(const pair<K, V>& kv)
			:_kv(kv)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(RED)//默认新节点为红色的
		{}
	};

	template<class K,class V>
	class RBTree
	{
		typedef TreeNode<K, V> Node;
	public:
		RBTree()
			:_root(nullptr)
		{}
		RBTree(const RBTree<K, V>& tree)
		{
			this->_root = Copy(tree._root);
		}
		RBTree<K, V>& operator=(RBTree<K, V> tree)
		{
			swap(this->_root, tree._root);//现代写法
			return *this;
		}
		~RBTree()
		{
			Destroy(_root);
		}

		bool insert(const pair<K, V>& kv)
		{
			if (_root == nullptr)
			{
				_root = new Node(kv);
				//如果插入的节点是头节点，需要遵守规则2（根是黑的）
				//需要默认的红色改为黑
				_root->_col = BLACK;
				return true;
			}

			Node* cur = _root;
			Node* parent = cur->_parent;
			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->_parent = parent;
			//父亲连孩子
			if (parent->_kv.first < kv.first)
				parent->_right = cur;
			else
				parent->_left = cur;

			//检查是否违反红黑树的规则
			//如果父亲存在且为红，则违反规则
			while (parent && parent->_col == RED)
			{
				Node* grandfather = parent->_parent;
				if (grandfather->_left == parent)
				{
					//根据爷爷节点找叔叔
					Node* uncle = grandfather->_right;

					//如果叔叔存在且为红,仅需要变色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						//然后继续向上调整
						cur = grandfather;
						parent = cur->_parent;
					}
					//如果叔叔不存在 或者存在且为黑，需要旋转+变色
					else
					{
						//判断单旋(直树)还是双旋(弯树)
						//单旋
						if (parent->_left == cur)
						{	
							//       g
							//     p   u
							//	c
							RotateR(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//双旋
						else
						{
							//        g
							//     p     u
							//	     c
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;

						}
						break;//旋转后已经符合规则，无需再调整了
					}
				}
				//grandfather->_right == parent
				else
				{
					Node* uncle = grandfather->_left;
					//如果叔叔存在且为红,仅需要变色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandfather->_col = RED;
						//继续调整
						cur = grandfather;
						parent = cur->_parent;
					}
					//如果叔叔不存在 或者存在且为黑，需要旋转+变色
					else
					{
						//    g
						// u     p
						//           c
						if (parent->_right == cur)
						{
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//      g
						//   u      p
						//	      c
						else
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
						}
						break;
					}
				}
			}
			//父亲不存在，或者父亲为黑时，无需判断，直接将根变黑
			_root->_col = BLACK;
			return true;
		}

		Node* find(const pair<K, V>& kv)
		{
			Node* cur = _root;

			while (cur)
			{
				if (cur->_kv.first < kv.first)
					cur = cur->_right;
				else if (cur->_kv.first > kv.first)
					cur = cur->_left;
				else
					return  cur;
			}
			return nullptr;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		bool IsRBTree()
		{
			Node* root = _root;
			if (root == nullptr)//空树也是
				return true;
			
			if (root->_col == RED)
			{
				cout << "根节点为红色，违反规则" << endl;
				return false;
			}

			//先统计最左侧路径上有多少黑节点作为标准
			Node* cur = root;
			int blackNum = 0;
			while (cur)
			{
				if (cur->_col == BLACK)
					blackNum++;
				cur = cur->_left;
			}
			//k用来记录路径中黑节点的个数
			int k = 0;
			//在依据标准黑节点的个数，比较其它路径
			return _IsRBTree(root, blackNum, k);
		}

		int Size()
		{
			return _Size(_root);
		}

		int Height()
		{
			return _Height(_root);
		}

	private:
		int _Height(Node* root)
		{
			if (root == nullptr)
				return 0;
			int leftH = _Height(root->_left);
			int rightH = _Height(root->_right);

			return leftH > rightH ? leftH + 1 : rightH + 1;
		}

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

			return 1 + _Size(root->_left) + _Size(root->_right);
		}

		bool _IsRBTree(Node* root, int blackNum, int k)
		{
			//一条路径走完，比较黑节点的个数
			if (root == nullptr)
			{
				if (blackNum != k)
				{
					cout << "路径黑节点个数不相等，违反规则" << endl;
					return false;
				}
				return true;
			}
			Node* parent = root->_parent;
			if (parent && root->_col == RED && parent->_col == RED)
			{
				cout << "存在连续的红节点，违反规则" << endl;
				return false;
			}

			//统计黑节点
			if (root->_col == BLACK)
				k++;
			//统计完根，在依次统计左右子树
			return _IsRBTree(root->_left, blackNum, k)
				&& _IsRBTree(root->_right, blackNum, k);
		}

		void RotateR(Node* parent)
		{
			Node* SubL = parent->_left;
			Node* SubLR = SubL->_right;

			//降级连兵
			parent->_left = SubLR;
			if (SubLR)
				SubLR->_parent = parent;
			Node* parentParent = parent->_parent;
			//升级连将
			SubL->_right = parent;
			parent->_parent = SubL;

			//将连将
			SubL->_parent = parentParent;
			if (parentParent == nullptr)
			{
				_root = SubL;
			}
			else
			{
				if (parentParent->_left == parent)
					parentParent->_left = SubL;
				else
					parentParent->_right = SubL;
			}
		}

		void RotateL(Node* parent)
		{
			Node* SubR = parent->_right;
			Node* SubRL = SubR->_left;

			//降级连兵
			parent->_right = SubRL;
			if (SubRL)
				SubRL->_parent = parent;
			Node* parentParent = parent->_parent;
			//升级连将
			SubR->_left = parent;
			parent->_parent = SubR;

			//将连将
			SubR->_parent = parentParent;
			if (parentParent == nullptr)
				_root = SubR;
			else
			{
				if (parentParent->_left == parent)
					parentParent->_left = SubR;
				else
					parentParent->_right = SubR;
			}
		}
		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			_root->_left = Copy(root->_left);
			_root->_right = Copy(root->_right);
			return _root;
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_kv.first << " ";
			_InOrder(root->_right);
		}

		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
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/1019381