【C++进阶】：红黑树

╰半橙微兮° 2024-03-04 02:01 87阅读 0赞

#### 红黑树 ####

*  一.红黑树简单实现
 *   *  1.性质
     *  二.更新颜色
     *   *  1.情况一
         *  2.情况二
         *  3.情况三
     *  3.完整代码(代码有注释，稍微画图很容易理解,旋转部分可以看我的AVL树博客)
 *  二.map和set
 *   *  1.基本实现
     *  2.迭代器

**本篇的前置条件是AVL树的旋转和搜索树，如果不了解可以看看我的AVL树博客**

## 一.红黑树简单实现 ##

### 1.性质 ###

> **红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。**

1.  每个结点不是红色就是黑色。
2.  根节点是黑色的。
3.  如果一个节点是红色的，则它的两个孩子结点是黑色的。
4.  对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
5.  每个叶子结点都是黑色的(此处的叶子结点指的是空结点）。

*创建节点*

![在这里插入图片描述][06d9131b6ec84e348822a93f7196e6cc.png]

![在这里插入图片描述][e955028381034ffc80088475b40f6c5f.png]

### 二.更新颜色 ###

#### 1.情况一 ####

插入一个节点，它的父亲是红色的并且它有叔叔且叔叔也是红色的。

![在这里插入图片描述][404dc93ad8d04aaaa122e0f953b1889e.png]

#### 2.情况二 ####

*如果叔叔不存在*

![在这里插入图片描述][88cc7b9c57054e30af4eecb418e6d155.png]  
此时单纯的变色是无法解决问题的，需要进行旋转，在此情况是右旋。

![在这里插入图片描述][325ba3ce0cb647f5a8e5150701e13080.png]

#### 3.情况三 ####

*叔叔存在且为黑，注意此时插入的点是在最下面，cur经过上面的转变后到达图示的位置。*

![在这里插入图片描述][e69418384f6b42228376ecb8d456dfd5.png]

![在这里插入图片描述][a2b26e51d00646d68f29717a2243cb7a.png]

### 3.完整代码(代码有注释，稍微画图很容易理解,旋转部分可以看我的AVL树博客) ###

*测试*

#include"RBTree.h"
    #include<vector>
    
    int main()
    {
        
    	RBTree<int, int> t;
    	srand(time(0));
    	vector<int>a;
    	for (int i = 0; i < 100; i++)
    	{
        
    		int x = rand();
    		a.push_back(x);
    	}
    	
    	for (auto x : a)
    		t.Insert(make_pair(x, x));
    	cout << t.IsBalance() << endl;
    	return 0;
    }

*树*

#include<iostream>
    #include<assert.h>
    using namespace std;
    
    
    
    enum Color
    {
        
    	RED,
    	BLACK
    };
    
    template<class K,class V>
    struct RBTreeNode
    {
        
    	pair<K, V> _kv;
    	RBTreeNode<K, V>* _left;
    	RBTreeNode<K, V>* _right;
    	RBTreeNode<K, V>* _parent;
    
    	RBTreeNode(const pair<K,V>& kv)//初始化节点
    		:_kv(kv)
    		,_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_col(RED)
    	{
        }
    
    	Color _col;
    };
    
    
    template<class K,class V>
    class RBTree
    {
        
    public:
    	typedef RBTreeNode<K, V> Node;
    
    	bool Insert(const pair<K, V>& kv)
    	{
        
    		if (_root == nullptr)
    		{
        
    			_root = new Node(kv);
    			_root->_col = BLACK;//根为黑色
    			return true;
    		}
    
    		Node* parent = _root;
    		Node* cur = _root;
    		//一般的搜索二叉树插入
    		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);
    		cur->_parent = parent;
    		
    		if (parent->_kv > kv) parent->_left = cur;
    		else parent->_right = cur;
    
    		//进行颜色更新
    		while (parent && parent->_col == RED)
    		{
        
    			Node* grandparent = parent->_parent;
    			Node* uncle;
    			//找到叔叔
    			if (grandparent->_left == parent)
    				uncle = grandparent->_right;
    			else
    				uncle = grandparent->_left;
    
    			//如果叔叔存在且为红色
    			if (uncle && uncle->_col == RED)
    			{
        
    				//变颜色
    				parent->_col = uncle->_col = BLACK;
    				grandparent->_col = RED;
    
    				//继续向上
    				cur = grandparent;
    				parent = cur->_parent;
    			}
    			//如果叔叔不存在或者是黑色
    			else
    			{
        
    				//parent是左，cur是左，进行右单旋
    				if (grandparent->_left == parent && parent->_left == cur)
    				{
        
    					RotateR(grandparent);
    					grandparent->_col = RED;
    					parent->_col = BLACK;
    				}
    				//parent是左，cur是右，进行左右旋
    				else if (grandparent->_left == parent && parent->_right == cur)
    				{
        
    					RotateL(parent);
    					RotateR(grandparent);
    
    					cur->_col = BLACK;
    					grandparent->_col = RED;
    				}
    				//parent是右,cur是右,进行左单旋
    				else if (grandparent->_right == parent && parent->_right == cur)
    				{
        
    					RotateL(grandparent);
    
    					grandparent->_col = RED;
    					parent->_col = BLACK;
    				}
    				//parent是右，cur是左,进行右左旋
    				else
    				{
        
    					RotateR(parent);
    					RotateL(grandparent);
    
    					cur->_col = BLACK;
    					grandparent->_col = RED;
    				}
    			}
    		}
    		_root->_col = BLACK;
    	}
    	//旋转函数
    	void RotateL(Node* parent)
    	{
        
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    		Node* ppnode = parent->_parent;//记录父节点的父节点
    
    		//父节点的右孩子变成curleft
    		parent->_right = curleft;
    		if (curleft)//细节注意curleft为空时不能操作
    			curleft->_parent = parent;
    		//父节点变为cur的左孩子
    		cur->_left = 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;
    		}
    	}
    	void RotateR(Node* parent)
    	{
        
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    		Node* pphead = parent->_parent;
    
    		//父节点到cur右边
    		cur->_right = parent;
    		parent->_parent = cur;
    		//父节点的左孩子变成curright
    		parent->_left = curright;
    		if (curright)
    			curright->_parent = parent;
    		//cur的父节点变为原来父节点的父节点
    		if (pphead)//如果不是根节点
    		{
        
    			if (pphead->_left == parent)
    				pphead->_left = cur;
    			else
    				pphead->_right = cur;
    			cur->_parent = pphead;
    		}
    		else
    		{
        
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    	}
    	void RotateRL(Node* parent)
    	{
        
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    
    		RotateR(parent->_right);
    		RotateL(parent);
    	}
    	void RotateLR(Node* parent)
    	{
        
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    
    		RotateL(parent->_left);
    		RotateR(parent);
    	}
    
    
    	//测试是否出问题
    	bool IsBalance()
    	{
        
    		return IsBalance(_root);
    	}
    	bool IsBalance(Node* root)
    	{
        
    		//根是否为黑色
    		if (_root->_col != BLACK)
    		{
        
    			cout << "根不是红色"<<endl;
    			return false;
    		}
    
    		int blackcheck = 0;
    		Node* cur = _root;
    		while (cur)
    		{
        
    			if (cur->_col == BLACK)
    				blackcheck++;
    			cur = cur->_left;
    		}
    
    		//判断是否有两个连续的红色和每条路径的黑色是否相同
    		return CheckColor(_root,blackcheck,0);
    	}
    
    	bool CheckColor(Node*root,int blackcheck,int blacknum)
    	{
        
    		if (root == nullptr)
    		{
        
    			//检查是否每条路径的黑色相同
    			if (blackcheck != blacknum)
    			{
        
    				cout << "路径上黑色个数不同" << ' ';
    				return false;
    			}
    			return true;
    		}
    
    		//判断是否有两个连续的红色
    		Node* parent = root->_parent;
    		if (root->_col == RED)
    		{
        
    			if (parent && parent->_col == RED)
    			{
        
    				cout << "有连续的红色" << ' ';
    				return false;
    			}
    		}
    		if (root->_col == BLACK) blacknum++;
    
    		return CheckColor(root->_left, blackcheck, blacknum)
    			&& CheckColor(root->_right, blackcheck, blacknum);
    	}
    private:
    	Node* _root = nullptr;
    };

## 二.map和set ##

### 1.基本实现 ###

map和set虽然功能不同，但在库里都是使用红黑树实现的，接下来对红黑树的代码进行改造。在库里，set和map走的是泛型，也就是map和set可以使用同一份红黑树代码。

*对红黑树进行泛化处理，方便之后传参*

![在这里插入图片描述][7918a8b8082544a18011a81d6d45fbd9.png]

这里有一个问题：对于data，如果是set那么我们可以直接比较，但如果是map呢？map的T是一个pair，我们是不能直接比较的，为了解决这个问题，我们可以使用仿函数（如果不了解可以看看我的仿函数这篇博客）。

*map里返回pair的firist*  
![在这里插入图片描述][27fa617f95084169874e5681d2969d21.png]

*set为了保持一致，直接返回key*  
![在这里插入图片描述][cd4131e90b5342029db67a70fed6fd44.png]

*在树里创建一个对象，用该对象的规则进行比较*  
![在这里插入图片描述][0ae1c03c8ab14c8691d40ebbf2d36358.png]

*分别对map和set加入插入操作*

![在这里插入图片描述][b50e51487cbb4c219cf45014bdddc261.png]

![在这里插入图片描述][349d33ef80a44ce3be9ca3ea149adbc4.png]

### 2.迭代器 ###

首先需要明确迭代器的功能，就是能够将整棵树进行中序遍历。

![在这里插入图片描述][d22733c9f2bd4d2e804560516e7fbd12.png]

我们需要++，\*，–，!=等操作。对于++操作，我们需要进行中序遍历。

![在这里插入图片描述][9624a345963841d6994f03ad15a67fd2.png]

![在这里插入图片描述][5eed5680357b4b5aa944fbf203117f65.png]

其他一些小功能就不细说，下面是完整代码

*RBTree.h*

#pragma once
    #include<iostream>
    using namespace std;
    
    enum Colour
    {
        
    	RED,
    	BLACK
    };
    
    template<class T>
    struct RBTreeNode
    {
        
    	RBTreeNode<T>* _left;
    	RBTreeNode<T>* _right;
    	RBTreeNode<T>* _parent;
    	
    	T _data;
    	Colour _col;
    
    	RBTreeNode(const T& data)
    		:_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_data(data)
    		,_col(RED)
    	{
        }
    };
    
    template<class T>
    struct __TreeIterator
    {
        
    	typedef RBTreeNode<T> Node;
    	typedef __TreeIterator<T> Self;
    	Node* _node;
    
    	__TreeIterator(Node* node)
    		:_node(node)
    	{
        }
    
    	T& operator*()
    	{
        
    		return _node->_data;
    	}
    
    	T* operator->()
    	{
        
    		return &_node->_data;
    	}
    
    	bool operator!=(const Self& s)
    	{
        
    		return _node != s._node;
    	}
    	Self& operator++()
    	{
        
    		if (_node->_right)
    		{
        
    			// 右树的最左节点(最小节点)
    			Node* subLeft = _node->_right;
    			while (subLeft->_left)
    			{
        
    				subLeft = subLeft->_left;
    			}
    
    			_node = subLeft;
    		}
    		else
    		{
        
    			Node* cur = _node;
    			Node* parent = cur->_parent;
    			// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点
    			while (parent)
    			{
        
    				if (cur == parent->_left)
    				{
        
    					break;
    				}
    				else
    				{
        
    					cur = cur->_parent;
    					parent = parent->_parent;
    				}
    			}
    
    			_node = parent;
    		}
    
    		return *this;
    	}
    };
    
    // set->RBTree<K, K, SetKeyOfT> _t;
    // map->RBTree<K, pair<K, V>, MapKeyOfT> _t;
    
    template<class K, class T, class KeyOfT>
    struct RBTree
    {
        
    	typedef RBTreeNode<T> Node;
    public:
    	typedef __TreeIterator<T> iterator;
    	// const_iterator
    
    	iterator begin()
    	{
        
    		Node* leftMin = _root;
    		while (leftMin && leftMin->_left)
    		{
        
    			leftMin = leftMin->_left;
    		}
    
    		return iterator(leftMin);
    	}
    
    	iterator end()
    	{
        
    		return iterator(nullptr);
    	}
    
    
    	Node* Find(const K& key)
    	{
        
    		Node* cur = _root;
    		KeyOfT kot;
    		while (cur)
    		{
        
    			if (kot(cur->_data) < key)
    			{
        
    				cur = cur->_right;
    			}
    			else if (kot(cur->_data) > key)
    			{
        
    				cur = cur->_left;
    			}
    			else
    			{
        
    				return cur;
    			}
    		}
    
    		return nullptr;
    	}
    
    	bool Insert(const T& data)
    	{
        
    		if (_root == nullptr)
    		{
        
    			_root = new Node(data);
    			_root->_col = BLACK;
    			return true;
    		}
    
    		Node* parent = nullptr;
    		Node* cur = _root;
    
    		KeyOfT kot;
    		while (cur)
    		{
        
    			if (kot(cur->_data) < kot(data))
    			{
        
    				parent = cur;
    				cur = cur->_right;
    			}
    			else if (kot(cur->_data) > kot(data))
    			{
        
    				parent = cur;
    				cur = cur->_left;
    			}
    			else
    			{
        
    				return false;
    			}
    		}
    
    		cur = new Node(data);
    		cur->_col = RED;
    
    		if (kot(parent->_data) < kot(data))
    		{
        
    			parent->_right = cur;
    		}
    		else
    		{
        
    			parent->_left = cur;
    		}
    
    		cur->_parent = parent;
    
    		while (parent && parent->_col == RED)
    		{
        
    			Node* grandfather = parent->_parent;
    			if (parent == grandfather->_left)
    			{
        
    				Node* uncle = grandfather->_right;
    				// u存在且为红
    				if (uncle && uncle->_col == RED)
    				{
        
    					// 变色
    					parent->_col = uncle->_col = BLACK;
    					grandfather->_col = RED;
    
    					// 继续向上处理
    					cur = grandfather;
    					parent = cur->_parent;
    				}
    				else // u不存在 或 存在且为黑
    				{
        
    					if (cur == parent->_left)
    					{
        
    						//     g
    						//   p
    						// c
    						RotateR(grandfather);
    						parent->_col = BLACK;
    						grandfather->_col = RED;
    					}
    					else
    					{
        
    						//     g
    						//   p
    						//		c
    						RotateL(parent);
    						RotateR(grandfather);
    
    						cur->_col = BLACK;
    						grandfather->_col = RED;
    					}
    
    					break;
    				}
    			}
    			else // parent == grandfather->_right
    			{
        
    				Node* uncle = grandfather->_left;
    				// u存在且为红
    				if (uncle && uncle->_col == RED)
    				{
        
    					// 变色
    					parent->_col = uncle->_col = BLACK;
    					grandfather->_col = RED;
    
    					// 继续向上处理
    					cur = grandfather;
    					parent = cur->_parent;
    				}
    				else
    				{
        
    					if (cur == parent->_right)
    					{
        
    						// g
    						//	  p
    						//       c
    						RotateL(grandfather);
    						grandfather->_col = RED;
    						parent->_col = BLACK;
    					}
    					else
    					{
        
    						// g
    						//	  p
    						// c
    						RotateR(parent);
    						RotateL(grandfather);
    						cur->_col = BLACK;
    						grandfather->_col = RED;
    					}
    
    					break;
    				}
    			}
    		}
    
    		_root->_col = BLACK;
    
    		return true;
    	}
    
    	void RotateL(Node* parent)
    	{
        
    		++_rotateCount;
    
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    
    		parent->_right = curleft;
    		if (curleft)
    		{
        
    			curleft->_parent = parent;
    		}
    
    		cur->_left = 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;
    		}
    	}
    
    
    	void RotateR(Node* parent)
    	{
        
    		++_rotateCount;
    
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    
    		parent->_left = curright;
    		if (curright)
    			curright->_parent = parent;
    
    		Node* ppnode = parent->_parent;
    		cur->_right = parent;
    		parent->_parent = cur;
    
    		if (ppnode == nullptr)
    		{
        
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else
    		{
        
    			if (ppnode->_left == parent)
    			{
        
    				ppnode->_left = cur;
    			}
    			else
    			{
        
    				ppnode->_right = cur;
    			}
    
    			cur->_parent = ppnode;
    		}
    	}
    	
    
    	bool CheckColour(Node* root, int blacknum, int benchmark)
    	{
        
    		if (root == nullptr)
    		{
        
    			if (blacknum != benchmark)
    				return false;
    
    			return true;
    		}
    
    		if (root->_col == BLACK)
    		{
        
    			++blacknum;
    		}
    
    		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
    		{
        
    			cout << root->_kv.first << "出现连续红色节点" << endl;
    			return false;
    		}
    
    		return CheckColour(root->_left, blacknum, benchmark)
    			&& CheckColour(root->_right, blacknum, benchmark);
    	}
    
    	bool IsBalance()
    	{
        
    		return IsBalance(_root);
    	}
    
    	bool IsBalance(Node* root)
    	{
        
    		if (root == nullptr)
    			return true;
    
    		if (root->_col != BLACK)
    		{
        
    			return false;
    		}
    
    		// 基准值
    		int benchmark = 0;
    		Node* cur = _root;
    		while (cur)
    		{
        
    			if (cur->_col == BLACK)
    				++benchmark;
    
    			cur = cur->_left;
    		}
    
    		return CheckColour(root, 0, benchmark);
    	}
    
    	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;
    	}
    
    private:
    	Node* _root = nullptr;
    
    public:
    	int _rotateCount = 0;
    };

*Map.h*

#include"RBTree.h"
    
    namespace Mine
    {
        
    	template<class K, class V>
    	class map
    	{
        
    		struct MapKeyOfT
    		{
        
    			const K& operator()(const pair<K, V>& kv)
    			{
        
    				return kv.first;
    			}
    		};
    	public:
    		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
    		iterator begin()
    		{
        
    			return _t.begin();
    		}
    
    		iterator end()
    		{
        
    			return _t.end();
    		}
    
    		V& operator[](const K& key);
    
    		bool insert(const pair<K, V>& kv)
    		{
        
    			return _t.Insert(kv);
    		}
    
    	private:
    		RBTree<K, pair<K, V>, MapKeyOfT> _t;
    	};
    }

*Set.h*

#include"RBTree.h"
    
    namespace Mine
    {
        
    	template<class K>
    	class set
    	{
        
    		struct SetKeyOfT
    		{
        
    			const K& operator()(const K& key)
    			{
        
    				return key;
    			}
    		};
    	public:
    		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
    
    		iterator begin()
    		{
        
    			return _t.begin();
    		}
    
    		iterator end()
    		{
        
    			return _t.end();
    		}
    
    		bool insert(const K& key)
    		{
        
    			return _t.Insert(key);
    		}
    	private:
    		RBTree<K, K, SetKeyOfT> _t;
    	};
    }

[06d9131b6ec84e348822a93f7196e6cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/1643c487a7b84674a69f23ebf629e418.png
[e955028381034ffc80088475b40f6c5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/539ba0d7531e41b58508dbe3d76c80e5.png
[404dc93ad8d04aaaa122e0f953b1889e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/a14c72c8630340dda1d4cc22ce1df6bb.png
[88cc7b9c57054e30af4eecb418e6d155.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/25f663224ec94d9091be3ed438221964.png
[325ba3ce0cb647f5a8e5150701e13080.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/1319590e94934b0d861f3c350369d4c7.png
[e69418384f6b42228376ecb8d456dfd5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/c1fc3547c80b418d866ee04b6e6d74f3.png
[a2b26e51d00646d68f29717a2243cb7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/c3b53ddacd974c9386ae1357d4d06586.png
[7918a8b8082544a18011a81d6d45fbd9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/658e014539844ea9a53392b85bc40f7c.png
[27fa617f95084169874e5681d2969d21.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/6a8361616f9640659442b90db4c9d150.png
[cd4131e90b5342029db67a70fed6fd44.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/15c7f1f541b241dba27a5788d4de50a1.png
[0ae1c03c8ab14c8691d40ebbf2d36358.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/bb39b17867ee4b41a67fca00cbb3f0d2.png
[b50e51487cbb4c219cf45014bdddc261.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/aad253d29460482bb66519e6e3a98de2.png
[349d33ef80a44ce3be9ca3ea149adbc4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/bc1cf3d605f84fb8a5901477a507ae86.png
[d22733c9f2bd4d2e804560516e7fbd12.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/f7af3d4ba1334fb5940e06711ac07964.png
[9624a345963841d6994f03ad15a67fd2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/9998b990b6b0409291d54f052a136c3c.png
[5eed5680357b4b5aa944fbf203117f65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/6f577bd2eaaa4d4f99d050599c34ded1.png