【高阶数据结构】封装Map和Set

这篇具有很好参考价值的文章主要介绍了【高阶数据结构】封装Map和Set。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🌈欢迎来到数据结构专栏~~封装Map和Set


  • (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort
  • 目前状态:大三非科班啃C++中
  • 🌍博客主页:张小姐的猫~江湖背景
  • 快上车🚘,握好方向盘跟我有一起打天下嘞!
  • 送给自己的一句鸡汤🤔:
  • 🔥真正的大师永远怀着一颗学徒的心
  • 作者水平很有限,如果发现错误,可在评论区指正,感谢🙏
  • 🎉🎉欢迎持续关注!
    map find 函数封装,数据结构—流浪计划,数据结构,算法,c++

map find 函数封装,数据结构—流浪计划,数据结构,算法,c++

map find 函数封装,数据结构—流浪计划,数据结构,算法,c++

一. 红黑树源码

虽然 set 参数只有 key,但是介于 map 除了 key 还有 value;我们任然将对一棵KV模型的红黑树进行封装,

//枚举颜色
enum  Colour
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;//三叉链
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	pair<K, V> _kv;//存储键值对
	Colour _col;//节点颜色

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

template<class K, class V>
struct RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	//如果是空树,则插入节点作为root节点
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;//根节点必须是黑色
			return true; //插入成功
		}

		//按二叉搜索树的插入方法,找到待插入位置
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kv.first > cur->_kv.first)//待插入结点的key值大于当前结点的key值
			{
				//往节点的右子树走
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)//待插入结点的key值小于当前结点的key值
			{
				//往节点的左子树走
				parent = cur;
				cur = cur->_left;
			}
			else//插入的值等于当前的节点,返回失败
			{
				return false;
			}
		}

		//将节点链接到树上
		cur = new Node(kv);//构造节点 
		cur->_col = RED;

		if (kv.first < parent->_kv.first)		//判断链接左还是右?
		{
			//插入到左边
			parent->_left = cur;
			cur->_parent = parent;
		}
		else if (kv.first > parent->_kv.first)
		{
			//插入到右边
			parent->_right = cur;
			cur->_parent = parent;
		}

		//如果插入节点的父节点是红色的,则需要对红黑树进行操作
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			assert(grandfather);
			assert(grandfather->_col == BLACK);

			//关键看叔叔  ~ 判断叔叔的位置
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//情况1:uncle存在且为红  + 继续往上处理
				if (uncle && uncle->_col == RED)
				{
					//变色:p和u变黑,g变红
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else  //情况2 + 情况3:uncle不存在 + uncle存在且为黑
				{
					//情况二:单旋 + 变色
					//    g
					//  p   u
					//c            
					if (cur = parent->_left)
					{
						RotateR(grandfather);//右旋

						//颜色调整
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur == parent->_right
					{
						//情况三:左右双旋 + 变色
						//    g
						//  p   u
						//    c 
						RotateL(parent);
						RotateR(grandfather);

						//调整颜色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else  //parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				//情况1:uncle存在且为红 + 继续往上处理
				if (uncle && uncle->_col == RED)
				{
					//变色:p和u变黑,g变红
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else  //情况2 + 情况3:uncle不存在 + uncle存在且为黑
				{
					//情况二:单旋 + 变色
					//    g
					//  u   p
					//        c            
					if (cur = parent->_right)
					{
						RotateL(grandfather);//左单 旋

						//颜色调整
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur == parent->_left
					{
						//情况三:右左双旋 + 变色
						//    g
						//  u   p
						//    c 
						RotateR(parent);
						RotateL(grandfather);

						//调整颜色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;//不管什么,最后根要变黑
		return true;
	}

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

	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col == RED)
		{
			cout << "根节点不是黑色" << endl;
			return false;
		}

		// 黑色节点数量基准值
		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;

			cur = cur->_left;//以最左的路径进行
		}

		return PrevCheck(_root, 0, benchmark);
	}


private:
	bool PrevCheck(Node* root, int blackNum, int& benchmark)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			//return;
			if (benchmark == 0)
			{
				benchmark = blackNum;
				return true;
			}

			if (blackNum != benchmark)
			{
				cout << "某条黑色节点的数量不相等" << endl;
				return false;
			}
			else
			{
				return true;
			}
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}
		//检测它的父亲
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return PrevCheck(root->_left, blackNum, benchmark)
			&& PrevCheck(root->_right, blackNum, benchmark);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)//空树也是红黑树
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentParent = parent->_parent;

		//建立subRL与parent之间的联系
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		//建立parent与subR之间的联系
		subR->_left = parent;
		parent->_parent = subR;

		//建立subR与parentParent之间的联系
		if (parentParent == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
	}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentParent = parent->_parent;

		//建立subLR与parent之间的联系
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		//建立parent与subL之间的联系
		subL->_right = parent;
		parent->_parent = subL;

		//建立subL与parentParent之间的联系
		if (parentParent == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
	}

	//左右双旋
	void RotateLR(Node* parent)
	{
		RotateL(parent->_left);
		RotateR(parent);
	}

	//右左双旋
	void RotateRL(Node* parent)
	{
		RotateR(parent->_right);
		RotateL(parent);
	}

private:
	Node* _root = nullptr;
};

二. 观察源码

🥑底层RBTree的结构

RBTree是根据传的Value的值来判断是什么类型,也就是一棵泛型的RBTree,通过不同的实例化,实现出了Map和Set传Key就是Set,传pair就是Map

map find 函数封装,数据结构—流浪计划,数据结构,算法,c++

🥑底层的Key和Map

可见set传的是Key,Map传的是pair
map find 函数封装,数据结构—流浪计划,数据结构,算法,c++

二. 参数的适配

为了实现泛型RBTree,对此我们将红黑树第二个模板参数的名字改为T,让自动识别是map还是set

template<class K, class T>
struct RBTree

T模板参数可能只是键值Key,也可能是由Key和Value共同构成的键值对。如果是set容器,那么它传入底层红黑树的模板参数就是Key和Key:

template<class K>
class set
{
public//...
private:
	RBTree<K, K> _t;
};

但如果是map容器,那么它传入底层红黑树的模板参数就是Key以及Key和Value构成的键值对:

template<class K, class V>
class map
{
public:
	//...
private:
	RBTree<K, pair<K, V>> _t;
};

那么问题来了:如果只看T的判断的话,是不是可以只保留第二个模板参数呢?

1️⃣对于Insert来说确实是这样的,因为此时红黑树的第二个模板参数当中也是有键值Key的,但是Key实际上是不可以省略的!

2️⃣对于set容器来说,省略红黑树的第一个参数当然没问题,因为set传入红黑树的第二个参数与第一个参数是一样的。但是对于map容器来说就不行了,因为map容器所提供的接口当中有些是只要求给出键值Key的,比如find和erase

三. 数据的存储

红黑树的模板参数变成了K和T,那节点存的是什么呢?
看了源码得知

  • set容器:K和T都代表键值Key
  • map容器:K代表键值Key,T代表由Key和Value构成的键值对

对于set容器来说,底层红黑树结点当中存储K和T都是一样的,但是对于map容器来说,底层红黑树就只能存储T了。由于底层红黑树并不知道上层容器到底是map还是set,因此红黑树的结点当中直接存储T就行了

这样一来就可以实现泛型树了,当上层容器是set的时候,结点当中存储的是键值Key;当上层容器是map的时候,结点当中存储的就是<Key, Value>键值对

map find 函数封装,数据结构—流浪计划,数据结构,算法,c++

template<class T>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;//三叉链
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	T _data;//存储的数据
	Colour _col;//节点颜色

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

四. 仿函数的支持

那我们插入比较的时候用data去比较吗?

  • 对于set而言是Key,可以比较
  • 但是对于map是pair,那我们要取其中的first来比较,但是我们能取first吗?
  • 这个地方的data有可能是map;也有可能是set

那就只能我们自己实现一个仿函数了,如果是map那就是用于获取T当中的键值Key,当红黑树比较的时候就是仿函数去获取

仿函数,就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了

template<class K, class V>
class map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	}
private:
	RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

底层的红黑树不知道上层传的是map还是set,因此当需要进行两个结点键值的比较时,底层红黑树都会通过传入的仿函数来获取键值Key,进而进行两个结点键值的比较

set的仿函数不可缺

template<class K>
class set
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	}
private:
	RBTree<K, K, SetKeyOfT> _t;

所以set容器传入底层红黑树的就是set的仿函数,map容器传入底层红黑树的就是map的仿函数

map find 函数封装,数据结构—流浪计划,数据结构,算法,c++

//查找函数
Node* Find(const K& key)
{
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kot(data) > kot(cur->_data))//待插入结点的key值大于当前结点的key值
		{
			//往节点的右子树走
			parent = cur;
			cur = cur->_right;
		}
		else if (kot(data) < kot(cur->_data))//待插入结点的key值小于当前结点的key值
		{
			//往节点的左子树走
			parent = cur;
			cur = cur->_left;
		}
		else//插入的值等于当前的节点,返回失败
		{
			return false;
		}
	}

注意

  • 1️⃣所有进行节点键值比较的地方,均需要通过仿函数获取对应节点的键值后再进行键值的比较
  • 2️⃣map和set的底层是一棵泛型红黑树实例化而来实际上不是同一棵红黑树

五. 迭代器实现

🎨正向迭代器

红黑树的正向迭代器实际上就是对结点指针进行了封装,因此在正向迭代器当中实际上就只有一个成员变量,那就是结点的指针!

//正向迭代器
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;//节点类型
	typedef __RBTreeIterator<T, Ref, Ptr> Self;//正向迭代器类型

	Node* _node;//封装节点的指针
}

通过一个节点的指针就可以封装出迭代器!

__RBTreeIterator(Node* node)
	:_node(node)
{}

当我们对正向迭代器进行解引用操作时,我们直接返回对应结点数据的引用即可

Ref operator*()
{
	return _node->_data;//返回节点数据的引用
}

以及成员访问操作符 ->

Ptr operator->()
{
	return &_node->_data;//返回节点数据的指针
}

当然,正向迭代器当中至少还需要重载==!=运算符,实现时直接判断两个迭代器所封装的结点是否是同一个即可

bool operator!=(const Self& s) const
{
	return _node != s._node//判断两个正向迭代器所封装的结点是否是同一个
}

bool operator==(const Self& s) const
{
	return _node == s._node//同上
}

重头戏才刚刚开始!真正的难点实际上++--运算符的重载

map find 函数封装,数据结构—流浪计划,数据结构,算法,c++

一个结点的正向迭代器进行++操作后,应该根据红黑树中序遍历的序列找到当前结点的下一个结点

具体思路如下:

  1. 当前节点的右子树不为空++就是找 右子树中序的第一个(最左节点)
  2. 如果节点的右子树为空++就是找到 孩子在祖先左边的祖先
Self& operator++()
{
	if (_node->_right)
	{
		//寻找该节点右子树中的最左节点
		Node* left = _node->_right;
		while (left->_left)
		{
			left = left->_left;
		}
		_node = left;//给给变成该节点
	}
	else
	{
		//找孩子在祖先左边的祖先
		Node* parent = _node->_parent;
		Node* cur = _node;
		while (parent && cur == parent->_right) //判断parent不为空,空就崩了
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

同理, -- 的逻辑是一样的:

  1. 当前节点的左子树不为空--就是找 左子树中序的第一个(最右节点)
  2. 如果节点的左子树为空--就是找到 孩子在祖先右边的祖先
Self& operator--()
{
	if (_node->_left)//结点的左子树不为空
	{
		//寻找该节点左子树中的最右节点
		Node* right = _node->_left;
		while (right->_right)
		{
			right = right->_right;
		}
		_node = right;//给给变成该节点
	}
	else//结点的左子树为空
	{
		//找孩子在祖先右边的祖先
		Node* parent = _node->_parent;
		Node* cur = _node;
		while (parent && cur == parent->_left) //判断parent不为空,空就崩了
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

我们实现迭代器的时候会将迭代器类型进行 typedef 方便调用,完事了不要忘了迭代器还有两个成员函数 begin()end()

  • begin() 返回中序序列当中第一个结点的正向迭代器,即最左节点
  • end ()返回中序序列当中最后一个结点下一个位置的正向迭代器,这里直接用空指针构造一个正向迭代器(不严谨的处理)
template<class K, class T, class KeyOfT>
struct RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __RBTreeIterator<T, T&, T*> iterator;//正向迭代器

	iterator begin()
	{
		//寻找最左节点
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}

		//返回最左结点的正向迭代器
		return iterator(left);
	}

	iterator end()
	{
		//返回空节点的迭代器
		return iterator(nullptr);
	}
}

实际上,上述所实现的迭代器是有缺陷的,因为理论上我们对end()位置的正向迭代器进行–操作后,应该得到最后一个结点的正向迭代器,但我们实现end()时,是直接返回由nullptr构造得到的正向迭代器的,因此上述实现的代码无法完成此操作

所以我们不妨看看 C++ STL 库的实现逻辑

map find 函数封装,数据结构—流浪计划,数据结构,算法,c++库里面是采用了类似双向链表的处理,给整个红黑树造了一个哨兵位节点,该节点左边指向最小的最左节点,右边指向最大的右节点,同时还有一个非常 bug 的设计就是这里哨兵位节点 header 的红黑树头结点之间的 parent 相互指向

在该结构下,实现 begin() 时,直接用头结点的左孩子构造一个正向迭代器即可,实现 rbegin() 时,直接用头结点的右孩子构造一个反向迭代器即可,严谨的过程是先构造正向迭代器,再用正向迭代器构造反向迭代器,end() 和 rend() 此时就不需要什么 nullptr 了,直接有头结点(哨兵位)进行迭代器构造即可,这样就能完成一个逻辑完整的迭代器了

🎨反向迭代器

上面得知:反向迭代器的严谨构造过程是用正向迭代器进行封装,我们可以将

template<class Iterator>//迭代器适配器
struct ReverseIterator
{
	typedef ReverseIterator<Iterator> Self; //反向迭代器
	typedef typename Iterator::reference Ref; //指针的引用
	typedef typename Iterator::pointer Ptr; //结点指针

	Iterator _it; //反向迭代器封装的正向迭代器

	//构造函数
	ReverseIterator(Iterator it)
		:_it(it) //根据所给正向迭代器构造一个反向迭代器
	{}

	Ref operator*()
	{
		return *_it; //调用正向迭代器的operator*返回引用
	}
	
	Ptr operator->()
	{
		return _it.operator->(); //调用正向迭代器的operator->返回指针
	}

	Self& operator++() //前置++
	{
		--_it; //调用正向迭代器的前置--
		return *this;
	}
	//前置--
	Self& operator--()
	{
		++_it; //调用正向迭代器的前置++
		return *this;
	}

	bool operator!=(const Self& s) const
	{
		return _it != s._it; 
	}
	bool operator==(const Self& s) const
	{
		return _it == s._it; 
	}
};

Set的实现

都是接上红黑树的接口即可

namespace ljj
{
	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:

		//typename告诉编译器这一大坨是类型,不是静态变量
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return _t.Insert(key);//调用红黑树的insert
		}

	private:
		RBTree<K, K, SetKeyOfT> _t;
	};
}

Map的实现

map 也和 set 同理,复用红黑树的底层接口实现,此外还需要实现 [] 运算符的重载

template<class K, class V>
class map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
public:
	//typename告诉编译器这一大坨是类型,不是静态变量
	typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;

	iterator begin()
	{
		return _t.begin();
	}

	iterator end()
	{
		return _t.end();
	}

	pair<iterator, bool> insert(const pair<K, V>& kv)
	{
		return _t.Insert(kv);//调用红黑树的insert
	}

	//【】的底层调用就是Insert
	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = Insert(make_pair(K, V()));//插入成功就是当前的迭代器,失败就是之前的迭代器
		return ret.first->second;
	}
private:
	RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

红黑树的代码

//枚举颜色
enum  Colour
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;//三叉链
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//pair<K, V> _kv;//存储键值对
	T _data;
	Colour _col;//节点颜色

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

//正向迭代器
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;//节点类型
	typedef __RBTreeIterator<T, Ref, Ptr> Self;//正向迭代器类型

	Node* _node;//封装节点的指针

	__RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;//返回节点数据的引用
	}

	Ptr operator->()
	{
		return &_node->_data;//返回节点数据的指针
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node;//判断两个正向迭代器所封装的结点是否是同一个
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node;//同上
	}

	Self& operator++()
	{
		if (_node->_right)
		{
			//寻找该节点右子树中的最左节点
			Node* left = _node->_right;
			while (left->_left)
			{
				left = left->_left;
			}
			_node = left;//给给变成该节点
		}
		else
		{
			//找孩子在祖先左边的祖先
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_right) //判断parent不为空,空就崩了
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self& operator--()
	{
		if (_node->_left)//结点的左子树不为空
		{
			//寻找该节点左子树中的最右节点
			Node* right = _node->_left;
			while (right->_right)
			{
				right = right->_right;
			}
			_node = right;//给给变成该节点
		}
		else//结点的左子树为空
		{
			//找孩子在祖先右边的祖先
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_left) //判断parent不为空,空就崩了
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};


template<class K, class T, class KeyOfT>
struct RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __RBTreeIterator<T, T&, T*> iterator;//正向迭代器

	iterator begin()
	{
		//寻找最左节点
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}

		//返回最左结点的正向迭代器
		return iterator(left);
	}

	iterator end()
	{
		//返回空节点的迭代器
		return iterator(nullptr);
	}

	//如果是空树,则插入节点作为root节点
	pair<iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;//根节点必须是黑色
			return make_pair(iterator(_root), true); //插入成功
		}

		//按二叉搜索树的插入方法,找到待插入位置
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kot(data) > kot(cur->_data))//待插入结点的key值大于当前结点的key值
			{
				//往节点的右子树走
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(data) < kot(cur->_data))//待插入结点的key值小于当前结点的key值
			{
				//往节点的左子树走
				parent = cur;
				cur = cur->_left;
			}
			else//插入的值等于当前的节点,返回失败
			{
				return make_pair(iterator(cur), false);
			}
		}

		//将节点链接到树上
		cur = new Node(data);//构造节点 
		Node* newnode = cur;
		cur->_col = RED;

		if (kot(data) < kot(parent->_data))		//判断链接左还是右?
		{
			//插入到左边
			parent->_left = cur;
			cur->_parent = parent;
		}
		else if (kot(data) > kot(parent->_data))
		{
			//插入到右边
			parent->_right = cur;
			cur->_parent = parent;
		}

		//如果插入节点的父节点是红色的,则需要对红黑树进行操作
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			assert(grandfather);
			assert(grandfather->_col == BLACK);

			//关键看叔叔  ~ 判断叔叔的位置
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//情况1:uncle存在且为红  + 继续往上处理
				if (uncle && uncle->_col == RED)
				{
					//变色:p和u变黑,g变红
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else  //情况2 + 情况3:uncle不存在 + uncle存在且为黑
				{
					//情况二:单旋 + 变色
					//    g
					//  p   u
					//c            
					if (cur = parent->_left)
					{
						RotateR(grandfather);//右旋

						//颜色调整
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur == parent->_right
					{
						//情况三:左右双旋 + 变色
						//    g
						//  p   u
						//    c 
						RotateL(parent);
						RotateR(grandfather);

						//调整颜色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else  //parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				//情况1:uncle存在且为红 + 继续往上处理
				if (uncle && uncle->_col == RED)
				{
					//变色:p和u变黑,g变红
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else  //情况2 + 情况3:uncle不存在 + uncle存在且为黑
				{
					//情况二:单旋 + 变色
					//    g
					//  u   p
					//        c            
					if (cur = parent->_right)
					{
						RotateL(grandfather);//左单 旋

						//颜色调整
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur == parent->_left
					{
						//情况三:右左双旋 + 变色
						//    g
						//  u   p
						//    c 
						RotateR(parent);
						RotateL(grandfather);

						//调整颜色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;//不管什么,最后根要变黑
		return make_pair(iterator(newnode), true);
	}

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

	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col == RED)
		{
			cout << "根节点不是黑色" << endl;
			return false;
		}

		// 黑色节点数量基准值
		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;

			cur = cur->_left;//以最左的路径进行
		}

		return PrevCheck(_root, 0, benchmark);
	}


private:
	bool PrevCheck(Node* root, int blackNum, int& benchmark)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			//return;
			if (benchmark == 0)
			{
				benchmark = blackNum;
				return true;
			}

			if (blackNum != benchmark)
			{
				cout << "某条黑色节点的数量不相等" << endl;
				return false;
			}
			else
			{
				return true;
			}
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}
		//检测它的父亲
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return PrevCheck(root->_left, blackNum, benchmark)
			&& PrevCheck(root->_right, blackNum, benchmark);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)//空树也是红黑树
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentParent = parent->_parent;

		//建立subRL与parent之间的联系
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		//建立parent与subR之间的联系
		subR->_left = parent;
		parent->_parent = subR;

		//建立subR与parentParent之间的联系
		if (parentParent == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
	}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentParent = parent->_parent;

		//建立subLR与parent之间的联系
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		//建立parent与subL之间的联系
		subL->_right = parent;
		parent->_parent = subL;

		//建立subL与parentParent之间的联系
		if (parentParent == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
	}

	//左右双旋
	void RotateLR(Node* parent)
	{
		RotateL(parent->_left);
		RotateR(parent);
	}

	//右左双旋
	void RotateRL(Node* parent)
	{
		RotateR(parent->_right);
		RotateL(parent);
	}

private:
	Node* _root = nullptr;
};

📢写在最后

map find 函数封装,数据结构—流浪计划,数据结构,算法,c++文章来源地址https://www.toymoban.com/news/detail-806523.html

到了这里,关于【高阶数据结构】封装Map和Set的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包赞助服务器费用

相关文章

  • 【高阶数据结构】跳表

    【高阶数据结构】跳表

    skiplist本质上也是一种查找结构,用于解决算法中的查找问题,跟平衡搜索树和哈希表的价值是 一样的,可以作为key或者key/value的查找模型。那么相比而言它的优势是什么的呢?这么等我 们学习完它的细节实现,我们再来对比。 skiplist 是由 William Pugh 发明的,最早出现于他在

    2024年02月16日
    浏览(5)
  • 高阶数据结构 ——— 并查集

    高阶数据结构 ——— 并查集

    并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。 并查集通常用森林来表示,森林中的每棵树表示一个集合,树中的结点对应一个元素。 说明一下: 虽然利用其他数据结构也能完成不相交集合的合并及查询,但在数据量极大的情况下,其耗费的时

    2024年02月03日
    浏览(13)
  • 【高阶数据结构】——并查集

    【高阶数据结构】——并查集

    在一些应用问题中, 需要将n个不同的元素划分成一些不相交的集合。开始时,每个元素自成一个单元素集合, 然后按一定的规律将归于同一组元素的集合合并 。在此过程中要 反复用到查询某一个元素归属于那个集合的运算 。适合于描述这类问题的抽象数据类型称为 并查集

    2024年02月16日
    浏览(8)
  • 高阶数据结构 ——— 图

    高阶数据结构 ——— 图

    图的基本概念 图是由顶点集合和边的集合组成的一种数据结构,记作 G = ( V , E ) G=(V, E) G = ( V , E ) 。 有向图和无向图: 在有向图中,顶点对 x , y x, y x , y 是有序的,顶点对 x , y x, y x , y 称为顶点 x x x 到顶点 y y y 的一条边, x , y x, y x , y 和 y , x y, x y , x 是两条不同的边。 在

    2024年02月08日
    浏览(10)
  • 【高阶数据结构】B+树

    【高阶数据结构】B+树

    B+树是B树的变形,是在B树基础上优化的多路平衡搜索树,B+树的规则跟B树基本类似,但是又在B树的基础上做了一些改进优化。 一棵m阶的B+树需满足下列条件: 每个分支结点最多有m棵子树(孩子结点)。 非叶根结点至少有两棵子树,其他每个分支结点至少有「m/2]棵子树。 (前

    2024年02月21日
    浏览(9)
  • 【高阶数据结构】B树

    【高阶数据结构】B树

    种类 数据格式 时间复杂度 顺序查找 无要求 O(N) 二分查找 有序 O(log 2 N ) 二叉搜索树 无要求 O(N) 二叉平衡树(红黑树和AVL树) 无要求 O(log 2 N ) 哈希 无要求 O(1) 以上结构适合用于数据量相对不是很大,能够一次性存放在内存中,进行数据查找的场景 。如果数据量很大,比如有

    2024年02月16日
    浏览(7)
  • 高阶数据结构学习 —— 图(3)

    高阶数据结构学习 —— 图(3)

    先看一下连通图和生成树的概念 连通图。在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的,则称此图为连通图。 生成树:一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边

    2024年02月06日
    浏览(7)
  • 【高阶数据结构】哈希表详解

    【高阶数据结构】哈希表详解

    上一篇文章我们学习了STL中unordered系列容器的使用,并且提到,unordered系列容器的效率之所以比较高(尤其是查找),是因为它底层使用了哈希结构,即哈希表。 那这篇文章,我们就来学习一下哈希表 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,

    2024年02月11日
    浏览(7)
  • 【高阶数据结构】AVL树详解

    【高阶数据结构】AVL树详解

    前面对map/multimap/set/multiset进行了简单的介绍,在其文档介绍中发现。 这几个容器有个共同点是: 其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N),因此

    2024年02月12日
    浏览(10)
  • 【高阶数据结构】红黑树详解

    【高阶数据结构】红黑树详解

    这篇文章我们再来学习一种平衡搜索二叉树—— 红黑树 红黑树和AVL树都是常见的自平衡二叉搜索树,它们都可以用于高效地支持插入、删除和查找等操作。虽然它们都能够保持树的平衡性,但在不同的应用场景下,红黑树和AVL树有各自的优势和适用性。 红黑树(Red-Black Tr

    2024年02月12日
    浏览(12)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包