【C++取经之路】红黑树封装set

目录

前言

红黑树的结构

红黑树的结点定义

红黑树的迭代器

红黑树

封装set

前言

本文参考《STL源码剖析》中SGI STL对红黑树的结构设计，涉及到红黑树迭代器的实现等，所以在读这篇文章之前，我希望你对红黑树有一定的了解，比如在红黑树插入时的变色和旋转操作，最好自己实现过。不然这篇文章对你可能不太友好，因为本文对红黑树的结构设计较为复杂，插入时的操作细节不会在本文详细说明。说实话，封装set对其实很简单，难点在于前期的红黑树设计上，在设计上的一些细节还是很有挑战的。下面我们进入正题，一起领略写SGI STL的大佬们的风采。

红黑树的结构

在这一模块下，我们先从上帝视角来看看到底要实现出怎样的红黑树，以便我们脑海里有个认知。

其中，header节点就是一个很巧妙的设计，它与根结点互为对方的父节点，这看起来是不是挺奇怪呀？没关系。 也就是说header的父节点是_root，_root的父节点是header。同时，header的左右指针分别指向最左节点和最右结点，也就是分别指向最小值和最大值。为了与根节点_root区分，header的颜色为红色。我们在插入节点的时候需要维护指向最左和最右节点的两个指针，确保它们的正确性。不要害怕，这两个指针维护起来并不困难。后面我们再说为什么要引入header。

红黑树的结点定义

enum Color{RED, BLACK};

template <class Value>
struct RBTreeNode
{
	RBTreeNode<Value>* _left;
	RBTreeNode<Value>* _right;
	RBTreeNode<Value>* _parent;//旋转时需要访问父节点
	Color _color;//颜色
	Value _value;//数据域

	RBTreeNode(const Value& value = Value())
		:_left(nullptr), _right(nullptr), _parent(nullptr)
		,_color(RED), _value(value)
	{}
};

红黑树的迭代器

这里大家就要注意了，我们已经进入关键地带了。首先，红黑树的迭代器是双向迭代器，既要支持++，也要支持--。当然除了前进和后退操作，还有蛮多的功能需要我们实现。下面就开始吧！

template <class Value, class Ref, class Ptr>
struct RBIterator
{
	typedef RBIterator<Value, Ref, Ptr> Self;
	typedef RBTreeNode<Value> Node;
	Node* _node;
	RBIterator(Node* node) :_node(node){}
}

上面是我们实现迭代器功能的基础，我解释一下。

先解释三个模板参数，Value是数据的类型，Ref是数据类型的引用，Ptr是指向数据的指针。例如数据类型为int，Value就是int，Ref即为int&，Ptr为int*。   _node就是红黑树的节点，迭代器与红黑树之间就是靠这个节点建立起联系的。知道当前指向红黑树的哪一个结点，我们才知道下一步给去到哪。所以需要为迭代器传入红黑树的结点。

迭代器++

不管前进还是后退，迭代器依据的都是二叉搜索树的规则，再加上实现上的技巧，所谓的技巧指的就是引入的header结点。这个稍后会详细说明。现在回到迭代器的前进问题，我们知道，红黑树的遍历方式是中序遍历，因为当我们通过迭代器遍历红黑树时，得到的是有序序列。中序遍历的顺序是：左子树 根 右子树。我们要实现的迭代器的遍历方式也是按照 左子树 根 右子树 去走的。下面我结合图形来分析重点。

假设迭代器当前指向结点8，现在迭代器要往下一个结点走。

我们要时刻牢记：左子树 根 右子树 是我们要的顺序。当前迭代器指向结点8，说明以结点8为根的子树的左子树已经访问结束，根节点正在被我们访问，下一个就要去到它的右子树了。记住我们的顺序是左子树 根 右子树。

好，8的右子树不为空，我们往里走，来到结点11，此时我们能直接访问11吗？当然不能！因为以11为根节点的树的左子树我们都还没访问，怎么就轮到根呢？我们的顺序是左子树 根 右子树呀。所以此时我们往11结点的左子树走，发现11结点的左子树为空，这时我们才可以访问根节点11。那么，我们下一步是不是该往11的右子树走了？是的，一点没错！但我们往里走时发现11的右子树为空，此时说明以11为根节点的子树我们都已按照预想访问完毕。我们下一步从节点11回到节点8，也就是说从8的右子树回到节点8,说明以8为根节点的子树我们已经访问完毕，下一个节点时13……

我讲了那么多，希望你能记住，每到达一个节点，都要先考虑它的左子树，如果左子树不为空，就访问左子树，访问完左子树了才能访问根，最后访问右子树，从右子树回到根结点的那一刻，说明当前的子树全部访问完毕。知道了这一点足够了，不必去纠结上面的细节了，来，我们马上进入代码，看看它的细节，这时该纠结就纠结吧！

//因为要说的比较多，就不写注释了，我在代码下方另做解释
Self& operator++()
{
	if (_node->_right != nullptr)
	{
		Node* node = _node->_right;
		while (node->_left != nullptr)
			node = node->_left;
		_node = node;
	}
	else
	{
		Node* parent = _node->_parent;
		while (parent->_right == _node)
		{
			_node = parent;
			parent = _node->_parent;
		}

		if (_node->_right != parent)//最难理解的部分，这与红黑树的设计有关
			_node = parent;
	}
	return *this;
}

迭代器指向的当前结点已被访问，说明它的左子树也已经访问过了，就剩下右子树了。如果当前结点的右子树不为空，则进入。然后一直往左走，别回头，直到走到当前子树的最左结点。为什么？还是那句话，左子树 根 右子树。我们每到一个节点，如果它的左子树不为空，我们就不能直接访问它，要先访问它的左节点，然而，它的左节点左节点也为人父母呀，也就是说左节点也是它所在子树的根，所以我们也还不能访问，一直走到左节点为空为止。如果还是不理解的话，对照着图，按着这规则走一遍就好多了。

如果右子树为空，也就是进入了else语句里。这时我们需要做的就是往回走，边走边回头。如果一个棵树的高度较高，我们在往回走时，回头看去都是我们已经访问的结点，这就需要继续往回走。例如我们从上图的11开始往回走，走到8，回头看(看的是右边)，11我们已经访问过了，所以8继续往回走，走到13，往右一看，发现这些节点我们都还未访问，说明我们应该访问13了，访问完13我们才可以去访问往右看所看到的。记住：左子树 根 右子树。

下面解释else语句中的后两行代码

如果_node为指向header节点， 那么parent就是_root结点。此时不满足while循环的进入条件，所以不会进入循环。如果直接执行_node=parent的话，_node就是指向_root，这是不是很离谱呀？！原本_node是指向end()，即header，++了之后反而回退了。所以需要对这种情况做特殊处理。如果了解红黑树的结构的话也不难想到。

迭代器--

牢牢记住，逆着走的顺序是：右子树 根 左子树。所以，每当我们到达一个节点时，都首先要考虑这个节点是否有右节点，如果有，先访问右节点，在访问根，最后访问左节点。明白了这一点，无论是前进还是好后退，都可以游刃有余。

Self& operator--()
{
	//特殊处理——与红黑树的结构设计有关
	if (_node->_color == RED && _node == _node->_parent->_parent)
		_node = _node->_right;
	else if (_node->_left != nullptr)
	{
		Node* node = _node->_left;
		while (node->_right != nullptr)
			node = node->_right;
		_node = node;
	}
	else
	{
		Node* parent = _node->_parent;
		while (parent->_left == _node)
		{
			_node = parent;
			parent = _node->_parent;
		}
		_node = parent;
	}

	return *this;
}

在解释上述代码之前，我们先来聊一聊end()的指向。别小看这一问题哈，这里面可大有文章。

首先问大家一个问题，end()应该指向哪里？最大元素？nullptr？

如果end()指向最大元素，那么我们在使用范围for遍历传递begin当end区间时，是访问不到最大元素的，因为规定区间是左闭右开。这就很不合理，所以end()不应该指向最大元素。如果end()指向nullptr，因为红黑树的迭代器是双向迭代器，我们在--end()时就会报错——对空指针进行解引用。SGI STL的做法是将end()指向header，因为header的_rigjht指针指向的是最大节点，--end()时，很容易就可以找到最大节点。所以上述代码首先处理了这种情况。剩下的都是常规情况，就不过多解释了。下面给出红黑树迭代器的完整代码。

template <class Value, class Ref, class Ptr>
struct RBIterator
{
	typedef RBIterator<Value, Ref, Ptr> Self;
	typedef RBTreeNode<Value> Node;
	Node* _node;
	RBIterator(Node* node) :_node(node){}
	 
	Ref operator*() { return _node->_value; }
	Ptr operator->() { return &(_node->_value); }
	bool operator==(Self& self) { return _node == self._node; }
	bool operator!=(Self& self) { return _node != self._node; }

	Self& operator++()
	{
		if (_node->_right != nullptr)
		{
			Node* node = _node->_right;
			while (node->_left != nullptr)
				node = node->_left;
			_node = node;
		}
		else
		{
			Node* parent = _node->_parent;
			while (parent->_right == _node)
			{
				_node = parent;
				parent = _node->_parent;
			}

			if (_node->_right != parent)//最难理解的部分，这与红黑树的设计有关
				_node = parent;
		}
		return *this;
	}

	Self operator++(int)
	{
		Self tmp = *this;
		++(*this);
		return tmp;
	}

	Self& operator--()
	{
		//特殊处理——与红黑树的结构设计有关
		if (_node->_color == RED && _node == _node->_parent->_parent)
			_node = _node->_right;
		else if (_node->_left != nullptr)
		{
			Node* node = _node->_left;
			while (node->_right != nullptr)
				node = node->_right;
			_node = node;
		}
		else
		{
			Node* parent = _node->_parent;
			while (parent->_left == _node)
			{
				_node = parent;
				parent = _node->_parent;
			}
			_node = parent;
		}

		return *this;
	}

	Self operator--(int)
	{
		Self tmp = *this;
		--(*this);
		return tmp;
	}
};

红黑树

这里我只解释如何维护header的left和right指针，剩下的操作也都是红黑树的基本操作，不赘述了。

要维护header的left和right指针，我们只需要在插入时留意：

当新插入节点插入在parent的左边时，如果parent == header->_left，也就是说parent在新节点插入前是最小值，那么在插入新节点后就需要更新header的left。

当新插入节点插入在parent的右边时，如果parent == header->_right，也就是说parent在新节点插入之前是最大值，那么在插入新节点后就需要更新header的right。

template <class Key, class Value, class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<Value> Node;
public:
	typedef RBIterator<Value, Value&, Value*> iterator;

	RBTree() { init(); }
	pair<iterator, bool> insert(const Value& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(val);
			_root->_color = BLACK;
			_root->_parent = header;
			header->_parent = _root;
			header->_left = header->_right = _root;
			return make_pair(iterator(_root), true);
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (KeyOfValue()(val) > KeyOfValue()(cur->_value))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (KeyOfValue()(val) < KeyOfValue()(cur->_value))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}

		cur = new Node(val);
		cur->_parent = parent;
		if (KeyOfValue()(parent->_value) > KeyOfValue()(val))
		{
			parent->_left = cur;
			if (parent == header->_left)
				header->_left = cur;
		}
		else
		{
			parent->_right = cur;
			if (parent == header->_right)
				header->_right = cur;
		}

		while (parent && parent != header && parent->_color == RED)
		{
			Node* grandfather = parent->_parent;

			if (grandfather->_left == parent)
			{
				Node* unclue = grandfather->_right;
				if (unclue && unclue->_color == RED)
				{
					parent->_color = BLACK;
					unclue->_color = BLACK;
					grandfather->_color = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateRight(grandfather);
					}
					else
					{
						RotateLeft(parent);
						RotateRight(grandfather);
					}

					grandfather->_color = RED;
					parent->_color = BLACK;

					break;
				}
			}
			else
			{
				Node* unclue = grandfather->_left;
				
				if (unclue && unclue->_color == RED)
				{
					parent->_color = BLACK;
					unclue->_color = BLACK;
					grandfather->_color = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (parent == grandfather->_right)
					{
						RotateLeft(grandfather);
					}
					else
					{
						RotateRight(parent);
						RotateLeft(grandfather);
					}

					parent->_color = BLACK;
					grandfather->_color = RED;

					break;
				}
			}
		}

		_root->_color = BLACK;
		return make_pair(iterator(cur), true);
	}
	iterator begin(){ return iterator(header->_left); }
	iterator end() { return iterator(header); }
	void inorder() { _inorder(_root); cout << endl; }
	Node* Maximum(){ return header->_right;}
	Node* Minimum(){ return header->_left;}
private:
	void RotateLeft(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

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

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

		subR->_parent = parentParent;

		if (parentParent != header)
		{
			if (parentParent->_left == parent)
				parentParent->_left = subR;
			else
				parentParent->_right = subR;
		}
		else
		{
			_root = subR;
			subR->_color = BLACK;
			subR->_parent = header;
			header->_parent = subR;
		}
	}

	void RotateRight(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		Node* parentParent = parent->_parent;
		parent->_parent = subL;

		subL->_parent = parentParent;

		if (parentParent != header)
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				parentParent->_right = subL;
		}
		else
		{
			_root = subL;
			subL->_color = BLACK;
			subL->_parent = header;
			header->_parent = subL;
		}
	}

	void init()
	{
		header = new Node();
		header->_left = header;
		header->_right = header;
	}

	void _inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_inorder(root->_left);
		cout << root->_value << " ";
		_inorder(root->_right);
	}
private:
	Node* _root = nullptr;
	Node* header = nullptr;
};

封装set

set的函数基本是转调底层的红黑树。实现起来就是转调红黑树，所以我这里直接给代码了。

namespace pcz
{
	template <class Key>
	class set
	{
		struct KeyOfValue
		{
			const Key& operator()(const Key& key)
			{
				return key;
			}
		};
		typedef typename RBTree<Key, Key, KeyOfValue>::iterator iterator;
	public:
		pair < iterator, bool> insert(const Key& val)
		{
			return _rb.insert(val);
		}
		void inorder() { return _rb.inorder(); }
		Key minimum() { return _rb.Minimum()->_value; }
		Key maximum() { return _rb.Maximum()->_value; }
		iterator begin() { return _rb.begin(); }
		iterator end() { return _rb.end(); }
	private:
		RBTree<Key, Key, KeyOfValue> _rb;
	};

	void test_set()
	{
		set<int> s;
		int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15, 0 };
		for (auto val : arr)
		{
			s.insert(val);
		}
		s.inorder();

		cout << s.minimum() << endl;
		cout << s.maximum() << endl;
		cout << *s.begin() << endl;
	}
}

本文到这就结束啦~感谢支持！