- 1 相关头文件
- 2 红黑树的实现
- 2.1 红黑树的节点
- 2.2 红黑树的结构
- 2.3 红黑树的迭代器
- 3 set/map/multiset/multimap与红黑树的关系
- 3.1 map
1 相关头文件
tree.h stl_tree.h map.h stl_map.h set.h stl_set.h
2 红黑树的实现
首先重温下红黑树的定义。同时满足以下条件的二叉树才可称之为红黑树:
- 所有节点非红即黑
- 根节点为红色。
- 所有叶子节点为黑色。
- 如果一个节点为红色，那么它的子节点为黑色。
- 从任意给定节点向下到达叶子节点，经过相同数量的黑色节点。
2.1 红黑树的节点
首先用bool定义了红黑树节点的两种颜色：
typedef bool _Rb_tree_Color_type; const _Rb_tree_Color_type _S_rb_tree_red = false; const _Rb_tree_Color_type _S_rb_tree_black = true;
其次定义节点，_Rb_tree_node_base定义了红黑树节点的基本结构，_Rb_tree_node在其基础上加上了数据字段_M_value_field
struct _Rb_tree_node_base { typedef _Rb_tree_Color_type _Color_type; typedef _Rb_tree_node_base* _Base_ptr; _Color_type _M_color; // 节点颜色 _Base_ptr _M_parent; // 指向父节点 _Base_ptr _M_left; // 指向左节点 _Base_ptr _M_right; // 指向右节点 } template <class _Value> struct _Rb_tree_node : public _Rb_tree_node_base { typedef _Rb_tree_node<_Value>* _Link_type; _Value _M_value_field; // 节点值 };
2.2 红黑树的结构
2.2.1 _Rb_tree_base
_Rb_tree_base定义了红黑树基本的数据结构。
从代码中看到，其模板参数中_Tp表示红黑树节点中数据部分的类型, _Alloc表示内存分配器类类型。在数据结构上，红黑树由一个根节点_M_header组成。
_M_get_node/_M_put_node分别申请和释放节点内存。
template <class _Tp, class _Alloc> struct _Rb_tree_base { typedef _Alloc allocator_type; allocator_type get_allocator() const { return allocator_type(); } _Rb_tree_base(const allocator_type&) : _M_header(0) { _M_header = _M_get_node(); } ~_Rb_tree_base() { _M_put_node(_M_header); } protected: _Rb_tree_node<_Tp>* _M_header; typedef simple_alloc<_Rb_tree_node<_Tp>, _Alloc> _Alloc_type; _Rb_tree_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); } void _M_put_node(_Rb_tree_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } };
2.2.2 _Rb_tree
_Rb_tree派生于_Rb_tree_base，在其基础上增加了红黑树增删改查等接口。
_Rb_tree中模板参数众多，且与STL源码分析--hashtable中hashtable的模板参数相似：_Key表示红黑树中key(用于搜索节点)的类型，_Value表示红黑树节点中数据字段的类型，_KeyOfValue为函数对象，用于从_Value对象中抽取出key, _Compare为函数对象类型，用于比较两个key的大小，因为红黑树中所有节点必须按key值有序放置。
_Alloc为内存分配器类型，缺省为STL默认内存分配器(见STL源码分析--内存分配器)
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) > class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc> { typedef _Rb_tree_base<_Value, _Alloc> _Base; ... }
至于_Rb_tree中的增删查改操作，可直接参考《算法导论》中相关章节，这里略过。
2.3 红黑树的迭代器
红黑树中的迭代器属于双向迭代器，既可自增1，又可自减1(见STL源码分析--iterator)
_Rb_tree_base_iterator包含了一个指向红黑树节点的指针，表示迭代器的当前位置。另外还 定义了红黑树迭代器的部分基本类型(iterator_category和difference_type)、自增自减操作
struct _Rb_tree_base_iterator { typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; typedef bidirectional_iterator_tag iterator_category; typedef ptrdiff_t difference_type; _Base_ptr _M_node; ... }
_Rb_tree_iterator重载了自增自减操作符，分别调用了基类_Rb_tree_base_iterator中的_M_increment和_M_decrement函数。
template <class _Value, class _Ref, class _Ptr> struct _Rb_tree_iterator : public _Rb_tree_base_iterator { ... _Self& operator++() { _M_increment(); return *this; } _Self operator++(int) { _Self __tmp = *this; _M_increment(); return __tmp; } _Self& operator--() { _M_decrement(); return *this; } _Self operator--(int) { _Self __tmp = *this; _M_decrement(); return __tmp; } ... }
3 set/map/multiset/multimap与红黑树的关系
set/map/multiset/multimap都包含_Rb_tree。在使用上，set/multiset只存key，没有value，map/multimap中key和value成对出现；set/map中不允许重复key存在，multiset/multimap则允许多个相同key的存在。接下来带着这些问题过下相关代码：
3.1 map
map中key的类型为_Key, value的类型为_Tp。对应的，红黑树节点中数据字段类型为pair<const _Key, _Tp>，_KeyOfValue为_Select1st<pair<const _Key, _Tp>>，印证了map中key/value成对出现的说法。
另外key的比较函数对象为less<_Key>，当左值小于右值时返回true。有了_Compare，可推断：
key1 == key2等效于! _Compare()(key1, key2) && !_Compare()(key2, key1)
key1 > key2等效于_Compare()(key2, key1)
template <class _Key, class _Tp, class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>), class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > class map; // _Key 为键值类型，_Tp为实值类型。 template <class _Key, class _Tp, class _Compare, class _Alloc> class map { public: typedef _Key key_type; // 键值类型 typedef _Tp data_type; // 数据类型 typedef _Tp mapped_type; typedef pair<const _Key, _Tp> value_type; // 元素类型(键值/实值) typedef _Compare key_compare; // 键值比较函数 ... private: // 以下定义表述类型(representation type).以map元素类型(一个pair)的第一类型， // 作为RB-tree节点的键值类型 typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, key_compare, _Alloc> _Rep_type; _Rep_type _M_t; // red-black tree representing map ... }
map的insert接口代码如下，其调用了_rb_tree::insert_unique函数，其保证了如果有同值key存在，则不插入任何节点。
pair<iterator,bool> insert(const value_type& __x) { return _M_t.insert_unique(__x); }
至于set/multiset/multimap，留给聪明的读者自行分析。
