5.1 树的导览
标准的STL关联式容器分为set(集合)和map(映射表)两大类,以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表)。这些容器的底层机制均以RB-tree(红黑树)完成。RB-tree也是一个独立的容器,但并不开放给外界使用。
此外,SGI STL还提供了一个不在标准规格之列的关联式容器:hash table(散列表),以及以此hash table为底层机制而完成的hash_set(散列集合)、hash_map(散列映射表)、hash_multiset(散列多键集合)、hash_multimap(散列多键映射表)。关系如下图所示:
一般而言,关联式容器的内部结构是一个平衡二叉树,以便获得良好的搜寻效率。平衡二叉树有多种类型,包括AVL-tree、RB-tree、AA-tree。其中最被广泛用于STL的是RB-tree。
有关二叉搜索树的说明参考:http://blog.csdn.net/u012243115/article/details/40779429。
二叉搜索树如下图所示:
AVL-tree是“加上了额外平衡条件”的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为O(logN)。额外平衡条件是指:任何结点的左右子树高度相差最多1。
AVL-tree树如下图所示:
AVL-tree平衡树调整的规则:如果某一个子树平衡被打破,那么根据新插入的节点的位置可以分为以下几种:(X是被打破平衡的那个子树的根节点)
1. 插入点位于X的左子节点的左子树—左左
2. 插入点位于X的左子节点的右子树—左右
3. 插入点位于X的右子节点的左子树—右左
4. 插入点位于X的右子节点的右子树—右右
对于1、4彼此对称,称为外侧插入,可以采用单旋转操作调整;对于2、3,称为内侧插入,可以采用双旋转操作。
5.2 RB-tree(红黑树)
RB-tree是另一种被广泛使用的平衡二叉搜索树,也是SGI STL唯一实现的搜寻树,作为关联式容器的底层机制之用。RB-tree的平衡条件虽然不同于AVL-tree(都是二叉搜索树),但同样运用了单旋转和双旋转修正操作。
RB-tree的规则:
1.每个节点不是红色就是黑色;
2.根节点为黑色;
3.如果节点为红,其子节点必须为黑;
4.任一节点到NULL(树尾端)的任何路径,所含黑节点数必须相同。
由规则4 => 新增节点必须为红色。规则3 => 新增节点的父节点为黑色。如果插入不满足上述要求,就需要调整RB-tree。
红黑树的结构如下图所示:
有关红黑树的说明参考:http://blog.csdn.net/u012243115/article/details/40817119。
本文介绍的RB-Tree(红黑树)是来自源码SGI STL中的文件<stl_tree.h>。
5.2.3 RB-tree的节点设计
RB-tree的节点源码剖析:
typedef bool _Rb_tree_Color_type;//节点颜色类型,非红即黑 const _Rb_tree_Color_type _S_rb_tree_red = false;//红色为0 const _Rb_tree_Color_type _S_rb_tree_black = true;//黑色为1 //RB-Tree节点基本结构 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;//指向右孩子节点 //RB-Tree最小节点,即最左节点 static _Base_ptr _S_minimum(_Base_ptr __x) { while (__x->_M_left != 0) __x = __x->_M_left; return __x; } //RB-Tree最大节点,即最右节点 static _Base_ptr _S_maximum(_Base_ptr __x) { //一直往RB-Tree的右边走,最右的节点即是最大节点 //这是二叉查找树的性质 while (__x->_M_right != 0) __x = __x->_M_right; return __x; } }; //RB-Tree节点结构 //继承节点基本结构_Rb_tree_node_base的节点信息 template <class _Value> struct _Rb_tree_node : public _Rb_tree_node_base { typedef _Rb_tree_node<_Value>* _Link_type;//节点指针,指向数据节点 _Value _M_value_field;//节点数据域,即关键字 };
5.2.4 RB-tree的迭代器
迭代器源码剖析:
//RB-Tree的迭代器iterator基本结构 //iterator迭代器的类型为双向迭代器bidirectional_iterator 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;//节点指针,连接容器 /* 重载运算符++和--;目的是找到前驱和后继节点. */ //下面只是为了实现oprerator++的,其他地方不会调用. //RB-Tree的后继节点 void _M_increment() { //the right subtree of node x is not empty //【情况1】:存在右子树,则找出右子树的最小节点 if(_M_node->_M_right != 0) {//如果有右子树 _M_node = _M_node->_M_right;//向右边走 while (_M_node->_M_left != 0)//往右子树中的左边一直走到底 _M_node = _M_node->_M_left;//最左节点就是后继结点 } //theright subtree of node x is empty,and the node of x has a successor node y //没有右子树,但是RB-Tree中节点node存在后继结点 else { _Base_ptr __y = _M_node->_M_parent;//沿其父节点上溯 while (_M_node == __y->_M_right) { //【情况2】:若节点是其父节点的右孩子,则上溯 _M_node = __y; //一直上溯,直到“某节点不是其父节点的右孩子”为止 __y = __y->_M_parent; } /* 若此时的右子节点不等于此时的父节点,此时的父节点即为解答,否则此时的node为解答. 因为SGI STL中的RB-Tree加入的header节点,所以需考虑特殊情况; 这样做是为了应付一种特殊情况:我们欲寻找根节点的下一个节点,而恰巧根节点无右孩子。 当然,以上特殊做法必须配合RB-tree根节点与特殊header之间的特殊关系 */ //以下情况3和情况4是针对header节点的使用,因为根节点和header节点是互为父节点 if (_M_node->_M_right != __y)//【情况3】:若此时的右子节点不等于此时的父节点 _M_node = __y;//此时的父节点即为解答 //【情况4】:否则此时的node为解答 } } //下面只是为了实现oprerator--的,其他地方不会调用. //RB-Tree的前驱节点 void _M_decrement() { if (_M_node->_M_color == _S_rb_tree_red &&// 如果是红节点,且 _M_node->_M_parent->_M_parent == _M_node)// 父节点的父节点等于自己 _M_node = _M_node->_M_right; //【情况1】:右子节点即为解答。 /* 以上情况发生于node为header时(亦即node为end()时)。注意,header之右孩子即 mostright,指向整棵树的max节点。 */ else if (_M_node->_M_left != 0) {//若有左孩子节点。【情况2】:左子树的最大值即为前驱节点 _Base_ptr __y = _M_node->_M_left;//向左边走,即令y指向左孩子 while (__y->_M_right != 0)//y存在右孩子, __y = __y->_M_right;//一直往右走到底 _M_node = __y;//最后即为解答 } else {//即非根节点,且没有左孩子节点,【情况3】 _Base_ptr __y = _M_node->_M_parent;//找出父节点 while (_M_node == __y->_M_left) {//node节点是其父节点的左孩子 _M_node = __y;//一直交替上溯 __y = __y->_M_parent;//直到不为左孩子结点 } _M_node = __y;//此时父节点即为解答 } } }; //RB-Tree的迭代器iterator结构 //继承基类迭代器Rb_tree_base_iterator template <class _Value, class _Ref,class _Ptr> struct _Rb_tree_iterator : public _Rb_tree_base_iterator { //迭代器的内嵌类型 typedef _Value value_type; typedef _Ref reference; typedef _Ptr pointer; typedef _Rb_tree_iterator<_Value, _Value&, _Value*> iterator; typedef _Rb_tree_iterator<_Value, const _Value&, const _Value*> const_iterator; typedef _Rb_tree_iterator<_Value, _Ref, _Ptr> _Self; typedef _Rb_tree_node<_Value>* _Link_type;//节点指针 //构造函数 _Rb_tree_iterator() {} _Rb_tree_iterator(_Link_type __x) { _M_node = __x; } _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; } /* 以下是操作符重载 */ reference operator*() const { return_Link_type(_M_node)->_M_value_field; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ //前缀operator++找出后继节点,调用基类的_M_increment() _Self& operator++() { _M_increment(); return *this; } //后缀operator++找出后继节点,调用基类的_M_increment() _Self operator++(int) { _Self __tmp = *this; _M_increment(); return__tmp; } //前缀operator--找出前驱节点,调用基类的_M_decrement() _Self& operator--() { _M_decrement(); return *this; } //后缀operator--找出前驱节点,调用基类的_M_decrement() _Self operator--(int) { _Self __tmp = *this; _M_decrement(); return __tmp; } }; //两个迭代器相等,意味着指向RB-Tree的同一个节点 inline bool operator==(const_Rb_tree_base_iterator& __x, const_Rb_tree_base_iterator& __y) { return __x._M_node == __y._M_node; } inline bool operator!=(const_Rb_tree_base_iterator& __x, const_Rb_tree_base_iterator& __y) { return __x._M_node != __y._M_node; //两个迭代器不相等,意味着所指向的节点不同 } #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION inline bidirectional_iterator_tag iterator_category(const_Rb_tree_base_iterator&) { return bidirectional_iterator_tag(); } inline_Rb_tree_base_iterator::difference_type* distance_type(const_Rb_tree_base_iterator&) { return (_Rb_tree_base_iterator::difference_type*) 0; } template <class _Value, class _Ref,class _Ptr> inline _Value* value_type(const_Rb_tree_iterator<_Value, _Ref, _Ptr>&) { return (_Value*) 0; } #endif /*__STL_CLASS_PARTIAL_SPECIALIZATION */
5.2.5 RB-tree的数据结构
//RB-Tree类的定义,继承基类_Rb_tree_base 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; protected: typedef _Rb_tree_node_base* _Base_ptr; typedef _Rb_tree_node<_Value> _Rb_tree_node; typedef _Rb_tree_Color_type _Color_type; public: typedef _Key key_type; typedef _Value value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef _Rb_tree_node* _Link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef typename _Base::allocator_type allocator_type; allocator_type get_allocator() const { return _Base::get_allocator(); } protected: #ifdef __STL_USE_NAMESPACES using _Base::_M_get_node; using _Base::_M_put_node; using _Base::_M_header;//这里是指向根节点的节点指针 #endif /* __STL_USE_NAMESPACES */ protected: //创建节点并对其初始化为x _Link_type _M_create_node(constvalue_type& __x) { _Link_type __tmp = _M_get_node();//分配一个节点空间 __STL_TRY { construct(&__tmp->_M_value_field, __x);//构造对象 } __STL_UNWIND(_M_put_node(__tmp)); return __tmp; } //复制节点的值和颜色 _Link_type _M_clone_node(_Link_type __x) { _Link_type __tmp = _M_create_node(__x->_M_value_field); __tmp->_M_color = __x->_M_color; __tmp->_M_left = 0; __tmp->_M_right = 0; return __tmp; } //释放节点 void destroy_node(_Link_type __p) { destroy(&__p->_M_value_field);//析构对象 _M_put_node(__p);//释放节点空间 } protected: size_type _M_node_count; // keeps track of size of tree _Compare_M_key_compare; //节点键值比较准则 //下面三个函数是用来获取header的成员 _Link_type& _M_root() const {return (_Link_type&) _M_header->_M_parent; } _Link_type& _M_leftmost() const {return (_Link_type&) _M_header->_M_left; } _Link_type& _M_rightmost() const {return (_Link_type&) _M_header->_M_right; } //下面六个函数获取节点x的成员 static _Link_type& _S_left(_Link_type __x) {return (_Link_type&)(__x->_M_left); } static _Link_type& _S_right(_Link_type __x) {return (_Link_type&)(__x->_M_right); } static _Link_type& _S_parent(_Link_type__x) {return (_Link_type&)(__x->_M_parent); } static reference _S_value(_Link_type __x) {return __x->_M_value_field; } static const _Key& _S_key(_Link_type __x) {return _KeyOfValue()(_S_value(__x)); } static _Color_type& _S_color(_Link_type __x) {return (_Color_type&)(__x->_M_color); } //跟上面六个函数功能相同,不同的是参数类型不同,一个是基类指针,一个是派生类指针 static _Link_type& _S_left(_Base_ptr __x) {return (_Link_type&)(__x->_M_left); } static _Link_type& _S_right(_Base_ptr __x) {return (_Link_type&)(__x->_M_right); } static _Link_type& _S_parent(_Base_ptr __x) {return (_Link_type&)(__x->_M_parent); } static reference _S_value(_Base_ptr __x) {return ((_Link_type)__x)->_M_value_field; } static const _Key& _S_key(_Base_ptr __x) {return _KeyOfValue()(_S_value(_Link_type(__x)));} static_Color_type& _S_color(_Base_ptr __x) {return (_Color_type&)(_Link_type(__x)->_M_color); } //RB-Tree的极小值 static _Link_type _S_minimum(_Link_type __x) {return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); } //RB-Tree的极大值 static _Link_type _S_maximum(_Link_type __x) {return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
……未完待续