一、红黑树的迭代器
红黑树的遍历默认为中序遍历 —— key 从小到大，因此 begin() 应该获取到红黑树的最左节点 —— 最小，end() 获取到红黑树最右节点的下一个位置， operator++() 也应保证红黑树的遍历为中序的状态。
首先对红黑树节点进行改造：
引入一个模板参数 T ，使 RBTreeNode / RBTree 成为一个可以自动推演类型的容器，当我们向 RBTree 中传 key 时，封装 set 容器；向 RBTree 中传 pair<key, value> 时，封装 map 容器。
1.1 定义红黑树的迭代器：
template<class T, class Ref, class Ptr> // 与 list 迭代器处没有区别，Ref —— T& ，Ptr —— T* struct RBTreeIterator { typedef RBTreeNode<T> Node; typedef RBTreeNodeIterator<T， Ref, Ptr> Self; Node* _node; RBTreeIterator(Node* node) :_node(node) {} };
1.2 红黑树 operator++()
请务必记住：红黑树迭代器 ++ 为中序遍历 —— 左子树 — 根 — 右子树 ！
假设 cur —— 迭代器 已经走到了 key 为 8 的节点 位置，这代表着 key 为 8 的节点 的左子树已经遍历过了，若 key 为 8 的节点 的右子树不为空，则中序遍历 key 为 8 的节点 的右子树。
iterator operator++() { if (_node == nullptr) // 空树，直接返回 空 的迭代器 { return iterator(nullptr); } if (_node->_right) { Node* subLeft = _node->_right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } return *this; }
经过 operator++() 后，cur 到了 key 为 11 的节点 位置，此时 cur->_right 为空，表明以 key 为 11 的节点 为最右节点的子树已经全部遍历过，要去找从根到当前节点的简单路径中，cur 所在子树 为 左子树 的最近祖宗节点。
iterator operator++() { // ... if (_node->_right) { //... } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur != parent->_left) // parent 存在 且 cur所在子树不是parent的左子树时 { cur = parent; parent = cur->_parent; } _node = parent; } return *this; }
总结：
- 迭代器指向节点的右子树不为空时， operator++() 的下一个位置就是其右子树的最左节点。
- 迭代器指向节点的右子树为空，意味当前节点所在的左子树已经全部访问完了，operator++() 的下一个位置是当前子树为左子树的最近祖宗节点。
1.3 operator*()
Ref operator*() { return _node->_data; }
1.4 operator->()
Ptr operator->() { return &(_node->_data); }
二、改造红黑树
在对红黑树进行修改之前，首先得明确：
- 老版本 Node（RBTreeNode） 的 data 类型是 pair<K, V>，我们通常把 K 当做键值，进而实现节点的查找、map::value 的修改等功能。
- 改造 Node 的目的是我们对模板参数 T 传 key 时，则编译器封装出 set 容器；对 T 传 pair<K, V> 时，则封装 map 容器。以此减少冗余代码。
为了避免与 STL 中的 map 和 set 冲突，请在自己定义的命名空间内实现！
2.1 初步改造红黑树
template<class K, class T> class RBTree { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, T&, T*> iterator; typedef RBTreeIterator<T, const T&, const T*> const_iterator; private: Node* _root; };
2.2 初步搭建 map 和 set 的框架
map:
template<class K, class V> class map { typedef RBTree<K, pair<const K, V>>::iterator iterator; typedef RBTree<K, pair<const K, const V>>::const_iterator const_iterator; private: RBTree<K, pair<const K, V>> _t; // 加上 const ，保证 key 是无法被修改的 };
set:
template<class K> class set { typedef RBTree<K, const K>::iterator iterator; typedef RBTree<K, const K>::const_iterator const_iterator; private: RBTree<K, const K> _t; // set 中的节点不能被修改 }
无论是 map 还是 set 中，都存着两个 key ： K 和 const K / pair<const K, V> ，前者作为键值，用于查找；后者则是我们存入 Node 中的数据 —— 对应于 Node 的模板参数 T ，编译器会根据我们传入的数据类型生成对应类型的节点 。
注意容器内部树的类型要与 typedef 的迭代器类型保持一致，否则编译阶段会报错 —— 比如：在某些地方会出现 const 权限放大的问题。
2.3 引入仿函数 KeyOfT
我们再看一眼，旧版本的
RBTree::Insert()：
第一，写死的 const pair<K, V> kv 显然已经不合时宜；
第二，如果 T 的类型是 pair ，我们可以通过 cur->_data.first （新版 Node 已将 _kv 修改为 _data）取到 key 进行比较，若 T 的类型是 int ，则整个程序必然出现问题。
因此，我们需要引入一个仿函数 KeyOfT ，用于从节点的 _data 中取到相应的键值，进而完成一系列操作。
- 在 map 和 set 中封装仿函数 KeyOfT
// map: template<class K, class V> class map { typedef RBTree<K, pair<const K, V>, KeyOfT>::iterator iterator; typedef RBTree<K, pair<const K, const V>, KeyOfT>::const_iterator const_iterator; public: struct KeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; private: RBTree<K, pair<const K, V>, KeyOfT> _t; // 加上 const ，保证 key 是无法被修改的 }; // set: template<class K> class set { typedef RBTree<K, const K, KeyOfT>::iterator iterator; typedef RBTree<K, const K, KeyOfT>::const_iterator const_iterator; public: struct KeyOfT { const K& operator()(const K& k) { return k; } }; private: RBTree<K, const K, KeyOfT> _t; // set 中的节点不能被修改 }
同时我们要为 RBTree 增加一个接受仿函数的模板参数。
template<class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, T&, T*> iterator; typedef RBTreeIterator<T, const T&, const T*> const_iterator; private: Node* _root; };
- 改造 RBTree::Insert()
pair<iterator, bool> Insert(const T& data) { if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; // 默认构造节点为红色，根据红黑树的性质，我们应把根节点修改为黑色 return make_pair(iterator(root), true); } Node* cur = _root; Node* parent = nullptr; KeyOfT kot; // 仿函数变量，用于获取 data 中的键值 while (cur) { if (kot(cur->_data) > kot(data)) // 利用仿函数 kot 获取键值 { parent = cur; cur = cur->_left; } else if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else // 红黑树中已经存在一个要插入键值的节点 { return make_pair(iterator(cur), true); // 返回当前节点所在的迭代器，并 return false } } Node* newnode = cur; // 保存当前节点的位置，防止旋转导致 cur 指向其他节点而出现错误 if (kot(parent->_data) > kot(cur->_data)) { parent->_left = cur; } else { parent->_right = cur; } // 旋转的一系列过程 // ... // 与普通红黑树无异，前面的文章已提到，这里不再赘述 _root->_col = BLACK; // 把根节点修改为黑色 return make_pair(iterator(newnode), true); }
2.4 改造 Find() ，增加 begin() end()
- Find()
iterator Find(const K& key) { if (_root == nullptr) { return iterator(nullptr); // 空树，返回空迭代器 } Node* cur = _root; Node* parent = nullptr; KeyOfT kot; // 仿函数变量，用于获取 data 中的键值 while (cur) { if (kot(cur->_data) > kot(data)) // 利用仿函数 kot 获取键值 { parent = cur; cur = cur->_left; } else if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else // 找到了 { return iterator(cur); } } return iterator(nullptr); }
其实没有必要写 if (_root == nullptr) 这一语句，如果 _root 为空，cur 自然也为空，不会进入 while 循环，最终还是 return iterator(nullptr) ；为了代码的逻辑性，还是加上。
- begin()
iterator begin() { if (_root == nullptr) { return iterator(nullptr); } Node* subLeft = _root; while (subLeft->_left) { subLeft = subLeft->_left; // 找红黑树的最左节点 } return iterator(subLeft); } const_iterator begin() const { if (_root == nullptr) { return iterator(nullptr); } Node* subLeft = _root; while (subLeft->_left) { subLeft = subLeft->_left; // 找红黑树的最左节点 } return iterator(subLeft); }
- end()
iterator end() { return iterator(nullptr); } const_iterator end() const { return iterator(nullptr); }
三、实现 map
3.1 对简单接口进行包装
template<class K, class V> class map { typedef RBTree<K, pair<const K, V>, KeyOfT>::iterator iterator; typedef RBTree<K, pair<const K, const V>, KeyOfT>::const_iterator const_iterator; public: struct KeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; iterator begin() // 封装 begin() { return _t.begin(); } iterator end() // end() { return _t.end(); } iterator find(const K& key) // find() { return _t.Find(key); } pair<iterator, bool> insert(const pair<K, V>& kv) // insert() { return _t.Insert(kv); } private: RBTree<K, pair<const K, V>, KeyOfT> _t; // 加上 const ，保证 key 是无法被修改的 };
3.2 operator[]
在前面的文章中，我们讲到过 operator[] 和 insert() 的关系。
同样，我们也要通过 insert() 实现 operator[] 接口。
V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); return ret.first->second; }
解释一下 ret.first->second ：
- ret.first 取到 pair 中的迭代器
- ret.first->second 全写为 ret.first->->second
第一个 -> 为 operator->() ，return &(_node->_data) ；
第二个 -> 为 (&_data)->second 。
编译器把两个 -> 简化为一个 —— 显式写两个反而会报错。
四、实现 set
与实现 map 基本一致，这里便不再重复了。
template<class K> class set { public: struct KeyOfT { const K operator()(const K& data) { return data; } }; typedef typename RBTree<K, const K, KeyOfT>::iterator iterator; typedef typename RBTree<K, const K, KeyOfT>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } iterator find(const K& key) { return _t.Find(key); } pair<iterator, bool> insert(const K& key) { return _t.Insert(key); } private: RBTree<K, const K, KeyOfT> _t; };
