【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;elseparentParent->_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;elseparentParent->_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;}
}本文到这就结束啦~感谢支持！