当前位置:   article > 正文

【数据结构】AVL树(平衡二叉树)

avl树

前言:
在前面我们学习了平衡二叉树,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N),因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实现,下面我们要学习的AVL树就是处理二叉树自身缺陷的一种方式
在这里插入图片描述

一、AVL树的概念

在平衡二叉树中,如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素的时间复杂度会退化成O(N)。
因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
AVL树可以是一颗空树,如果不是,则它(或者它的任何一颗子树)需要具备以下性质:

  1. 它的左右孩子都是AVL树
  2. 左右子树的高度之差(平衡因子)的绝对值不超过1

如果它有n个节点,它的高度可以保持在log_n,时间复杂度为O(log_n)

二、AVL树的节点

AVL树的节点定义:

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K,V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _bf;//平衡因子

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
		, _kv
	{}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

三、AVL树的插入

总的来说,AVL树就是在二叉搜索树的基础上加了一个平衡因子,所以AVL树的插入分两步:

1.按二叉搜索树的方式插入节点
2.插入后调节平衡因子

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

	Node* parent = nullptr;
	Node* cur = _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);
	if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;

	while (parent)
	{
	    // 更新双亲的平衡因子
		if (cur == parent->_left)
		{
			parent->_bf--;
		}
		else
		{
			parent->_bf++;
		}
		//没有改变高度,不继续向上更新平衡因子
		if (parent->_bf == 0)
		{
			break;
		}
       // 插入前双亲的平衡因子是0,插入后双亲的平衡因为为1 或者                 -1 ,说明以双亲为根的二叉树的高度增加了一层,因此需要继续向上调整
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		// 双亲的平衡因子为正负2,违反了AVL树的平衡性,需要对以Parent为根的树进行旋转处理
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			// 旋转处理
			.......

			break;
		}
		else
		{
			// 插入之前AVL树就有问题
			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树的旋转

当插入一个新节点时,若是平衡因子到了2,则会导致树的不平衡,此时我们就要对这棵树进行旋转操作,使其重新满足AVL树的性质。
注意:旋转的本质是在降低树的高度
根据节点插入位置,AVL树的旋转分四种:

1.插入在较高左子树的左侧,使用右单旋

在这里插入图片描述
上图在插入前,AVL树是平衡的,新节点插入到4的左子树(注意:此处不是左孩子)中,2左子树增加了一层,导致以1为根的二叉树不平衡,要让1平衡,只能将1左子树的高度减少一层,右子树增加一层, 即将左子树往上提,这样1节点转下来,因为1节点比2节点大,只能将其放在2的右子树,而如果2节点有右子树,右子树根的值一定大于2节点,小于1节点,只能将其放在1节点的左子树,旋转完成后,更新节点的平衡因子即可。在旋转过程中,有以下几种情况需要考虑:

  1. **2节点的右孩子可能存在,也可能不存在
  2. 1节点可能是根节点,也可能是子树
    如果是根节点,旋转完成后,要更新根节点
    如果是子树,可能是某个节点的左子树,也可能是右子树**

说白了就是把5节点给1节点,再把1节点给2节点,就像是用手把1节点按下来一样(画图理解更佳)

代码:

void RotateR(Node* parent)//以1为旋转点,进行右单旋
{
	Node* subL = parent->_left;//2节点
	Node* subLR = subL->_right;//5节点,也可能没有
	parent->_left = subLR;//5节点给1节点
	if (subLR)
	{
		subLR->_parent = parent;
	}
	subL->_right = parent;
	//1节点可能是根节点,也可能是子树
    // 如果是根节点,旋转完成后,要更新根节点
    // 如果是子树,可能是某个节点的左子树,也可能是右子树
	Node* ppnode = parent->_parent;
	parent->_parent = subL;
	if (parent == root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subL;
		}
		else
		{
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
	//更新平衡因子
	subL->_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
  • 33
  • 34
  • 35
  • 36

2.插入在较高右子树的右侧,使用左单旋

在这里插入图片描述
参考上面的右单旋,代码:

void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

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

	subR->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subR;

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

	parent->_bf = 0;
	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
  • 33
  • 34

3.插入较高左子树的右侧,先左单旋再右单旋

在这里插入图片描述

将双旋变成单旋后再旋转,先以2节点为旋转点进行左单旋,然后再以1节点为旋转点进行右单旋,旋转完成后再考虑平衡因子的更新
代码:

void RorareLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	// 旋转之前,60的平衡因子可能是-1/0/1,旋转完成之后,根据情况对其他节点的平衡因子进行调整
	int bf = subLR->_bf;
	// 先对2节点进行左单旋
	RorateL(parent->_left);
	// 再对对1节点进行右单旋
	RotateR(parent);


	if (bf == -1)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 1)
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		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
  • 32
  • 33
  • 34
  • 35

4.插入较高右子树的左侧,先右单旋再左单旋

在这里插入图片描述
和上面的先左再右差不多

总结一下:假如以parent为根的子树不平衡,即parent的平衡因子为2或者-2,分以下情况考虑:

  1. parent的平衡因子为2,说明parent的右子树高,设parent的右子树的根为subR
    当subR的平衡因子为1,左单旋
    当subR的平衡因子为-1,右左单旋

  2. parent的平衡因子为-2,说明parent的左子树高,设parent的左子树的根为subL
    当subL的平衡因子为1,左单旋
    当subL的平衡因子为-1,左右单旋

旋转完成后,原parent为根的子树个高度降低,已经平衡,不需要再向上更新

五、AVL树的验证

如何去验证我们写出来的是AVL树呢?
我们知道,AVL树是在二叉搜索树的基础上加入了控制高度平衡限制,所以对于验证AVL树,我们可以分两步:

  1. 验证是否为二叉搜索树
    对其来一次中序遍历,如果得到一个有序的序列,则为二叉搜索树

  2. 验证是否为平衡树
    (1) 各节点高度差的绝对值不超过1 (2)各节点的平衡因子是否正确

代码:

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

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

bool _IsBalance(Node* root, int& height)
{
	// 空树也是AVL树
	if (root == nullptr)
	{
		height = 0;
		return true;
	}

	int leftHeight = 0, rightHeight = 0;
	if (!_IsBalance(root->_left, leftHeight)
		|| !_IsBalance(root->_right, rightHeight))
	{
		return false;
	}

	if (abs(rightHeight - leftHeight) >= 2)
	{
		cout << root->_kv.first << "不平衡" << endl;
		return false;
	}

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

	height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

	return true;
}

bool IsBalance()
{
	int height = 0;
	return _IsBalance(_root, height);
}
  • 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

六、AVL树的删除

AVL树也算是二叉搜索树,所以我们可以用二叉搜索树删除节点的方式进行删除(可以看看之前讲的二叉搜索树删除操作:https://blog.csdn.net/liuty0125/article/details/139508094?spm=1001.2014.3001.5501),不过有差别的是,在删除后还要更新删除后的平衡因子,最坏情况可能会更新到根节点,所以一般不会对AVL树进行删除操作

七、讲讲AVL树的性能

先说优点:AVL树是一个平衡的二叉搜索树,它的每个节点的左右子树高度差的绝对值不超过1,因此,哪怕最坏也只是查找高度次,保证了查询时高效的时间复杂度O(log_n)。

但是它的缺陷也很明显:如果我们要对AVL树做一些修改方面的操作时,它的性能就十分低了,因为在修改时我们还要维护它的绝对平衡,旋转的次数比较多,而且在删除时,最坏情况可能会更新到根节点。

所以,如果只是需要一种查询高效且有序的数据结构,且数据个数为静态(不改变),比较适合AVL树,但如果你需要经常修改的话,AVL树可能就不太适合了。

八、完整代码

#pragma once
#include<iostream>
#include<cstring>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K,V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _bf;//平衡因子

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


template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _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);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = cur->_parent;
				parent = parent->_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
				{
					RotateRL(parent);
				}

				break;
			}
			else
			{
				// 插入之前AVL树就有问题
				assert(false);
			}
		}

		return true;
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;

		Node* ppnode = parent->_parent;
		parent->_parent = subL;
		if (parent == root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
		subL->_bf = 0;
		parent->_bf = 0;
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

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

		subR->_left = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = subR;

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

		parent->_bf = 0;
		subR->_bf = 0;
	}
	void RorareLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		int bf = subLR->_bf;
		RorateL(parent->_left);
		RotateR(parent);


		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			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);

		subRL->_bf = 0;
		if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return NULL;
	}
	
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->left);
		cout << root->value << " ";
		_InOrder(root->right);
	}
	void InOrder()
	{
		_InOrder(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;
	}

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

	bool _IsBalance(Node* root, int& height)
	{
		if (root == nullptr)
		{
			height = 0;
			return true;
		}

		int leftHeight = 0, rightHeight = 0;
		if (!_IsBalance(root->_left, leftHeight)
			|| !_IsBalance(root->_right, rightHeight))
		{
			return false;
		}

		if (abs(rightHeight - leftHeight) >= 2)
		{
			cout << root->_kv.first << "不平衡" << endl;
			return false;
		}

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

		height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

		return true;
	}

	bool IsBalance()
	{
		int height = 0;
		return _IsBalance(_root, height);
	}

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

	size_t _Size(Node* root)
	{
		if (root == NULL)
			return 0;

		return _Size(root->_left)
			+ _Size(root->_right) + 1;
	}
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
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/739927
推荐阅读
相关标签
  

闽ICP备14008679号