【C++】STL——用一颗红黑树封装出map和set

这篇具有很好参考价值的文章主要介绍了【C++】STL——用一颗红黑树封装出map和set。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

用一颗红黑树封装出map和set

【C++】STL——用一颗红黑树封装出map和set

一、前言

我们都知道set是K模型的容器,而map是KV模型的容器,但是它俩的底层都是用红黑树实现的,上篇博文中我们模拟实现了一颗红黑树,接下来将对其进行改造,继而用一颗红黑树封装出map和set。本质上map和set其内部的主要功能都是套用了红黑树现成的接口,只是稍作改动即可


二、红黑树模板参数的控制

既然set是K模型,map是KV模型,正如stl库里的map和set,如图所示:

【C++】STL——用一颗红黑树封装出map和set

我们发现map和set都是复用的同一颗红黑树,并且实现的都是Key_value模型。

优势:两个容器都可以复用同一颗红黑树,体现泛型编程的好处。

【C++】STL——用一颗红黑树封装出map和set

通过这里就能够很清晰的看出库里的节点的存储类型是根据set和map的第二个模板参数决定的,第二个参数存的是什么,节点存的就是什么类型,继而可以满足set和map的需求,而现在又可能引发一个新的问题:

  • 既然数据类型看第二个模板参数,那第一个模板参数有何用处?

因为在红黑树中,无可避免会要求实现find等对K有需求的函数,因为find函数主要是通过Key进行查找的,如若省略第一个模板参数,那么map就无法进行find查找操作

【C++】STL——用一颗红黑树封装出map和set

接下来,我们按照库里红黑树的样子对我们自己写的进行一个调整:

//节点类
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)
	{}
};

对红黑树的模板参数修改好了,那么我map(KV模型)和set(K模型)自然而然就能够适配了:

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

三、模板参数中仿函数的增加

由于现在红黑树的节点类型是T,当容器为set时,T就是键值Key,可以直接进行比较,当容器是map时,T就是pair<Key, Value>,此时不能直接比较,而需要从此键值对中取出Key,再拿Key进行大小比较。但是库里面pair比较大小的方式并不是我们想要的,并且map和set想要比较的数据是不同的。有的同学可能会说,这里我们再写一个比较函数,这是不行的,会和库里面函数冲突。

【C++】STL——用一颗红黑树封装出map和set

为了解决这一点,我们可以在红黑树的模板参数上再加一层仿函数,此参数专门用于获得Key类型,而这个仿函数的实现是在map和set内部封装的,通过仿函数,直接从红黑树的节点中取出想要的Key。

注意:map和set需要比较的数据为Key值,但是map和set的结构不同,所以需要在map和set类中实现不同的仿函数。

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

具体操作如下:

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

下面画图演示具体的调用情况:

【C++】STL——用一颗红黑树封装出map和set


四、红黑树正向迭代器的实现

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

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

	Node* _node; //正向迭代器所封装结点的指针
};

而在其内部,我们要完成如下操作:

  • 1、构造函数
  • 2、*和->运算符重载
  • 3、!=和==运算符重载
  • 4、++运算符重载
  • 5、–运算符重载

接下来具体展开演示:

  • 1、构造函数

构造函数我们直接通过一个节点的指针从而构造一个正向迭代器即可。

//构造函数
__TreeIterator(Node* node)
	:_node(node) //根据所给结点指针构造一个正向迭代器
{}
  • 2、*和->运算符重载

*运算符就是解引用,直接返回对应节点数据的引用即可;而->运算符返回的是对应节点数据的指针。

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

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

注意:这里operator->和list中实现是一样的,返回的是地址的原因是连续访问,编译器会把连续的operator->->优化成operator->.

  • 3、!=和==运算符重载

!=运算符直接返回两个节点是否不同,而==运算符直接返回两个节点是否相同即可。

//判断两个正向迭代器是否不同
bool operator!=(const Self& s) const
{
	return _node != s._node; //判断两个正向迭代器所封装的结点是否是同一个
}
//判断两个正向迭代器是否相同
bool operator==(const Self& s) const
{
	return _node == s._node; //判断两个正向迭代器所封装的结点是否是同一个
}
  • 4、++运算符重载

++运算符又分前置++和后置++

【C++】STL——用一颗红黑树封装出map和set

  • 前置++:

首先,这里红黑树迭代器里的++后的值应该是按此位置开始往后中序遍历的下一个。而这个下一个节点的值理应比原先的大,想要找到这个位置,结合二叉搜索树的性质,理应在右子树当中去寻找,而这又要看右子树是否为空,具体操作如下:

  • 1、右子树非空:直接遍历找到右子树的最左节点即可
  • 2、右子树为空:找祖先里面孩子是父亲左的那个祖先节点,否则继续往上找,直到为空(nullptr)
  • 3、当parent遍历到空时,++结束
  • 4、注意前置++返回的是++后的值
//前置++
Self& operator++()
{
	if (_node->_right) // 右子树不为空
	{
		// 找右子树的最左节点,使得_node指向此节点
		Node* rightmin = _node->_right;
		while (rightmin != nullptr)
		{
			rightmin = rightmin->_left;
		}
		// 最左节点为空
		_node = rightmin;
	}
	else  //_node->_right == nullptr
	{
		// 找祖先中,孩子是父亲左的那个祖先
		Node* cur = _node;
		Node* parent = cur->_parent;
		// cur为父亲的左或者父亲为空停止
		while (parent && cur == parent->_right)
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}
  • 后置++:

后置++和前置++的唯一区别就在于后置++是返回++前的值,这里只需要在前置++的基础上在一开始把当前节点保存起来,直接调用前置++,最后返回保存的那个节点值即可。

//后置++
Self operator++(int)
{
	Self tmp(*this);
	return tmp;
}

找孩子是祖先的左的那个祖先节点,这样就实现了非递归,这种非递归的前提是必须为三叉链结构

  • 5、–运算符重载

–运算符又分为前置–和后置–,下面分别讨论:

  • 前置–:

–运算符和++运算符相反,–运算符是找比当前位置次小的节点而这个节点,而这又要优先去左子树里寻找,而左子树又分为如下两种情况:

  • 左子树为空:找祖先里面孩子是父亲右的那个节点
  • 左子树非空:找左子树里最右的节点
//前置--
Self& operator--()
{
	if (_node->_left) // 左子树不为空
	{
			// 找左子树的最右节点,使得_node指向此节点
		Node* leftmax = _node->_left;
		while (leftmax != nullptr)
		{
			leftmax = leftmax->_right;
		}

					_node = leftmax;
	}
	else // 左子树为空
	{
		//找祖先中,孩子是父亲右的那个祖先
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (cur && cur == parent->_left)
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		_node = parent;
	}

	return *this;
}
  • 后置–:

注意后置–返回的是–前的值,所以先定义tmp把*this保存起来,再套用前置–函数进行自减,最后返回tmp。

//后置--
Self operator--(int)
{
	Self tmp(*this);
	return tmp;
}

五、红黑树的反向迭代器的实现

红黑树的反向迭代器实际上就是正向迭代器的一个封装,因此红黑树的反向迭代器就是一个迭代器适配器

在反向迭代器当中只有一个成员变量,那就是反向迭代器封装的正向迭代器。反向迭代器的中成员函数,都是通过调用正向迭代器对应的函数来完成相应功能的。

//反向迭代器---迭代器适配器
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; //调用正向迭代器的operator!=
	}
	bool operator==(const Self& s) const
	{
		return _it == s._it; //调用正向迭代器的operator==
	}
};

需要注意的是,反向迭代器只接收了一个模板参数,即正向迭代器的类型,也就是说,反向迭代器不知道结点的引用类型和结点的指针类型,因此我们需要在正向迭代器当中对这两个类型进行typedef,这样反向迭代器才能通过正向迭代器获取结点的引用类型和结点的指针类型。

//正向迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef Ref reference; //结点指针的引用
	typedef Ptr pointer; //结点指针
};

六、红黑树的begin()和end()

迭代器实现后,我们需要在红黑树的实现当中进行迭代器类型的typedef。需要注意的是,为了让外部能够使用typedef后的正向迭代器类型iterator,我们需要在红黑树的public区域进行typedef。

template <class K, class T, class KeyOfT>
class RBTree
{    
public:
	typedef __RBTreeIterator<T, T&, T*> iterator;//普通迭代器
	typedef __RBTreeIterator<T, const T&, const T*> const_iterator;//const迭代器
}

其实,STL中的红黑树的底层是有一个哨兵位头结点的,如下所示:

【C++】STL——用一颗红黑树封装出map和set

STL明确规定,begin()与end()代表的是一段前闭后开的区间,而对红黑树进行中序遍历后,可以得到一个有序的序列,因此:begin()可以放在红黑树中最小节点(即最左侧节点)的位置,end()放在最大节点(最右侧节点)的下一个位置,关键是最大节点的下一个位置在哪块?能否给成nullptr呢?答案是行不通的,因为对end()位置的迭代器进行–操作,必须要能找最后一个元素,此处就不行,因此最好的方式是将end()放在头结点的位置。

虽说库里的红黑树实现的是带哨兵位头节点的,但毕竟咱这是模拟(但求大概),综上begin()和end()的指向如下总结:

  • begin():指向红黑树中最小节点(即最左侧节点)的位置
  • end():指向红黑树中最大节点(最右侧节点)的下一个位置,即nullptr
//begin()
iterator begin()//找最左节点
{
	Node* subLeft = _root;
	while (subLeft && subLeft->_left)
	{
		subLeft = subLeft->_left;
	}
	return iterator(subLeft);//调用迭代器的构造函数
}
//end()
iterator end()//返回最右节点的下一个
{
	return iterator(nullptr);
}

当然这里最好再实现一个const版本的begin()和end(),为的是普通迭代器和const迭代器都能够使用,其实主要还是set的迭代器不能被修改,无论是普通迭代器还是const迭代器,其内部都是用const迭代器封装的,因此必须实现一个const版本的begin()和end()。

//begin() 
const_iterator begin() const//找最左节点
{
	Node* subLeft = _root;
	while (subLeft && subLeft->_left)
	{
		subLeft = subLeft->_left;
	}
	return const_iterator(subLeft);//调用迭代器的构造函数
}
//end()
const_iterator end() const//返回最右节点的下一个
{
	return const_iterator(nullptr);
}

如果 map/set 中想使用红黑树中的迭代器,我们需要在 map/set 中进行声明。

声明如下:

如果想取一个类模板中的一个类型,要使用 typedname 进行声明,告诉编译器这是一个类型,并不是一个静态变量

//如果想取一个类模板中的一个类型,要使用 typedname 进行声明。
//告诉编译器这是一个类型,并不是一个静态变量
typedef typename RBTree<K, pair<K, V>, MapKeyOfvalue>::iterator iterator;

注意:typename受限定符限制,尽量放在public下


七、红黑树的rbegin()和rend()

  • rbegin函数返回中序序列当中最后一个结点的反向迭代器,即最右结点。
  • rend函数返回中序序列当中第一个结点前一个位置的反向迭代器,这里直接用空指针构造一个反向迭代器。
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node; //结点的类型
public:
	typedef ReverseIterator<iterator> reverse_iterator; //反向迭代器
	
	reverse_iterator rbegin()
	{
		//寻找最右结点
		Node* right = _root;
		while (right&&right->_right)
		{
			right = right->_right;
		}
		//返回最右结点的反向迭代器
		return reverse_iterator(iterator(right));
	}
	reverse_iterator rend()
	{
		//返回由nullptr构造得到的反向迭代器(不严谨)
		return reverse_iterator(iterator(nullptr));
	}
private:
	Node* _root; //红黑树的根结点
};

八、[ ]下标访问运算符重载

我们来看 map 的 [ ] 下标访问操作符,其中 [ ]返回的是mapped_type(pair) 类型。

【C++】STL——用一颗红黑树封装出map和set

我们便要对 map 中 insert 的返回值做出修改:

【C++】STL——用一颗红黑树封装出map和set

注意,set 中的 insert 也是返回 pair,虽然很反常,但是STL库中确实是这样书写的。

【C++】STL——用一颗红黑树封装出map和set

因为只有 set 没有 [ ] 运算符重载,所以我们 set 中不必提供该函数,只用在 map 中提供即可。

首先,我们向 map 中 insert 数据 pair;pair的第一个参数为用户传入的 key 值,第二个参数则是用户声明的第二个模板参数的默认构造函数(如果是 int,则调用 int的构造函数,如果是 string ,则默认构造 string)。

pair<iterator, bool> result = insert(make_pair(key, V()));

然后我们返回迭代器指向的 pair 数据中的second。

//result.first取出迭代器,使用->运算符重载取出data地址,访问second并返回
return result.first->second;

完整函数如下:

V& operator[](const K& key)
{
	pair<iterator, bool> result = insert(make_pair(key, V()));
	//如果存在,则插入失败
	//如果不存在,则插入数据
	//无论是否存在,都返回 second;
	return result.first->second;
}

接下来我们要对红黑树的 Insert 的返回值处进行改动,进而契合 map 的 pair 数据类型。改动有三处,这里贴图大家观察即可。

【C++】STL——用一颗红黑树封装出map和set

九、红黑树的Find查找函数

查找的规则很简单,只需要遍历节点即可,具体规则如下:

  1. 如果查询的值 > 当前节点值,遍历到右子树查询
  2. 如果查询的值 < 当前节点值,遍历到左子树查询
  3. 如果查询的值 = 当前节点值,返回当前位置的迭代器
  4. 如果循环结束,说明未查询到,返回End()
//Find查找函数
iterator 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 iterator(cur);
		}
	}
	return End();
}


十、红黑树(修改版)源码链接

链接:RBTree.h · wei/cplusplus - 码云 - 开源中国 (gitee.com)

实现好了红黑树,接下来就可以套用红黑树继而实现map和set的相关功能函数。文章来源地址https://www.toymoban.com/news/detail-414395.html


十一、set、map模拟实现代码

1.set的代码

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

	public:
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

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

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

		const_iterator begin() const
		{
			return _t.begin();
		}

		const_iterator end() const 
		{
			return _t.end();
		}

		pair<iterator, bool> insert(const K& key)
		{
			pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
				return pair<iterator, bool>(ret.first, ret.second);
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};

	void test_set()
	{
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
		set<int> s;
		for (auto e : a)
		{
			s.insert(e);
		}

		set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

2.map的代码

namespace map_realize
{
	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<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

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

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

		const_iterator begin() const
		{
			return _t.begin();
		}

		const_iterator end() const
		{
			return _t.end();
		}

		pair<iterator, bool> insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			return ret.first->second;
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};

	void test_map()
	{
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
		map<int, int> m;
		for (auto e : a)
		{
			m.insert(make_pair(e, e));
		}
		cout << endl;

		map<int, int>::iterator it = m.begin();
		while (it != m.end())
		{
			//it->first++;
			it->second++;
			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;

		map<string, int> countMap;
		string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		for (auto& e : arr)
		{
            // 1、e不在countMap中,插入pair(e, int()),然后返回次数++
			// 2、e在countMap中,返回value(次数)的引用,次数++
			countMap[e]++;
		}

		for (auto& kv : countMap)
		{
			cout << kv.first << ":" << kv.second << endl;
		}
	}
}

到了这里,关于【C++】STL——用一颗红黑树封装出map和set的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C++ 改造红黑树,封装map和set

    set是Key模型的红黑树 map是Key-Value模型的红黑树 我们之前已经把红黑树实现并测试过了 这是Key-Value模型的红黑树 RBTree.h 要想用红黑树来封装set和map,我们首先想到的是在搞一份Key模型的红黑树, 然后用Key模型红黑树来封装set,Key-Value模型红黑树封装map 但是STL库中set和map的设计却

    2024年03月17日
    浏览(50)
  • 【C++】map与set容器——红黑树底层封装

    💭STL中,容器大概可分为两种类型——序列式容器和关联式容器。在前面的系列文章中,我们已经介绍了诸多序列式容器,如:vector、list、stack、queue等,它们以序列的形式存储数据。 💭而关联式容器也是一种非常重要的容器。标准的STL关联式容器分为set(集合)和map(映

    2023年04月11日
    浏览(39)
  • C++【一棵红黑树封装 set 和 map】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎃操作环境: Visual Studio 2019 版本 16.11.17 红黑树的基本情况我们已经在上一篇文章中学习过了,本文主要研究的是红黑树的实际应用:封装实现 set 和 map ,看看如何通过一棵红黑树满足两个不同的数据结构;在正式封装之前,

    2024年02月11日
    浏览(40)
  • C++ | 红黑树以及map与set的封装

    目录 前言 一、红黑树 1、红黑树的基本概念 2、红黑树相关特性 3、红黑树结点的定义 4、红黑树的查找 5、红黑树的插入 6、二叉树的拷贝构造与析构 7、红黑树的检测 8、红黑树总结 二、map与set的封装 1、红黑树的结点 2、红黑树迭代器 3、set的封装 4、map的封装 三、源码仓库

    2024年02月14日
    浏览(37)
  • 【C++】 使用红黑树模拟实现STL中的map与set

    前面的文章我们学习了红黑树,也提到了C++STL中的map和set的底层其实就是用的红黑树来实现的(而map和set的使用我们前面也学过了)。 既然红黑树我们也学习过了,那这篇文章我们就用红黑树来简单实现一下STL中的map和set,重点是学习它的框架。 上一篇文章我们实现了红黑

    2024年02月12日
    浏览(31)
  • 【C++】使用红黑树进行封装map和set

    🌇个人主页:平凡的小苏 📚学习格言:命运给你一个低的起点,是想看你精彩的翻盘,而不是让你自甘堕落,脚下的路虽然难走,但我还能走,比起向阳而生,我更想尝试逆风翻盘 。 🛸 C++专栏 : C++内功修炼基地 家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我真

    2024年02月07日
    浏览(46)
  • 【C++】用红黑树迭代器封装map和set

    封装有点难 - . - 文章目录 前言 一、红黑树原先代码的修改 二、红黑树迭代器的实现 总结 因为我们要将红黑树封装让map和set使用,所以我们要在原来的基础上将红黑树代码进行修改,最主要的是修改模板参数,下面我们直接进入正题: 首先我们拿出STL中的源代码,看看大佬

    2024年02月06日
    浏览(42)
  • Learning C++ No.23【红黑树封装set和map】

    北京时间:2023/5/17/22:19,不知道是以前学的不够扎实,还是很久没有学习相关知识,对有的知识可以说是遗忘了许多,以该篇博客有关知识为例,我发现我对迭代器和模板的有关知识的理解还不够透彻,不知道是对以前知识的遗忘,还是现在所学确实有难度,反正导致我很懵

    2024年02月05日
    浏览(50)
  • AVL树,红黑树,红黑树封装map和set

    二叉搜索树虽可以缩短查找的效率,但如果 数据有序或接近有序二叉搜索树将退化为单支树 ,查找元素相当于在顺序表中搜索元素, 效率低下 。因此,咱们中国的邻居俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法: 当向二叉搜索树中插入

    2023年04月25日
    浏览(61)
  • 红黑树封装set和map(插入部分)

    之前我们实现了红黑树的插入的部分,本文主要介绍将之前实现的红黑树封装成map和set。我们是以学习的角度来封装容器,不用非要把库中容器所有功能都实现出来。我们主要目的是学习库中代码设计技巧和模板复用的思想。 我们在实现之前还是和以前一样去看看库中是怎么

    2024年02月07日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包