stl_tree.h
這是整個STL中最復雜的數據結構，也是我接觸到的最復雜的數據結構之一
/**
Red-black tree class, designed for use in implementing STL
associative containers (set, multiset, map, and multimap). The
insertion and deletion algorithms are based on those in Cormen,
Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
except that
(1) the header cell is maintained with links not only to the root
but also to the leftmost node of the tree, to enable constant time
begin(), and to the rightmost node of the tree, to enable linear time
performance when used with the generic set algorithms (set_union,
etc.);
(2) when a node being deleted has two children its successor node is
relinked into its place, rather than copied, so that the only
iterators invalidated are those referring to the deleted node.
*/
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;
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;
///尋找以x為根節點的RB樹的最小值結點
static _Base_ptr _S_minimum(_Base_ptr __x)
{
while (__x->_M_left != 0) __x = __x->_M_left;
return __x;
}
///尋找以x為根節點的RB樹的最大值結點
static _Base_ptr _S_maximum(_Base_ptr __x)
{
while (__x->_M_right != 0) __x = __x->_M_right;
return __x;
}
};
template
struct _Rb_tree_node : public _Rb_tree_node_base
{
typedef _Rb_tree_node<_Value>* _Link_type;
_Value _M_value_field;
};
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;
///找到遞增序列的後繼
void _M_increment()
{
if (_M_node->_M_right != 0) ///如果右子樹非空
{
///找到右子樹的最左端子孫結點
_M_node = _M_node->_M_right;
while (_M_node->_M_left != 0)
_M_node = _M_node->_M_left;
}
else ///右子樹為空
{
_Base_ptr __y = _M_node->_M_parent;
///沿著父節點上溯,直到其為父節點的左孩子,或者到達根節點
while (_M_node == __y->_M_right)
{
_M_node = __y;
__y = __y->_M_parent;
}
///結點的右孩子不為其父節點,則後繼即為該父節點,如果結點的右孩子為其父節點
///只有一種情況,根節點無右子樹(根節點為right_most結點),此時while循環亦會將迭
///代器指針指向end結點,因此在此處不需要再次修改迭代器指向.
if (_M_node->_M_right != __y)
_M_node = __y;
}
}
///找到遞增序列的前驅
void _M_decrement()
{
if (_M_node->_M_color == _S_rb_tree_red &&
_M_node->_M_parent->_M_parent == _M_node) ///對end迭代器進行遞減,指向最大值
_M_node = _M_node->_M_right;
else if (_M_node->_M_left != 0) ///左子樹不為空
{
///找到左子樹最右邊子孫結點
_Base_ptr __y = _M_node->_M_left;
while (__y->_M_right != 0)
__y = __y->_M_right;
_M_node = __y;
}
else ///左子樹為空
{
///沿著父節點上溯,直到其為父節點的右孩子,或者到達根節點
_Base_ptr __y = _M_node->_M_parent;
while (_M_node == __y->_M_left)
{
_M_node = __y;
__y = __y->_M_parent;
}
///找到前驅,即為其父節點
_M_node = __y;
}
}
};
template
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;
}
pointer operator->() const
{
return &(operator*());
}
_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;
}
};
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;
}
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
inline _Value* value_type(const _Rb_tree_iterator<_Value, _Ref, _Ptr>&)
{
return (_Value*) 0;
}
///將以__x為根的子樹左旋
inline void
_Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
///用__x->_M_right取代__x的位置,x取代x->_M_right的左孩子
///x->_M_right的左孩子取代x的右孩子
_Rb_tree_node_base* __y = __x->_M_right;
__x->_M_right = __y->_M_left;
if (__y->_M_left !=0)
__y->_M_left->_M_parent = __x;
__y->_M_parent = __x->_M_parent;
if (__x == __root)
__root = __y;
else if (__x == __x->_M_parent->_M_left)
__x->_M_parent->_M_left = __y;
else
__x->_M_parent->_M_right = __y;
__y->_M_left = __x;
__x->_M_parent = __y;
}
///將以__x為根的子樹右旋
inline void
_Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
///用__x->_M_left取代__x的位置,x取代x->_M_left的右孩子
///x->_M_left的右孩子取代x的左孩子
_Rb_tree_node_base* __y = __x->_M_left;
__x->_M_left = __y->_M_right;
if (__y->_M_right != 0)
__y->_M_right->_M_parent = __x;
__y->_M_parent = __x->_M_parent;
if (__x == __root)
__root = __y;
else if (__x == __x->_M_parent->_M_right)
__x->_M_parent->_M_right = __y;
else
__x->_M_parent->_M_left = __y;
__y->_M_right = __x;
__x->_M_parent = __y;
}
///插入結點x之後的調整,使其符合RB樹的定義,
///調整采用按子樹逐層上溯處理,直至整棵樹合法為止
inline void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
__x->_M_color = _S_rb_tree_red; ///新插入的結點默認為紅色
///如果是根節點,只需要最後矯正根節點顏色,如果其父節點為黑色,則無需調整.
while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red)
{
if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) ///父節點為左孩子
{
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right; ///y為其叔父結點
if (__y && __y->_M_color == _S_rb_tree_red) ///父節點和叔父結點同為紅色
{
///其祖父結點必不為紅色,因此可以直接將紅色上移至其祖父結點,
///然後將其父節點和叔父結點同時染黑,可保證自其祖父結點以下
///滿足RB樹的定義.
__x->_M_parent->_M_color = _S_rb_tree_black;
__y->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
__x = __x->_M_parent->_M_parent; ///將x指向其祖父結點,再次循環從其祖父結點開始調整
}
else ///其叔父結點為黑色
{
///此時x,x父節點均為紅色,x叔父結點為黑色
if (__x == __x->_M_parent->_M_right) ///調整,將x調整為左孩子交由後面處理
{
__x = __x->_M_parent;
_Rb_tree_rotate_left(__x, __root);
}
///此時x必為左孩子,且x,x父節點均為紅色,x叔父結點為黑色
__x->_M_parent->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);
///此時x父節點已經為黑色,可保證整棵樹符合RB樹的定義,完全可以跳出循環
}
}
else ///父節點為右孩子,和上面對稱操作
{
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
if (__y && __y->_M_color == _S_rb_tree_red)
{
__x->_M_parent->_M_color = _S_rb_tree_black;
__y->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
__x = __x->_M_parent->_M_parent;
}
else
{
if (__x == __x->_M_parent->_M_left)
{
__x = __x->_M_parent;
_Rb_tree_rotate_right(__x, __root);
}
__x->_M_parent->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
}
}
}
__root->_M_color = _S_rb_tree_black; ///調整根節點顏色
}
///刪除結點z並調整該樹,使其符合RB樹的定義
inline _Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z,
_Rb_tree_node_base*& __root,
_Rb_tree_node_base*& __leftmost,
_Rb_tree_node_base*& __rightmost)
{
_Rb_tree_node_base* __y = __z;
_Rb_tree_node_base* __x = 0;
_Rb_tree_node_base* __x_parent = 0;
if (__y->_M_left == 0) /// __z has at most one non-null child. y == z.
__x = __y->_M_right; /// __x might be null.
else if (__y->_M_right == 0) /// __z has exactly one non-null child. y == z.
__x = __y->_M_left; /// __x is not null.
else
{
///為了刪除以後方便調整,RB樹只刪除沒有孩子或只有一個孩子的結點
///如果需要刪除的結點具有雙孩子,需要找到該結點的後繼(一定無雙孩子)
///然後用後繼代替該節點,同時染上該節點的顏色,調整因此,實際刪除
///的結點永遠無雙孩子
/// __z has two non-null children. Set __y to
__y = __y->_M_right; /// __z's successor. __x might be null.
while (__y->_M_left != 0)
__y = __y->_M_left;
__x = __y->_M_right;
}
if (__y != __z) ///z具有雙孩子
{
/// relink y in place of z. y is z's successor
__z->_M_left->_M_parent = __y;
__y->_M_left = __z->_M_left;
if (__y != __z->_M_right)
{
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
__y->_M_parent->_M_left = __x; /// __y must be a child of _M_left
__y->_M_right = __z->_M_right;
__z->_M_right->_M_parent = __y;
}
else
__x_parent = __y;
if (__root == __z)
__root = __y;
else if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __y;
else
__z->_M_parent->_M_right = __y;
__y->_M_parent = __z->_M_parent;
__STD::swap(__y->_M_color, __z->_M_color);
__y = __z;
/// __y now points to node to be actually deleted
}
else /// __y == __z
{
///z不具有雙孩子
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
if (__root == __z)
__root = __x;
else if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __x;
else
__z->_M_parent->_M_right = __x;
if (__leftmost == __z)
if (__z->_M_right == 0) /// __z->_M_left must be null also
__leftmost = __z->_M_parent;
/// makes __leftmost == _M_header if __z == __root
else
__leftmost = _Rb_tree_node_base::_S_minimum(__x);
if (__rightmost == __z)
if (__z->_M_left == 0) /// __z->_M_right must be null also
__rightmost = __z->_M_parent;
/// makes __rightmost == _M_header if __z == __root
else /// __x == __z->_M_left
__rightmost = _Rb_tree_node_base::_S_maximum(__x);
}
///刪除完畢,需要調整,和rebalance一樣是按子樹逐層上溯處理,直到整棵樹合法為止
///如果為紅色結點不需要調整
if (__y->_M_color != _S_rb_tree_red)
{
///如果x是根結點或者紅色結點,只需最後調整結點顏色為黑色即可使整棵樹滿足RB樹的定義
while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
if (__x == __x_parent->_M_left)
{
///w為被刪結點的兄弟,由於刪除操作,w子樹比x子樹多一個黑結點
_Rb_tree_node_base* __w = __x_parent->_M_right;
if (__w->_M_color == _S_rb_tree_red)
{
///通過調整將w變為黑色,交由下面處理
__w->_M_color = _S_rb_tree_black;
__x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__x_parent, __root);
__w = __x_parent->_M_right;
}
///此時w一定為黑色,而且仍然比x子樹多一個黑結點
if ((__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_rb_tree_black) &&
(__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black)) ///w的兩個孩子均為黑色
{
///將w染成紅色,此時w子樹減少了一個黑結點,和x子樹黑結點數目相同
///但__x_parent子樹比其兄弟子樹少一個結點,因此令x=__x_parent,
///交由下次循環處理
__w->_M_color = _S_rb_tree_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
}
else ///w為黑色,其孩子一紅一黑或者同為紅色
{
if (__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black) ///w孩子節點左紅右黑
{
if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
__w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__w, __root);
__w = __x_parent->_M_right;
///此處w仍然為黑色,w子樹的黑結點仍然比x子樹多1,但w的孩子節點為左黑右紅,交由下面處理
}
///此時此處w一定為黑色,w子樹的黑結點一定比x子樹多1,w的右孩子節點一定為紅色
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_rb_tree_black;
if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
_Rb_tree_rotate_left(__x_parent, __root);
///至此處可保證整棵樹符合RB樹的定義
break;
}
}
else /// same as above, with _M_right <-> _M_left.
{
_Rb_tree_node_base* __w = __x_parent->_M_left;
if (__w->_M_color == _S_rb_tree_red)
{
__w->_M_color = _S_rb_tree_black;
__x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__x_parent, __root);
__w = __x_parent->_M_left;
}
if ((__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black) &&
(__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_rb_tree_black))
{
__w->_M_color = _S_rb_tree_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
}
else
{
if (__w->_M_left == 0 ||
__w->_M_left->_M_color == _S_rb_tree_black)
{
if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
__w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__w, __root);
__w = __x_parent->_M_left;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_rb_tree_black;
if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
_Rb_tree_rotate_right(__x_parent, __root);
break;
}
}
if (__x) __x->_M_color = _S_rb_tree_black;
}
return __y;
}
/// In order to avoid having an empty base class, we arbitrarily
///move one of rb_tree's data members into the base class.
template
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);
}
};
template
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:
using _Base::_M_get_node;
using _Base::_M_put_node;
using _Base::_M_header;
protected:
_Link_type _M_create_node(const value_type& __x)
{
_Link_type __tmp = _M_get_node();
try
{
construct(&__tmp->_M_value_field, __x);
}
catch(...)
{
_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;
_Link_type& _M_root() const ///_M_header和_M_root互為父節點
{
return (_Link_type&) _M_header->_M_parent;
}
_Link_type& _M_leftmost() const ///_M_header->_M_left指向最小值,即最左端結點
{
return (_Link_type&) _M_header->_M_left;
}
_Link_type& _M_rightmost() const ///_M_header->_M_right指向最大值,即最右端結點
{
return (_Link_type&) _M_header->_M_right;
}
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);
}
static _Link_type _S_minimum(_Link_type __x)
{
return (_Link_type) _Rb_tree_node_base::_S_minimum(__x);
}
static _Link_type _S_maximum(_Link_type __x)
{
return (_Link_type) _Rb_tree_node_base::_S_maximum(__x);
}
public:
typedef _Rb_tree_iterator iterator;
typedef _Rb_tree_iterator
const_iterator;
typedef reverse_bidirectional_iterator
reverse_iterator;
typedef reverse_bidirectional_iterator
const_reverse_iterator;
private:
iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
_Link_type _M_copy(_Link_type __x, _Link_type __p);
void _M_erase(_Link_type __x);
public:
/// allocation/deallocation
_Rb_tree()
: _Base(allocator_type()), _M_node_count(0), _M_key_compare()
{
_M_empty_initialize();
}
_Rb_tree(const _Compare& __comp)
: _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
{
_M_empty_initialize();
}
_Rb_tree(const _Compare& __comp, const allocator_type& __a)
: _Base(__a), _M_node_count(0), _M_key_compare(__comp)
{
_M_empty_initialize();
}
_Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) ///copy constructor
: _Base(__x.get_allocator()),
_M_node_count(0), _M_key_compare(__x._M_key_compare)
{
if (__x._M_root() == 0)
_M_empty_initialize();
else
{
_S_color(_M_header) = _S_rb_tree_red;
_M_root() = _M_copy(__x._M_root(), _M_header);
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
}
_M_node_count = __x._M_node_count;
}
~_Rb_tree()
{
clear();
}
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>&
operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x);
private:
void _M_empty_initialize() ///空樹的創建
{
_S_color(_M_header) = _S_rb_tree_red; /// used to distinguish header from
/// __root, in iterator.operator++
_M_root() = 0;
_M_leftmost() = _M_header;
_M_rightmost() = _M_header;
}
public:
/// accessors:
_Compare key_comp() const
{
return _M_key_compare;
}
iterator begin()
{
return _M_leftmost();
}
const_iterator begin() const
{
return _M_leftmost();
}
iterator end()
{
return _M_header;
}
const_iterator end() const
{
return _M_header;
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
bool empty() const
{
return _M_node_count == 0;
}
size_type size() const
{
return _M_node_count;
}
size_type max_size() const
{
return size_type(-1);
}
void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t)
{
__STD::swap(_M_header, __t._M_header);
__STD::swap(_M_node_count, __t._M_node_count);
__STD::swap(_M_key_compare, __t._M_key_compare); ///一定要交換比較函數
}
public:
/// insert/erase
pair insert_unique(const value_type& __x);
iterator insert_equal(const value_type& __x);
iterator insert_unique(iterator __position, const value_type& __x);
iterator insert_equal(iterator __position, const value_type& __x);
template
void insert_unique(_InputIterator __first, _InputIterator __last);
template
void insert_equal(_InputIterator __first, _InputIterator __last);
void erase(iterator __position);
size_type erase(const key_type& __x);
void erase(iterator __first, iterator __last);
void erase(const key_type* __first, const key_type* __last);
void clear() ///將樹清空
{
if (_M_node_count != 0)
{
_M_erase(_M_root());
_M_leftmost() = _M_header;
_M_root() = 0;
_M_rightmost() = _M_header;
_M_node_count = 0;
}
}
public:
/// set operations:
iterator find(const key_type& __x);
const_iterator find(const key_type& __x) const;
size_type count(const key_type& __x) const;
iterator lower_bound(const key_type& __x);
const_iterator lower_bound(const key_type& __x) const;
iterator upper_bound(const key_type& __x);
const_iterator upper_bound(const key_type& __x) const;
pair equal_range(const key_type& __x);
pair equal_range(const key_type& __x) const;
public:
/// Debugging.
bool __rb_verify() const;
};
template
inline bool
operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
return __x.size() == __y.size() &&
equal(__x.begin(), __x.end(), __y.begin());
}
template
inline bool
operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
return lexicographical_compare(__x.begin(), __x.end(),
__y.begin(), __y.end());
}
template
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>&
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
{
if (this != &__x)
{
/// Note that _Key may be a constant type.
clear(); ///先將需要賦值的樹清空
_M_node_count = 0;
_M_key_compare = __x._M_key_compare; ///比較函數賦值
if (__x._M_root() == 0)
{
_M_root() = 0;
_M_leftmost() = _M_header;
_M_rightmost() = _M_header;
}
else
{
_M_root() = _M_copy(__x._M_root(), _M_header); ///復制整棵樹
_M_leftmost() = _S_minimum(_M_root()); ///調整樹的狀態
_M_rightmost() = _S_maximum(_M_root());
_M_node_count = __x._M_node_count;
}
}
return *this;
}
///v為要插入的值,x為要插入的位置,y為x的父節點
template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v)
{
_Link_type __x = (_Link_type) __x_;
_Link_type __y = (_Link_type) __y_;
_Link_type __z;
if (__y == _M_header || __x != 0 ||
_M_key_compare(_KeyOfValue()(__v), _S_key(__y)))
{
__z = _M_create_node(__v);
_S_left(__y) = __z; /// also makes _M_leftmost() = __z
/// when __y == _M_header
if (__y == _M_header)
{
_M_root() = __z;
_M_rightmost() = __z;
}
else if (__y == _M_leftmost())
_M_leftmost() = __z; /// maintain _M_leftmost() pointing to min node
}
else
{
__z = _M_create_node(__v);
_S_right(__y) = __z;
if (__y == _M_rightmost())
_M_rightmost() = __z; /// maintain _M_rightmost() pointing to max node
}
_S_parent(__z) = __y;
_S_left(__z) = 0;
_S_right(__z) = 0;
_Rb_tree_rebalance(__z, _M_header->_M_parent);
++_M_node_count;
return iterator(__z);
}
template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::insert_equal(const _Value& __v) ///鍵值可重復插入
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
while (__x != 0) ///尋找合適的插入點(一定為0),同時記錄插入點的父節點
{
__y = __x;
__x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
_S_left(__x) : _S_right(__x);
}
return _M_insert(__x, __y, __v);
}
template
pair::iterator,
bool>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::insert_unique(const _Value& __v) ///鍵值不可重復插入,插入可能失敗
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
bool __comp = true;
while (__x != 0) ///尋找可能的插入位置
{
__y = __x;
__comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
///v小於x的鍵值時向左子樹移動,否則向右子樹移動,因此,如果已有重復
///鍵值存在,x最終一定位於重復鍵值所在節點的右子樹
__x = __comp ? _S_left(__x) : _S_right(__x);
}
///檢查是否可以插入(鍵值是否有重復)
iterator __j = iterator(__y);
if (__comp) ///插入點是其父節點的左孩子
if (__j == begin())
{
///最左端結點,不可能位於某個節點的右子樹,因此可判定無重復鍵值,可插入
return pair(_M_insert(__x, __y, __v), true);
}
else
{
--__j; ///得到其父節點的直接前驅結點,若插入x,即成為x的直接前驅結點
}
///此時,j為若插入x後x的直接前驅結點.
if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
return pair(_M_insert(__x, __y, __v), true);
return pair(__j, false);
}
///不可重復插入,先在指定位置插入,若指定位置插入不合法,
///再試圖尋找合法位置插入
template
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>
::insert_unique(iterator __position, const _Val& __v)
{
if (__position._M_node == _M_header->_M_left) /// begin()
{
if (size() > 0 &&
_M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
{
/// first argument just needs to be non-null
return _M_insert(__position._M_node, __position._M_node, __v);
}
else
{
return insert_unique(__v).first;
}
}
else if (__position._M_node == _M_header) /// end()
{
if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
return _M_insert(0, _M_rightmost(), __v);
else
return insert_unique(__v).first;
}
else
{
iterator __before = __position;
--__before; ///找到插入位置的直接前驅
if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v))
&& _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)))
{
if (_S_right(__before._M_node) == 0)
return _M_insert(0, __before._M_node, __v);
else
return _M_insert(__position._M_node, __position._M_node, __v);
/// first argument just needs to be non-null
}
else
return insert_unique(__v).first;
}
}
template
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>
::insert_equal(iterator __position, const _Val& __v)
{
if (__position._M_node == _M_header->_M_left) /// begin()
{
if (size() > 0 &&
!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
return _M_insert(__position._M_node, __position._M_node, __v);
/// first argument just needs to be non-null
else
return insert_equal(__v);
}
else if (__position._M_node == _M_header) /// end()
{
if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
return _M_insert(0, _M_rightmost(), __v);
else
return insert_equal(__v);
}
else
{
iterator __before = __position;
--__before;
if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
&& !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
{
if (_S_right(__before._M_node) == 0)
return _M_insert(0, __before._M_node, __v);
else
return _M_insert(__position._M_node, __position._M_node, __v);
/// first argument just needs to be non-null
}
else
return insert_equal(__v);
}
}
template
template
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_equal(_II __first, _II __last)
{
for ( ; __first != __last; ++__first)
insert_equal(*__first);
}
template
template
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_unique(_II __first, _II __last)
{
for ( ; __first != __last; ++__first)
insert_unique(*__first);
}
template
inline void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::erase(iterator __position)
{
_Link_type __y =
(_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
_M_header->_M_parent,
_M_header->_M_left,
_M_header->_M_right);
destroy_node(__y);
--_M_node_count;
}
template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
{
pair __p = equal_range(__x);
size_type __n = 0;
distance(__p.first, __p.second, __n);
erase(__p.first, __p.second);
return __n;
}
///復制以__x作為根節點的子樹,得到的樹作為__p的子樹
template
typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
_Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>
::_M_copy(_Link_type __x, _Link_type __p)
{
///整棵樹所有的右子樹都遞歸復制,所有的左子樹都直接復制
/// structural copy. __x and __p must be non-null.
_Link_type __top = _M_clone_node(__x);
__top->_M_parent = __p;
try
{
if (__x->_M_right)
__top->_M_right = _M_copy(_S_right(__x), __top); ///遞歸復制x的右子樹
__p = __top;
__x = _S_left(__x);
///直接復制x的左子樹
while (__x != 0)
{
_Link_type __y = _M_clone_node(__x);
__p->_M_left = __y;
__y->_M_parent = __p;
if (__x->_M_right)
__y->_M_right = _M_copy(_S_right(__x), __y); ///繼續遞歸復制右子樹
__p = __y;
__x = _S_left(__x); ///x指向其左孩子,循環復制其左子樹
}
}
catch(...)
{
_M_erase(__top);
}
return __top;
}
template
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::_M_erase(_Link_type __x)
{
/// erase without rebalancing
while (__x != 0)
{
_M_erase(_S_right(__x)); ///遞歸刪除右子樹
///循環刪除左子樹
_Link_type __y = _S_left(__x);
destroy_node(__x);
__x = __y;
}
}
template
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::erase(iterator __first, iterator __last)
{
if (__first == begin() && __last == end())
clear();
else
while (__first != __last) erase(__first++);
}
template
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::erase(const _Key* __first, const _Key* __last)
{
while (__first != __last) erase(*__first++);
}
template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
{
_Link_type __y = _M_header; /// Last node which is not less than __k.
_Link_type __x = _M_root(); /// Current node.
while (__x != 0)
{
if (!_M_key_compare(_S_key(__x), __k)) ///k <= x的鍵值時
__y = __x, __x = _S_left(__x);
else ///k > x的鍵值時
__x = _S_right(__x);
}
///至此,x為k的可插入點,y為x的直接前驅,如果k存在,則j不可能為end(),
///而且應有j指向結點的鍵值和k相等
iterator __j = iterator(__y);
return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
end() : __j;
}
template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) const
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
while (__x != 0)
{
if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
}
const_iterator __j = const_iterator(__y);
return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
end() : __j;
}
template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::count(const _Key& __k) const
{
pair __p = equal_range(__k);
size_type __n = 0;
distance(__p.first, __p.second, __n);
return __n;
}
///返回"最小的"鍵值和k相同結點
template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::lower_bound(const _Key& __k)
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
while (__x != 0)
{
///當__x的鍵值 == k時,尋找"更小的" 鍵值等於k的__x
if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else /// x的鍵值 < k
__x = _S_right(__x);
}
return iterator(__y);
}
template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::lower_bound(const _Key& __k) const
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return const_iterator(__y);
}
///返回"最大的"鍵值和k相同結點的直接後繼
template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::upper_bound(const _Key& __k)
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
while (__x != 0)
{
if (_M_key_compare(__k, _S_key(__x))) ///k小於x的鍵值
__y = __x, __x = _S_left(__x);
else ///當__x的鍵值 == k時,尋找"更大的" __x
__x = _S_right(__x);
}
return iterator(__y);
}
template
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::upper_bound(const _Key& __k) const
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
while (__x != 0)
if (_M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return const_iterator(__y);
}
template
inline
pair::iterator,
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::equal_range(const _Key& __k)
{
return pair(lower_bound(__k), upper_bound(__k));
}
template
inline
pair::const_iterator,
typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator>
_Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>
::equal_range(const _Key& __k) const
{
return pair(lower_bound(__k),
upper_bound(__k));
}
///計算[__node,__root]之間黑色結點的個數,采用遞歸上溯法
inline int
__black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
{
if (__node == 0)
return 0;
else
{
int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0;
if (__node == __root)
return __bc;
else
return __bc + __black_count(__node->_M_parent, __root);
}
}
template
bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
{
if (_M_node_count == 0 || begin() == end())
return _M_node_count == 0 && begin() == end() &&
_M_header->_M_left == _M_header && _M_header->_M_right == _M_header;
int __len = __black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it)
{
_Link_type __x = (_Link_type) __it._M_node;
_Link_type __L = _S_left(__x);
_Link_type __R = _S_right(__x);
if (__x->_M_color == _S_rb_tree_red) ///檢驗紅色結點是否有紅色孩子
if ((__L && __L->_M_color == _S_rb_tree_red) ||
(__R && __R->_M_color == _S_rb_tree_red))
return false;
///檢驗鍵值是否不大於其左孩子
if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
return false;
///檢驗鍵值是否不小於其右孩子
if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
return false;
///檢驗左右孩子到根節點路徑的黑色結點數目是否相同
if (!__L && !__R && __black_count(__x, _M_root()) != __len)
return false;
}
///檢驗最大、小值指針指向是否正確
if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
return false;
if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
return false;
return true;
}
