• 数据结构：AVL树讲解（C++）

    AVL树

    1.AVL树的概念

    普通二叉搜索树：二叉搜索树

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

    AVL树也是二叉搜索树，但有以下特点：

    • 它的左右子树都是AVL树
    • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
    • 如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2​n)，搜索时间复杂度O( l o g 2 n log_2 n log2​n)。



    2.平衡因子

    AVL树的实现有很多种，本文引入平衡因子来维持高度稳定。
    本文平衡因子的定义：右子树高度 - 左子树的高度。

    依据每个节点的平衡因子，我们可以判断树的情况：

    • 平衡因子在(-1, 0, 1)，当前节点所在子树是稳定的。
    • 平衡因子为2或-2，当前节点所在子树是不稳定的。

    插入节点后平衡因子的更新：

    • 插入节点在右子树，平衡因子加一。
    • 插入节点在左子树，平衡因子减一。

    插入节点后平衡因子的不同情况（重点）：

    • 当前节点所在子树平衡因子为0，子树高度不变，不需要更新
      （原来一边高一边低，新插入在低一方，变成完全平衡）。
    • 当前节点所在子树平衡因子为1或-1，子树高度变化，需要向上更新。
      （原来完全平衡，现在一边高，子树整体高度加1，会影响到祖先的平衡，故需要向上更新看祖先所在子树是否平衡）
    • 当前节点所在子树平衡因子为2或-2，子树高度变化且不平衡，无需向上更新，对当前子树进行旋转操作。
      （当前子树已不平衡，向上更新没有意义，旋转操作是AVL树的核心，可以降低当前子树的高度且不影响上面的树结构）

    在这里插入图片描述



    3.节点的定义

    节点除了需要增加一个平衡因子，还需要增加一个父亲指针，方便我们进行平衡因子的向上更新和旋转操作。

    template<class K, class V>
struct ALVTreeNode
{
	ALVTreeNode<K, V>* _left;
	ALVTreeNode<K, V>* _right;
	ALVTreeNode<K, V>* _parent;
	pair<K, V> _kv;  //存储键值对
	int _bf;  //平衡因子
	ALVTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16



    4.插入操作

    PS：因为多加了一个父亲指针，所以插入时要注意更新父亲指针，平衡因子更新按前面的分析来还是比较简单的，旋转操作后面单独讲。

    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->_right;
		}
		else if (kv.first < cur->_kv.first)  //待插入节点在左子树
		{
			parent = cur;
			cur = cur->_left;
		}
		else  //待插入节点已存在
		{
			return false;
		}
	}
	cur = new Node(kv);
	if (kv.first > parent->_kv.first)  //插入在父亲的右边
	{
		parent->_right = cur;
	}
	else  //插入在父亲的左边
	{
		parent->_left = cur;
	}
	cur->_parent = parent;  //注意更新父亲指针

	//调整平衡因子
	while (parent)  //是有可能调整到根部的
	{
		if (cur == parent->_right)  //如果新插入的在右子树
		{
			parent->_bf++;
		}
		else if (cur == parent->_left)  //如果新插入的在左子树
		{
			parent->_bf--;
		}

		if (parent->_bf == 0) //插入后高度不变
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)  //插入后高度变化，但当前子树依然平衡，需要向上更新
		{
			parent = parent->_parent;
			cur = cur->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)  //插入后高度变化，并且当前子树已经不平衡,旋转
		{
			//旋转操作（先省略）
			break;
		}
		else //存在大于2小于-2的情况，树原来就不平衡，应该报错
		{
			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



    5.旋转操作（重点）

    5.1左单旋

    主体思想：

    在这里插入图片描述


    平衡因子的调整：
    在这里插入图片描述


    代码加细节处理：

    在这里插入图片描述

    void RotateL(Node* parent)  //左单旋,rotate->旋转
{
	Node* SubR = parent->_right;
	Node* SubRL = SubR->_left;  //这个有可能为空
	Node* ppnode = parent->_parent;  //原来父亲的父亲

	parent->_right = SubRL;
	if(SubRL)  SubRL->_parent = parent;

	SubR->_left = parent;
	parent->_parent = SubR;

	if (ppnode == nullptr)  //旋转的是整颗树
	{
		_root = SubR;
		SubR->_parent = nullptr;
	}
	else  //旋转的是部分
	{
		if (ppnode->_left == parent) //是左子树
		{
			ppnode->_left = SubR;
		}
		else  //是右子树
		{
			ppnode->_right = SubR;
		}
		SubR->_parent = ppnode;
	}
	//最后更新平衡因子
	parent->_bf = SubR->_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

    5.2右单旋

    PS：右单旋和左单旋类似，细节处理也差不多，这里只讲主体思路。
    主体思路：
    在这里插入图片描述

    平衡因子的调整：
    在这里插入图片描述

    代码：

    void RotateR(Node* parent)  //右单旋细节处理和左单旋差不多
{
	Node* SubL = parent->_left;
	Node* SubLR = SubL->_right;  //这个有可能为空
	Node* ppnode = parent->_parent;

	parent->_left = SubLR;
	if(SubLR)  SubLR->_parent = parent;

	SubL->_right = parent;
	parent->_parent = SubL;

	if (ppnode == nullptr)  //旋转的是整颗树
	{
		_root = SubL;
		SubL->_parent = nullptr;
	}
	else  //旋转部分
	{
		if (ppnode->_left == parent)  //是左子树
		{
			ppnode->_left = SubL;
		}
		else  //右子树
		{
			ppnode->_right = SubL;
		}
		SubL->_parent = ppnode;
	}
	//最后更新平衡因子
	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

    5.3左右双旋

    PS：双旋其实就是两次单旋(复用即可)，有前面的基础很好理解，重点在于旋转后平衡因子的更新。

    旋转思路：
    在这里插入图片描述

    平衡因子的调整：
    想知道平衡因子调整是那种情况，我们需要在旋转前记录SubRL的平衡因子bf：

    • bf为0是第一种情况。
    • bf为1是第二种情况。
    • bf为-1是第三种情况。

    在这里插入图片描述

    代码：

    void RotateLR(Node* parent)  //左右双旋
{
	Node* SubL = parent->_left;
	Node* SubLR = SubL->_right;
	int bf = SubLR->_bf;

	RotateL(SubL);
	RotateR(parent);

	if (bf == 1) //插入的是右边
	{
		SubLR->_bf = 0;
		SubL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == -1) //插入的是左边
	{
		SubLR->_bf = 0;
		SubL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 0) //刚好原来parent的左边就两个节点
	{
		SubLR->_bf = SubL->_bf = parent->_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

    5.4右左双旋

    PS：右左双旋和左右双旋思路是差不多的，重点还是在旋转后平衡因子的更新。

    旋转思路：
    在这里插入图片描述

    平衡因子的调整：
    和前面一样，旋转前确认SubRL的平衡因子bf即可。
    在这里插入图片描述

    代码：

    void RotateRL(Node* parent)  //右左双旋
{
	Node* SubR = parent->_right;
	Node* SubRL = SubR->_left;
	int bf = SubRL->_bf;

	RotateR(SubR);
	RotateL(parent);

	if (bf == 1)  //插入的是右边
	{
		SubRL->_bf = 0;
		SubR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1) //插入的是左边
	{
		SubRL->_bf = 0;
		parent->_bf = 0;
		SubR->_bf = 1;
	}
	else if (bf == 0)  //原来parent的右边就两个节点
	{
		SubRL->_bf = SubR->_bf = parent->_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



    6.一些简单的测试接口

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

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()
{
	return IsBalance(_root);
}

//看当前树是不是平衡树
//（1）看每个子树是否满足左右子树高度差不超过一
//（2）看平衡因子和所求的左右子树高度差是否一致
bool IsBalance(Node* root)
{
	if (root == nullptr)
		return true;

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

	if (rightHight - leftHight != root->_bf)
	{
		cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;
		return false;
	}

	return abs(rightHight - leftHight) < 2
		&& IsBalance(root->_left)
		&& IsBalance(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



    7.完整代码

    #pragma once
#include 
#include 
#include 
using namespace std;

template<class K, class V>
struct ALVTreeNode
{
	ALVTreeNode<K, V>* _left;
	ALVTreeNode<K, V>* _right;
	ALVTreeNode<K, V>* _parent;
	pair<K, V> _kv;  //存储键值对
	int _bf;
	ALVTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
		,_kv(kv)
	{}
};

template<class K, class V>
class AVLTree
{
public:
	typedef ALVTreeNode<K, V> Node;

	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->_right;
			}
			else if (kv.first < cur->_kv.first)  //待插入节点在左子树
			{
				parent = cur;
				cur = cur->_left;
			}
			else  //待插入节点已存在
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (kv.first > parent->_kv.first)  //插入在父亲的右边
		{
			parent->_right = cur;
		}
		else  //插入在父亲的左边
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//调整平衡因子
		while (parent)  //是有可能调整到根部的
		{
			if (cur == parent->_right)  //如果新插入的是右子树
			{
				parent->_bf++;
			}
			else if (cur == parent->_left)  //如果新插入的是左子树
			{
				parent->_bf--;
			}

			if (parent->_bf == 0) //插入后高度不变
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)  //插入后高度变化，但当前子树依然平衡，需要向上更新
			{
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)  //插入后高度变化，并且当前子树已经不平衡,旋转
			{
				//旋转
				if (parent->_bf == 2 && cur->_bf == 1)  //左单旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1) //右单旋
				{
					RotateR(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);
			}
		}
		return true;
	}

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

	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()
	{
		return IsBalance(_root);
	}

	//看当前树是不是平衡树
	//（1）看每个子树是否满足左右子树高度差不超过一
	//（2）看平衡因子和所求的左右子树高度差是否一致
	bool IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;

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

		if (rightHight - leftHight != root->_bf)
		{
			cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;
			return false;
		}

		return abs(rightHight - leftHight) < 2
			&& IsBalance(root->_left)
			&& IsBalance(root->_right);
	}

private:
	void RotateL(Node* parent)  //左单旋,rotate->旋转
	{
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;  //这个有可能为空
		Node* ppnode = parent->_parent;  //原来父亲的父亲

		parent->_right = SubRL;
		if(SubRL)  SubRL->_parent = parent;

		SubR->_left = parent;
		parent->_parent = SubR;

		if (ppnode == nullptr)  //旋转的是整颗树
		{
			_root = SubR;
			SubR->_parent = nullptr;
		}
		else  //旋转的是部分
		{
			if (ppnode->_left == parent) //是左子树
			{
				ppnode->_left = SubR;
			}
			else  //是右子树
			{
				ppnode->_right = SubR;
			}
			SubR->_parent = ppnode;
		}
		//最后更新平衡因子
		parent->_bf = SubR->_bf = 0;
	}

	void RotateR(Node* parent)  //右单旋细节处理和左单旋差不多
	{
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;  //这个有可能为空
		Node* ppnode = parent->_parent;

		parent->_left = SubLR;
		if(SubLR)  SubLR->_parent = parent;

		SubL->_right = parent;
		parent->_parent = SubL;

		if (ppnode == nullptr)  //旋转的是整颗树
		{
			_root = SubL;
			SubL->_parent = nullptr;
		}
		else  //旋转部分
		{
			if (ppnode->_left == parent)  //是左子树
			{
				ppnode->_left = SubL;
			}
			else  //右子树
			{
				ppnode->_right = SubL;
			}
			SubL->_parent = ppnode;
		}
		//最后更新平衡因子
		parent->_bf = SubL->_bf = 0;
	}

	void RotateLR(Node* parent)  //左右双旋
	{
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;
		int bf = SubLR->_bf;

		RotateL(SubL);
		RotateR(parent);

		if (bf == 1) //插入的是右边
		{
			SubLR->_bf = 0;
			SubL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == -1) //插入的是左边
		{
			SubLR->_bf = 0;
			SubL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 0) //刚好原来parent的左边就两个节点
		{
			SubLR->_bf = SubL->_bf = parent->_bf = 0;
		}
		else  //原来就不是平衡树，出现问题
		{

			assert(false);
		}
	}

	void RotateRL(Node* parent)  //右左双旋
	{
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;
		int bf = SubRL->_bf;

		RotateR(SubR);
		RotateL(parent);

		if (bf == 1)  //插入的是右边
		{
			SubRL->_bf = 0;
			SubR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1) //插入的是左边
		{
			SubRL->_bf = 0;
			parent->_bf = 0;
			SubR->_bf = 1;
		}
		else if (bf == 0)  //原来parent的右边就两个节点
		{
			SubRL->_bf = SubR->_bf = parent->_bf = 0;
		}
		else //原来就有问题
		{
			assert(false);
		}
	}

	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
    • 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
  • 相关阅读:
    【Java并发入门】03 互斥锁（上）：解决原子性问题
    数据采集的数据源有哪些？
    Linux毕业设计：基于OpenCV和QT库实现的人脸识别考勤/门禁系统(arm嵌入式ubuntu)
    Android kotlin开启协程的几种方式
    Mybatis（一）
    关系数据库理论【数据库系统概论】
    使用Spring Web Flow—Spring Web Flow的配置
    Adadelta--学习笔记
    探寻JWT的本质：它是什么？它有什么作用？
    网络安全笔记-网络设备专场（路由器、交换机、防火墙）
  • 原文地址：https://blog.csdn.net/2301_76269963/article/details/134230615