【C++杂货铺】会杂耍的二叉搜索树——AVLTree

r囧r小猫 2023-10-16 16:48 10阅读 0赞

![在这里插入图片描述][b8ceddb223644d0a9986b6e87facd8a2.gif_pic_center]

#### **文章目录** ####

*  一、前言
 *  二、AVL 树的概念
 *  三、AVL 树结点的定义
 *  四、AVL 树的框架
 *  五、AVL 树的插入
 *   *  5.1 平衡因子的更新
     *  5.2 AVL 树的旋转
     *   *  5.2.1 左单旋
         *  5.2.2 右单旋
         *  5.2.3 先右单旋再左单旋
         *  5.2.4 先左单旋再右单旋
     *  5.3 AVL 树插入完整代码
     *  5.4 AVL 树的验证
 *  六、AVL 树的删除
 *  七、AVL 树的性能
 *  八、结语

## 一、前言 ##

在上一篇文章中对 set、multiset、map、multimap 进行了简单的介绍，在其文档介绍中发现，这几个容器都有一个共同点：其底层都是借助二叉搜索树来实现的。但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成为单支树，时间复杂度会退化成  O ( N ) O(N) O(N)，因此 set、map 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。那么今天就让我们对 set 和 map 的底层结构一探究竟。

## 二、AVL 树的概念 ##

二叉搜索树虽然可以缩短查找的效率，但是如果数据有序或者接近有序，二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率就会变得低下。因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过 1（超过 1 需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。一颗 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：

*  它的左右子树都是 AVL 树。
 *  左右子树高度之差（简称平衡因子）的绝对值不超过 1（-1、0、1）。

![在这里插入图片描述][8f5e614085454416ae658c468ca1d11e.png_pic_center]  
**小Tips**：如果一颗二叉搜索树是高度平均的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在  O ( l o g 2 n ) O(log2^n) O(log2n)，搜索时间复杂度为  O ( l o g 2 n ) O(log2^n) O(log2n)。平衡二叉搜索树中平衡并不是说要让平衡因子始终保持 0，这是做不到的，以两个结点为例，根节点的平衡因子只可能是 1 或者 -1，不可能是 0。二叉搜索树在实际中基本不太可能实现完全平衡，但是理论上可以，即满二叉树。后面我们学的多叉平衡搜索树在现实中可以做到完全平衡。

## 三、AVL 树结点的定义 ##

template<class K, class V>
    struct AVLTreeNode
    {
        
    	AVLTreeNode(const pair<K, V>& kv = pair<K, V>())
    		:_kv(kv)
    		,_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_bf(0)
    	{
        }
    
    	pair<K, V> _kv;//存储key和value
    	AVLTreeNode<K, V>* _left = nullptr;//指向左孩子
    	AVLTreeNode<K, V>* _right = nullptr;//指向右孩子
    	AVLTreeNode<K, V>* _parent = nullptr;//指向父亲结点
    	int _bf = 0;//平衡因子
    };

## 四、AVL 树的框架 ##

template<class K, class V>
    	class AVLTree
    	{
        
    		typedef AVLTreeNode<K, V> Node;
    	private:
    		Node* _root = nullptr;
    	};

## 五、AVL 树的插入 ##

AVL 树就是在二叉搜索树的基础上引入平衡因子，因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步：

*  按照二叉搜索树的方式插入新节点。
 *  调整结点的平衡因子。

### 5.1 平衡因子的更新 ###

新结点插入后，AVL 树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了 AVL 树的平衡性。假设新插入的结点为 `cur`，那么 `cur` 的平衡因子一定是 0，因为它的左后孩子都是 `nullptr`。但是 `cur` 的双亲结点 `parent` 的平衡因子一定需要调整，在插入之前，`parent` 的平衡因子分为三种情况：-1、0、1。对 `parent` 平衡因子的调整分为以下两种情况：

*  如果 `cur` 插入到 `parent` 的左侧，只需要给 `parent` 的平衡因子  − 1 -1 −1 即可。
 *  如果 `cur` 插入到 `parent` 的右侧，只需要给 `parent` 的平衡因子  \+ 1 +1 \+1 即可。

此时更新后 `parent` 的平衡因子有以下三种情况： 0 0 0、 ± 1 ±1 ±1、 ± 2 ±2 ±2

*  如果 `parent` 的平衡因子为  0 0 0，说明插入前 `parent` 的平衡因子一定为  ± 1 ±1 ±1，即左右孩子中一定有一个是 `nullptr`，并且新结点就插入在为空的一侧，插入后平衡因子被调整成  0 0 0，整棵树的高度任然不变，满足 AVL 树的性质，插入成功。
 *  如果 `parent` 的平衡因子是  ± 1 ±1 ±1，说明插入前 `parent` 的平衡因子一定是  0 0 0，即插入前 `parent` 的左右孩子都为 `nullptr`，并未新结点就插入在 `parent` 的任意一侧，所以插入后平衡因子被调整成了  ± 1 ±1 ±1，此时以 `parent` 为跟的树的高度增加了，需要继续沿着祖先结点向上更新，知道某一个祖先节点的平衡因子变成了  0 0 0，此时更新结束，插入成功。
 *  如果 `parent` 的平衡因子为  ± 2 ±2 ±2，则 `parent` 的平衡因子违反了平衡树的性质，需要对其进行旋转处理。

**情况一：**  
![在这里插入图片描述][6a2cccb1ebe94421b853decc87e8275f.png_pic_center]  
**情况二：**  
![在这里插入图片描述][dfd8d691f93c478893fc21b12d76a8b4.png_pic_center]  
**情况三：**  
![在这里插入图片描述][6b24ed1b6b8a424782a7a30a64f00749.png_pic_center]

### 5.2 AVL 树的旋转 ###

如果在一颗原本是平衡的 AVL 树中插入一个新结点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据结点插入位置的不同，AVL 树的旋转分为四种：

#### 5.2.1 左单旋 ####

新结点插入在较高右子树的右侧----右右：即 `parent` 的平衡因子是  2 2 2，`cur` 的平衡因子是  1 1 1，此时就需要左单旋。下面举两个左单旋的例子。

**例一：**  
![在这里插入图片描述][2cc0986ed79c441d996edc8269dd10fd.png_pic_center]  
**例二：**  
![在这里插入图片描述][804af32e06a44a9cbf2b32a5d3d2f4c4.png_pic_center]  
**抽象图：**  
![在这里插入图片描述][b45bc32414b34f5c89ff748664991806.png_pic_center]

**小Tips**：无论是这四种旋转中的哪一个，都要保证以下两点：首先在旋转的过程中要保证这棵树是搜索树，其次经过旋转后，这棵树应该变成平衡树，且降低这个子树的高度。这两点就决定了左旋的核心操作就是将 `cur` 的左子树给 `parent` 的右子树，再让 `parent` 成为 `cur` 的左子树。

void RotateL(Node* parent)
    {
        
    	Node* cur = parent->_right;
    	Node* curleft = cur->_left;
    
    	parent->_right = curleft;
    	cur->_left = parent;
    
    	if (curleft)
    	{
        
    		curleft->_parent = parent;
    	}
    	
    	Node* ppnode = parent->_parent;
    	parent->_parent = cur;
    
    	if (parent == _root)
    	{
        
    		_root = cur;
    		cur->_parent = nullptr;
    	}
    	else
    	{
        
    		if (ppnode->_left == parent)
    		{
        
    			ppnode->_left = cur;
    		}
    		else
    		{
        
    			ppnode->_right = cur;
    		}
    		cur->_parent = ppnode;
    	}
    	parent->_bf = cur->_bf = 0;
    }

#### 5.2.2 右单旋 ####

新结点插入在较高左子树的左侧----左左：即 `parent` 的平衡因子是  − 2 -2 −2，`cur` 的平衡因子是  − 1 -1 −1，此时就需要右单旋。

**抽象图：**  
![在这里插入图片描述][3ac04b40c4ee4165983a5e334ccba4a5.png_pic_center]

//右单旋
    void RotateR(Node* parent)
    {
        
    	Node* cur = parent->_left;
    	Node* curright = cur->_right;//此时的情况是curright比cur大，比parent小
    
    	parent->_left = curright;
    	cur->_right = parent;
    
    	if (curright)
    	{
        
    		curright->_parent = parent;
    	}
    	
    	Node* ppnode = parent->_parent;
    	parent->_parent = cur;
    
    	if (ppnode)
    	{
        
    		cur->_parent = ppnode;
    		if (ppnode->_left == parent)
    		{
        
    			ppnode->_left = cur;
    		}
    		else
    		{
        
    			ppnode->_right = cur;
    		}
    	}
    	else
    	{
        
    		_root = cur;
    		cur->_parent = nullptr;
    	}
    	parent->_bf = cur->_bf = 0;
    }

#### 5.2.3 先右单旋再左单旋 ####

新结点插入在较高右子树的左侧----右左：即 `parent` 的平衡因子是  2 2 2，`cur` 的平衡因子是  − 1 -1 −1。此时就需要先以 `cur` 为旋转点进行一个右单旋，再以 `parent` 为旋转点进行一个左单旋。下面给大家举两个例子。

**例一：**  
![在这里插入图片描述][c12e7a907179430f90d295591a76ea2f.png_pic_cemter]  
**例二：**  
![在这里插入图片描述][76a9a4729f7d42ffb13f40848f4b75d5.png_pic_center]  
**抽象图：**  
![在这里插入图片描述][1b7a25d3c2f149a8beaa9f33e200b8d7.png_pic_center]  
**小Tips**：右左双旋的本质是把 60 结点的右边给了 90 结点的左边，把 60 结点的左边给了 30 结点的右边，然后 60 结点变成了这颗子树的跟结点。进行右左双旋后，平衡因子的更新有以下三种情况：

*  插入后 60 结点的平衡因子是  0 0 0，说明 60 自己就是新增节点，此时 `parent` 和 `cur` 的平衡因子都是  0 0 0。
 *  插入后 60 结点的平衡因子是  − 1 -1 −1，说明是在 60 结点的左侧插入，此时 `parent` 的平衡因子是  0 0 0，`cur` 的平衡因子是  − 1 -1 −1。
 *  插入后 60 结点的平衡因子是  1 1 1，说明是在 60 结点的右侧插入，此时 `parent` 的平衡因子是  − 1 -1 −1，`cur` 的平衡因子是  0 0 0。

//右左双旋
    void RotateRL(Node* parent)
    {
        
    	Node* cur = parent->_right;
    	Node* curleft = cur->_left;
    	int bf = curleft->_bf;
    
    	RotateR(parent->_right);
    	RotateL(parent);
    
    	if (bf == 0)
    	{
        
    		parent->_bf = cur->_bf = curleft->_bf = 0;
    	}
    	else if (bf == 1)
    	{
        
    		cur->_bf = 0;
    		parent->_bf = -1;
    		curleft->_bf = 0;
    	}
    	else if (bf == -1)
    	{
        
    		cur->_bf = 1;
    		parent->_bf = 0;
    		curleft->_bf = 0;
    	}
    }

#### 5.2.4 先左单旋再右单旋 ####

新结点插入在较高左子树的右侧----左右：即 `parent` 的平衡因子是  − 2 -2 −2，`cur` 的平衡因子是  1 1 1。此时就需要先以 `cur` 为旋转点进行一个左单旋，然后再以 `parent` 为旋转点进行一个右单旋。下面为大家举两个具体的实例。

**例一：**  
![在这里插入图片描述][ed134f9b41a141b7b380aaddac95df06.png_pic_center]  
**例二：**  
![在这里插入图片描述][3b3dc6957ab34185985351abea9cbf93.png_pic_center]  
**抽象图：**  
![在这里插入图片描述][c514ddc2e92a4975afcdad8c7b91b03a.png_pic_center]

### 5.3 AVL 树插入完整代码 ###

/*AVLTree.h*/
    public:
    	bool Insert(const pair<K, V>& kv)
    	{
        
    		if (_root == nullptr)
    		{
        
    			_root = new Node(kv);
    			return true;//插入成功
    		}
    	
    		//找插入位置
    		Node* cur = _root;
    		Node* parent = nullptr;
    	
    		while (cur)
    		{
        
    			if (kv.first < cur->_kv.first)//小于往左走
    			{
        
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if (kv.first > cur->_kv.first)//大于往右走
    			{
        
    				parent = cur;
    				cur = cur->_right;
    			}
    			else//相等插入不了
    			{
        
    				return false;
    			}
    		}
    	
    		//找到待插入位置了，进行插入
    		cur = new Node(kv);
    		if (kv.first < parent->_kv.first)
    		{
        
    			parent->_left = cur;
    		}
    		else
    		{
        
    			parent->_right = cur;
    		}
    	
    		cur->_parent = parent;
    	
    		//控制平衡
    		//更新衡因子
    		while (parent)//我们这里始终更新的是parent的平衡银子，当parent为nullptr说明根节点_root的平衡因子已经被我们更新过了
    		{
        
    			//更新平衡因子
    			if (cur == parent->_left)
    			{
        
    				--(parent->_bf);
    			}
    			else if (cur == parent->_right)
    			{
        
    				++(parent->_bf);
    			}
    	
    			//判断更新后parent的平衡因子
    			if (parent->_bf == 0)//输入成功
    			{
        
    				break;
    			}
    			else if (parent->_bf == -1 || parent->_bf == 1)
    			{
        
    				//继续往上更新
    				cur = parent;
    				parent = parent->_parent;
    			}
    			else if (parent->_bf == -2 || parent->_bf == 2)
    			{
        
    				//需要旋转
    				if (cur->_bf == 1 && parent->_bf == 2)//左单旋
    				{
        
    					RotateL(parent);
    				}
    				else if (cur->_bf == -1 && parent->_bf == -2)//右单旋
    				{
        
    					RotateR(parent);
    				}
    				else if (cur->_bf == -1 && parent->_bf == 2)//右左单旋
    				{
        
    					RotateRL(parent);
    				}
    				else if (cur->_bf == 1 && parent->_bf == -2)//左右单旋
    				{
        
    					RotateLR(parent);
    				}
    	
    				break;
    			}
    			else
    			{
        
    				assert(false);
    			}
    		}
    	
    		return true;
    	}
    	
    	
    private:
    	//左单旋
    	void RotateL(Node* parent)
    	{
        
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    	
    		parent->_right = curleft;
    		cur->_left = parent;
    	
    		if (curleft)
    		{
        
    			curleft->_parent = parent;
    		}
    		
    		Node* ppnode = parent->_parent;
    		parent->_parent = cur;
    	
    		if (parent == _root)
    		{
        
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else
    		{
        
    			if (ppnode->_left == parent)
    			{
        
    				ppnode->_left = cur;
    			}
    			else
    			{
        
    				ppnode->_right = cur;
    			}
    			cur->_parent = ppnode;
    		}
    	
    		parent->_bf = cur->_bf = 0;
    	}
    	
    	//右单旋
    	void RotateR(Node* parent)
    	{
        
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;//此时的情况是curright比cur大，比parent小
    	
    		parent->_left = curright;
    		cur->_right = parent;
    	
    		if (curright)
    		{
        
    			curright->_parent = parent;
    		}
    		
    		Node* ppnode = parent->_parent;
    		parent->_parent = cur;
    	
    		if (ppnode)
    		{
        
    			cur->_parent = ppnode;
    			if (ppnode->_left == parent)
    			{
        
    				ppnode->_left = cur;
    			}
    			else
    			{
        
    				ppnode->_right = cur;
    			}
    		}
    		else
    		{
        
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		parent->_bf = cur->_bf = 0;
    	}
    	
    	//右左双旋
    	void RotateRL(Node* parent)
    	{
        
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    		int bf = curleft->_bf;
    	
    		RotateR(parent->_right);
    		RotateL(parent);
    	
    		if (bf == 0)
    		{
        
    			parent->_bf = cur->_bf = curleft->_bf = 0;
    		}
    		else if (bf == 1)
    		{
        
    			cur->_bf = 0;
    			parent->_bf = -1;
    			curleft->_bf = 0;
    		}
    		else if (bf == -1)
    		{
        
    			cur->_bf = 1;
    			parent->_bf = 0;
    			curleft->_bf = 0;
    		}
    	}
    	
    	//左右双旋
    	void RotateLR(Node* parent)
    	{
        
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    		int bf = curright->_bf;
    	
    		RotateL(cur);
    		RotateR(parent);
    	
    		if (bf == 0)
    		{
        
    			parent->_bf = cur->_bf = curright->_bf = 0;
    		}
    		else if (bf == 1)
    		{
        
    			parent->_bf = 0;
    			cur->_bf = -1;
    			curright->_bf = 0;
    		}
    		else if (bf == -1)
    		{
        
    			parent->_bf = 1;
    			cur->_bf = 0;
    			curright->_bf = 0;
    		}
    	}

### 5.4 AVL 树的验证 ###

AVL 树是在二叉搜索树的基础上加入了平衡的限制，因此要验证 AVL 树，可以分为两步：

*  验证其为二叉搜索树。如果中序遍历可以得到一个有序的序列，就说明为二叉搜索树。
 *  验证其为平衡树。每个结点左右子树高度差的绝对值不超过  1 1 1。其次检查结点的平衡因子是否计算正确。

public:
    	//中序
    	void Inorder()
    	{
        
    		return _Inorder(_root);
    	}
    	//检测平衡因子
    	bool IsBlance()
    	{
        
    		return _IsBalance(_root);
    	}
    private:
    	//中序
    	void _Inorder(Node* root)
    	{
        
    		if (root == nullptr)
    		{
        
    			return;
    		}
    	
    		_Inorder(root->_left);
    		cout << root->_kv.first << ' ';
    		_Inorder(root->_right);
    	
    		return;
    	}
    	
    	
    	//求树的高度
    	int Height(Node* root)
    	{
        
    		if (root == nullptr)
    		{
        
    			return 0;
    		}
    
    		int leftHeight = Height(root->_left);
    		int rightHeight = Height(root->_right);
    
    		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    	}
    	
    	//检测平衡因子
    	bool _IsBalance(Node* root)
    	{
        
    		if (root == nullptr)
    		{
        
    			return true;
    		}
    
    		int leftHeight = Height(root->_left);
    		int rightHeight = Height(root->_right);
    
    		if (rightHeight - leftHeight != root->_bf)
    		{
        
    			cout << "平衡因子异常:" << root->_bf << endl;
    			return false;
    		}
    
    		return abs(leftHeight - rightHeight) < 2
    			&& _IsBalance(root->_left)
    			&& _IsBalance(root->_right);
    	}

/*test.c*/
    int main()
    {
        
    	int a[] = {
         4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    	wcy::AVLTree<int, int> t;
    	for (auto e : a)
    	{
        
    		t.Insert(make_pair(e, e));
    		t.Inorder();
    		cout << endl;
    		if (t.IsBlance())
    		{
        
    			cout << "成功插入:" << e << endl;
    		}
    		else
    		{
        
    			cout << e << "插入失败" << endl;
    		}
    	}
    	return 0;
    }

![在这里插入图片描述][3c8b551f03d4440e9dd92a7260596d1c.png_pic_center]

## 六、AVL 树的删除 ##

因为 AVL 树也是二叉搜索树，可以按照二叉搜索树的方式将结点删除，然后再更新平衡因子，只不过与删除插入不同的是，删除结点后的平衡因子更新，最差情况下一直要调整到根结点的位置。具体的实现感兴趣的小伙伴可以参考《算法导论》或者《数据结构-用面向对象方法与C++描述》殷人昆版。

## 七、AVL 树的性能 ##

AVL 树是一颗绝对平衡的二叉搜索树，其要求每个结点的左右子树高度差的绝对值都不超过  1 1 1，这样在查询时可以保证高效的时间复杂度，即  O ( l o g 2 n ) O(log2^n) O(log2n)。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑 AVL 树，但一个结构经常修改，就不太适合。

## 八、结语 ##

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，[春人的主页][Link 1]还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！

![在这里插入图片描述][edc78985d03043828f98dcd5a8d2983e.gif_pic_center]

[b8ceddb223644d0a9986b6e87facd8a2.gif_pic_center]: https://img-blog.csdnimg.cn/b8ceddb223644d0a9986b6e87facd8a2.gif#pic_center
[8f5e614085454416ae658c468ca1d11e.png_pic_center]: https://img-blog.csdnimg.cn/8f5e614085454416ae658c468ca1d11e.png#pic_center
[6a2cccb1ebe94421b853decc87e8275f.png_pic_center]: https://img-blog.csdnimg.cn/6a2cccb1ebe94421b853decc87e8275f.png#pic_center
[dfd8d691f93c478893fc21b12d76a8b4.png_pic_center]: https://img-blog.csdnimg.cn/dfd8d691f93c478893fc21b12d76a8b4.png#pic_center
[6b24ed1b6b8a424782a7a30a64f00749.png_pic_center]: https://img-blog.csdnimg.cn/6b24ed1b6b8a424782a7a30a64f00749.png#pic_center
[2cc0986ed79c441d996edc8269dd10fd.png_pic_center]: https://img-blog.csdnimg.cn/2cc0986ed79c441d996edc8269dd10fd.png#pic_center
[804af32e06a44a9cbf2b32a5d3d2f4c4.png_pic_center]: https://img-blog.csdnimg.cn/804af32e06a44a9cbf2b32a5d3d2f4c4.png#pic_center
[b45bc32414b34f5c89ff748664991806.png_pic_center]: https://img-blog.csdnimg.cn/b45bc32414b34f5c89ff748664991806.png#pic_center
[3ac04b40c4ee4165983a5e334ccba4a5.png_pic_center]: https://img-blog.csdnimg.cn/3ac04b40c4ee4165983a5e334ccba4a5.png#pic_center
[c12e7a907179430f90d295591a76ea2f.png_pic_cemter]: https://img-blog.csdnimg.cn/c12e7a907179430f90d295591a76ea2f.png#pic_cemter
[76a9a4729f7d42ffb13f40848f4b75d5.png_pic_center]: https://img-blog.csdnimg.cn/76a9a4729f7d42ffb13f40848f4b75d5.png#pic_center
[1b7a25d3c2f149a8beaa9f33e200b8d7.png_pic_center]: https://img-blog.csdnimg.cn/1b7a25d3c2f149a8beaa9f33e200b8d7.png#pic_center
[ed134f9b41a141b7b380aaddac95df06.png_pic_center]: https://img-blog.csdnimg.cn/ed134f9b41a141b7b380aaddac95df06.png#pic_center
[3b3dc6957ab34185985351abea9cbf93.png_pic_center]: https://img-blog.csdnimg.cn/3b3dc6957ab34185985351abea9cbf93.png#pic_center
[c514ddc2e92a4975afcdad8c7b91b03a.png_pic_center]: https://img-blog.csdnimg.cn/c514ddc2e92a4975afcdad8c7b91b03a.png#pic_center
[3c8b551f03d4440e9dd92a7260596d1c.png_pic_center]: https://img-blog.csdnimg.cn/3c8b551f03d4440e9dd92a7260596d1c.png#pic_center
[Link 1]: https://blog.csdn.net/weixin_63115236?spm=1000.2115.3001.5343
[edc78985d03043828f98dcd5a8d2983e.gif_pic_center]: https://img-blog.csdnimg.cn/edc78985d03043828f98dcd5a8d2983e.gif#pic_center