文章/答案/技术大牛

发布

社区首页 >专栏 >【C++进阶篇】红黑树的封装（赋源码）

【C++进阶篇】红黑树的封装（赋源码）

熬夜学编程的小王

发布于 2025-05-28 00:39:18

8900

代码可运行

文章被收录于专栏：编程小王编程小王

运行总次数：0

代码可运行

红黑树逆袭：手把手拆解STL容器set/map底层引擎

一. 红黑树封装

核心思路：一颗红黑树通过泛型编程思想分别实现set和map。既然是红黑树，依然要满足红黑树和二叉搜索树的规则。

1.1 基本结构

红黑树模版结构：

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

template<class T>
struct RBTreeNode
{
	T _data;

	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	Colour _col;

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

template<class K, class T, class KeyOfT>//T是插入数据的类型
class RBTree
{
	typedef RBTreeNode<T> Node;//红黑树节点的结构
public:
private:
	Node* _root = nullptr;
};

通过模版参数T决定存储数据的类型，可能读者觉得第一个K有点冗余，它主要用于Find函数的参数，默认key值要支持比较大小，而string类型等不支持，咱们就可以使用仿函数自己来实现可以支持比较大小的仿函数。

1.1.1 插入

示例代码：

pair<Iterator,bool> Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		return make_pair(Iterator(_root,_root),true);
	}

	KeyOfT kot;
	Node* parent = nullptr;
	Node* cur = _root;
	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 make_pair(Iterator(cur, _root), false);
		}
	}

	cur = new Node(data);
	Node* newnode = cur;
	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 (grandfather->_left == parent)
		{
			//   g
			// p   u
			//
			Node* uncle = grandfather->_right;
			// uncle存在且为红
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else  // uncle不存在，或者存在且为黑
			{
				if (cur == parent->_left)
				{
					// 旋转+变色
					//    g
					//  p   u
					//c
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					// 旋转+变色
					//    g
					//  p   u
					//    c
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
		else
		{
			//	 g
			// u   p
			Node* uncle = grandfather->_left;
			// 叔叔存在且为红，-》变色即可
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				// 继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else // 叔叔不存在，或者存在且为黑
			{
				// 情况二：叔叔不存在或者存在且为黑
				// 旋转+变色
				//    g
				//  u   p
				// c
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//    g
					//  u   p
					// c
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}

				break;
			}
		}
	}

	_root->_col = BLACK;

	return make_pair(Iterator(newnode, _root), true);
}

插入数据之后不满足红黑树的规则需要进行旋转，插入的数据由上一层传递给本层，插入的逻辑与上节一致，唯一不同的是它支持插入任意数据的类型，返回值，插入成功返回pair类型数据，如果key已经存在则返回可以已经存在的迭代器和false，否则返回新插入数据的迭代器和true。使用key值比较大小时，需套一层仿函数，原因同上。

1.1.2 查找

通过key值比较，上层都会传入自己的仿函数给KeyOfT，提取键值，从而实现比较大小。返回也有讲究，为什么返回Node* 主要用于map实现修改value值的。

Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		KeyOfT kot;  
		if (kot(cur->_data) < key) 
		{
			cur = cur->_right;
		}
		else if (kot(cur->_data) > key)  
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}

1.2 迭代器(重点)

遍历红黑树，使用前序遍历。即左 - 根 - 右，begin节点为最左节点。

1.2.1 开始与结尾节点迭代器

Iterator Begin()//中序第一个是最左节点
{
	Node* cur = _root;
	while (cur && cur->_left)
	{
		cur = cur->_left;
	}

	return Iterator(cur,_root);
}

遍历至结尾，即空节点为end。

Iterator End()
{
	return Iterator(nullptr,_root);
}

const迭代器：

ConstIterator Begin()const
{
	Node* cur = _root;
	while (cur && cur->_left)
	{
		cur = cur->_left;
	}

	return ConstIterator(cur, _root);
}
ConstIterator End() const
{
	return ConstIterator(nullptr, _root);
}

1.2.2 迭代器基本结构：

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
	Node* _node;
	Node* _root;

	RBTreeIterator(Node* node, Node* root)
		:_node(node)
		, _root(root)
	{}
}

使用节点指针和根节点指针构造迭代器。

typedef RBTreeIterator<T,T&,T*> Iterator; typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

1.2.3 重载operator*()

用于取节点指针的数据。

Ref operator*()
{
	return _node->_data;
}

1.2.4 重载operator->()

用于取节点指针数据的地址。

Ptr operator->()
{
	return &_node->_data;
}

1.2.5 前置++

对节点进行++，分析场景如下：

如果当前节点的左孩子不为空，则直接找左孩子的最左节点。
如果左为空且右孩子不为空，则找右孩子的最左节点。
如果左为空，且右也为空，只需要往回找，孩子是parent节点左孩子的第一个。示例代码如下：

Self& operator++()
{
	if (_node->_right)
	{
		Node* minleft = _node->_right;
		//while (minleft->_left)
		while (minleft && minleft->_left)
		{
			minleft = minleft->_left;
		}

		_node = minleft;
	}
	else
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = parent->_parent;
		}

		_node = parent;
	}

	return *this;
}

1.2.6 operator–()

分析：

当前节点的左子树不为空，进入右子树的右孩子找最右节点。
当前节点左子树为空，需要向上回溯找孩子是父亲右的第一个节点。
上述两种场景都不会访问到最大节点，需要特殊判断。示例代码：

Self& operator--()
{
	if (_node == nullptr) // end()
	{
		// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点
		Node* rightMost = _root;
		while (rightMost && rightMost->_right)
		{
			rightMost = rightMost->_right;
		}
		_node = rightMost;
	}
	else if (_node->_left)
	{
		// 左子树不为空，中序左子树最后一个
		Node* rightMost = _node->_left;
		while (rightMost->_right)
		{
			rightMost = rightMost->_right;
		}
		_node = rightMost;
	}
	else
	{
		// 孩子是父亲右的那个祖先
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_left)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}

	return *this;
}

下面以一个具体的实例来详细说明一下这个特殊情况。

例如当前节点cur指向50，它的parent指向40，进入循环判断，parent在但cur节点不是parent的左，跳出循环，_node指向parent节点即40，未访问到50这个节点。
_node指向40，左不为空进入循环，无法进入右分支，更访问不到最大节点。
所以当_node为空时，特殊判断查找右子树的最右节点，即是最大节点。

重载operator!=()和operator==() 直接判断节点的指针是否相等即可。

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

二. 封装set/map

2.1 封装set

RBTree<K,const K,SetKeyOfT> _rbtree; 通过第二个参数，实现存储不同数据的类型。直接调用接口即可。

namespace SET
{
	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
		typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

		iterator begin()
		{
			return _rbtree.Begin();
		}
		iterator end()
		{
			return _rbtree.End();
		}

		const_iterator begin()const
		{
			return _rbtree.Begin();
		}
		const_iterator end()const
		{
			return _rbtree.End();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return _rbtree.Insert(key);
		}

		iterator find(const K& key)
		{
			return _rbtree.Find(key);
		}
	private:
		RBTree<K,const K,SetKeyOfT> _rbtree;
	};
	}

因为set的key值不允许修改，所以被const修饰。

2.2 map封装

2.2.1 map[]

map[]底层是用insert实现的。

V& operator[](const K& key)
{
	pair<iterator, bool> ret = _rbtree.Insert({ key,V() });
	return ret.first->second;
}

返回value值得引用允许修改value的值。与set类似，直接调用接口即可。

namespace MAP
{
	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>::ConstIterator const_iterator;

		iterator begin()
		{
			return _rbtree.Begin();
		}
		iterator end()
		{
			return _rbtree.End();
		}

		const_iterator begin()const
		{
			return _rbtree.Begin();
		}
		const_iterator end()const
		{
			return _rbtree.End();
		}

		pair<iterator, bool> insert(const pair<const K, V>& kv)
		{
			return _rbtree.Insert(kv);
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _rbtree.Insert({ key,V() });
			return ret.first->second;
		}
		iterator find(const K& key)
		{
			return _rbtree.Find(key);
		}
		}

源码：set/map封账-Gitee

三. 最后

本文详细阐述了基于红黑树实现STL容器set/map的核心技术。首先构建红黑树基础结构，通过模板参数支持泛型数据存储，插入操作采用红黑树平衡算法维护树结构，查找通过仿函数提取键值。迭代器重点实现中序遍历逻辑，包含边界处理及双向遍历操作符重载。在容器封装层面，set直接存储键值并限制修改，map通过键值对存储实现operator[]功能，二者均复用红黑树核心逻辑，通过模板特化与仿函数机制实现高效数据管理。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-05-25，如有侵权请联系 cloudcommunity@tencent.com 删除

函数