一、红黑树的迭代器
红黑树的遍历默认为中序遍历 —— 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; };