### 前言
? 有關紅黑樹的知識在前面博文有介紹，讀者可自行往前面博文《[紅黑樹RB-Tree](http://blog.csdn.net/chenhanzhun/article/details/38405041)》，《[二叉查找樹](http://blog.csdn.net/chenhanzhun/article/details/21990545)》閱讀。本文介紹的RB-Tree(紅黑樹)是來自源碼SGI STL中的文件<stl_tree.h>。這里采用了header技巧，header指向根節點的指針，與根節點互為對方的父節點。他們之間的結構如下圖所示：
### RB-Tree(紅黑樹)源碼剖析
~~~
#ifndef __SGI_STL_INTERNAL_TREE_H
#define __SGI_STL_INTERNAL_TREE_H
/*
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.
*/
//下面這段話是侯捷老師對上面說明的翻譯.
/*
這章講解Red-black tree（紅黑樹）class,用來當做SLT關系式容器（如set,multiset,map,
multimap）.里面所用的insertion和deletion方法以Cormen, Leiserson 和 Riveset所著的
《Introduction to Algorithms》一書為基礎,但是有以下兩點不同:
(1)header不僅指向root,也指向紅黑樹的最左節點,以便用常數時間實現begin(),并且也指向紅黑樹的最右邊節點,以便
set相關泛型算法（如set_union等等）可以有線性時間表現.
(2)當一個即將被刪除的節點有兩個孩子節點時,它的successor（后繼）node is relinked into its place, ranther than copied,
如此一來唯一失效的（invalidated）的迭代器就只是那些referring to the deleted node.
*/
/*
SGI STL中的RB-Tree實現機制有一定的技巧,定義了一個指向根節點的節點指針header,
并且,header和根節點root互為對方的父節點,header的左子節點指向RB-Tree的最小節點,
header的右子節點指向RB-Tree的最大節點.
*/
/*
RB-Tree是一棵二叉查找樹,并且具備有以下性質:
紅黑樹的性質：
(1)每個節點或是紅色的,或是黑色的.
(2)根節點是黑色的.
(3)每個葉節點（NULL）是黑色的.
(4)如果一個節點是紅色的，則它的兩個孩子節點都是黑色的.
(5)對每個節點，從該節點到其所有后代葉節點的簡單路徑上，均包含相同數目的黑色節點.
*/
#include <stl_algobase.h>
#include <stl_alloc.h>
#include <stl_construct.h>
#include <stl_function.h>
__STL_BEGIN_NAMESPACE
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1375
#endif
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;//節點數據域,即關鍵字
};
//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;//最左節點就是后繼結點
}
//the right 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 */
// 以下都是全域函式：__rb_tree_rotate_left(), __rb_tree_rotate_right(),
// __rb_tree_rebalance(), __rb_tree_rebalance_for_erase()
//新節點必須為紅色節點。如果安插處的父節點為紅色，就違反了紅黑色規則
//此時要旋轉和改變顏色
//左旋轉
//節點x為左旋轉點
inline void
_Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
_Rb_tree_node_base* __y = __x->_M_right;//獲取左旋轉節點x的右孩子y
__x->_M_right = __y->_M_left;//把y節點的左孩子作為旋轉節點x的右孩子
if (__y->_M_left !=0)
__y->_M_left->_M_parent = __x;//更新節點y左孩子父節點指針，指向新的父節點x
__y->_M_parent = __x->_M_parent;//y節點替換x節點的位置
//令y完全頂替x的地位（必須將x對其父節點的關系完全接收過來）
if (__x == __root)//若原始位置節點x是根節點
__root = __y;//則y為新的根節點
//否則，若x節點是其父節點的左孩子
else if (__x == __x->_M_parent->_M_left)
__x->_M_parent->_M_left = __y;//則更新節點y為原始x父節點的左孩子
else//若x節點是其父節點的右孩子
__x->_M_parent->_M_right = __y;//則更新節點y為原始x父節點的右孩子
__y->_M_left = __x;//旋轉后旋轉節點x作為節點y的左孩子
__x->_M_parent = __y;//更新x節點的父節點指針
}
//右旋轉
//節點x為右旋轉點
inline void
_Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
_Rb_tree_node_base* __y = __x->_M_left;//獲取右旋轉節點x的左孩子y
__x->_M_left = __y->_M_right;//把y節點的右孩子作為旋轉節點x的左孩子
if (__y->_M_right != 0)
__y->_M_right->_M_parent = __x;//更新節點y右孩子父節點指針，指向新的父節點x
__y->_M_parent = __x->_M_parent;//y節點替換x節點的位置
//令y完全頂替x的地位（必須將x對其父節點的關系完全接收過來）
if (__x == __root)//若原始位置節點x是根節點
__root = __y;//則y為新的根節點
//否則，若x節點是其父節點的右孩子
else if (__x == __x->_M_parent->_M_right)
__x->_M_parent->_M_right = __y;//則更新節點y為原始x父節點的右孩子
else//若x節點是其父節點的左孩子
__x->_M_parent->_M_left = __y;//則更新節點y為原始x父節點的左孩子
__y->_M_right = __x;//旋轉后旋轉節點x作為節點y的右孩子
__x->_M_parent = __y;//更新x節點的父節點指針
}
//重新令RB-tree平衡（改變顏色和旋轉）
//參數一為新增節點x，參數二為root節點
inline void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
__x->_M_color = _S_rb_tree_red;//新插入的節點必須為紅色,這樣不會違反性質5.
//若新插入節點不是為RB-Tree的根節點，且其父節點color屬性也是紅色,即違反了性質4.
//則進入while循環.
//此時根據節點x的父節點x->parent是其祖父節點x->parent->parent的左孩子還是右孩子進行討論,
//但是左右孩子之間是對稱的，所以思想是類似的.
while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
//case1：節點x的父節點x->parent是其祖父節點x->parent->parent的左孩子
if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
//節點y為x節點的叔叔節點,即是節點x父節點x->parent的兄弟
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
if (__y && __y->_M_color == _S_rb_tree_red) {//情況1：若其叔叔節點y存在,且為紅色
/*
此時x->parent和y都是紅色的，解決辦法是將x的父節點x->parent和叔叔結點y都著為黑色，
而將x的祖父結點x->parent->parent著為紅色，
然后從祖父結點x->parent->parent繼續向上判斷是否破壞紅黑樹的性質。
*/
__x->_M_parent->_M_color = _S_rb_tree_black;//將其父節點x->parent改變成黑色
__y->_M_color = _S_rb_tree_black;//將其叔叔節點y改變成黑色
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;//將其祖父節點變成紅色
//把祖父節點作為當前節點,一直上溯,繼續判斷是否破壞RB-Tree性質.
__x = __x->_M_parent->_M_parent;
}
else {//若無叔叔節點或者其叔叔節點y為黑色
/*
情況2：x的叔叔節點y是黑色且x是一個右孩子
情況3：x的叔叔節點y是黑色且x是一個左孩子
情況2和情況3中y都是黑色的，通過x是parent[x]的左孩子還是右孩子進行區分的。
情況2中x是右孩子，可以在parent[x]結點將情況2通過左旋轉為情況3，使得x變為左孩子。
無論是間接還是直接的通過情況2進入到情況3，x的叔叔y總是黑色的。
在情況3中，將parent[x]著為黑色，parent[parent[x]]著為紅色，然后從parent[parent[x]]處進行一次右旋轉。
情況2、3修正了對性質4的違反，修正過程不會導致其他的紅黑性質被破壞。
*/
if (__x == __x->_M_parent->_M_right) {//若節點x為其父節點x->parent的右孩子
//則以其父節點作為旋轉節點
//進行一次左旋轉
__x = __x->_M_parent;
_Rb_tree_rotate_left(__x, __root);
//旋轉之后,節點x變成其父節點的左孩子
}
__x->_M_parent->_M_color = _S_rb_tree_black;//改變其父節點x->parent顏色
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;//改變其祖父節點x->parent->parent顏色
_Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);//對其祖父節點進行一次右旋轉
}
}
//case2：節點x的父節點x->parent是其祖父節點x->parent->parent的右孩子
//這種情況是跟上面的情況(父節點為其祖父節點的左孩子)是對稱的.
else {
//節點y為x節點的叔叔節點,即是節點x父節點x->parent的兄弟
_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;//上溯祖父節點,判斷是否違背RB-Tree的性質
}
else {//若叔叔節點不存在或叔叔節點為黑色
if (__x == __x->_M_parent->_M_left) {//新節點x為其父節點的左孩子
//對其父節點進行一次右旋轉
__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);//進行一次左旋轉
}
}
}
//若新插入節點為根節點,則違反性質2
//只需將其重新賦值為黑色即可
__root->_M_color = _S_rb_tree_black;
}
//刪除節點
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 { // __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) { // 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
__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);
}
if (__y->_M_color != _S_rb_tree_red) {
while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
if (__x == __x_parent->_M_left) {
_Rb_tree_node_base* __w = __x_parent->_M_right;
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_left(__x_parent, __root);
__w = __x_parent->_M_right;
}
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->_M_color = _S_rb_tree_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
} else {
if (__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black) {
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->_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);
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;
}
// Base class to encapsulate the differences between old SGI-style
// allocators and standard-conforming allocators. In order to avoid
// having an empty base class, we arbitrarily move one of rb_tree's
// data members into the base class.
//以下是對內存分配的管理
#ifdef __STL_USE_STD_ALLOCATORS
// _Base for general standard-conforming allocators.
template <class _Tp, class _Alloc, bool _S_instanceless>
class _Rb_tree_alloc_base {
public:
typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return _M_node_allocator; }//空間配置器的類型
_Rb_tree_alloc_base(const allocator_type& __a)
: _M_node_allocator(__a), _M_header(0) {}
protected:
typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type
_M_node_allocator;
_Rb_tree_node<_Tp>* _M_header;//定義頭指針，指向Rb_tree的根節點
_Rb_tree_node<_Tp>* _M_get_node() //分配一個節點空間
{ return _M_node_allocator.allocate(1); }
void _M_put_node(_Rb_tree_node<_Tp>* __p) //釋放一個節點空間
{ _M_node_allocator.deallocate(__p, 1); }
};
// Specialization for instanceless allocators.
template <class _Tp, class _Alloc>
class _Rb_tree_alloc_base<_Tp, _Alloc, true> {
public:
typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {}
protected:
_Rb_tree_node<_Tp>* _M_header;
typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type
_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); }
};
//RB-Tree基本結構,即基類,繼承_Rb_tree_alloc_base
template <class _Tp, class _Alloc>
struct _Rb_tree_base
: public _Rb_tree_alloc_base<_Tp, _Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
typedef _Rb_tree_alloc_base<_Tp, _Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
_Base;
typedef typename _Base::allocator_type allocator_type;
_Rb_tree_base(const allocator_type& __a)
: _Base(__a) { _M_header = _M_get_node(); }
~_Rb_tree_base() { _M_put_node(_M_header); }
};
#else /* __STL_USE_STD_ALLOCATORS */
//RB-Tree基本結構,即基類,沒有繼承_Rb_tree_alloc_base
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); }
};
#endif /* __STL_USE_STD_ALLOCATORS */
//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(const value_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); }
public:
//迭代器
typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
typedef _Rb_tree_iterator<value_type, const_reference, const_pointer>
const_iterator;
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
typedef reverse_bidirectional_iterator<iterator, value_type, reference,
difference_type>
reverse_iterator;
typedef reverse_bidirectional_iterator<const_iterator, value_type,
const_reference, difference_type>
const_reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
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)
: _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:
//初始化header
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(); }//RB-Tree的起始迭代器為最小節點
const_iterator begin() const { return _M_leftmost(); }
iterator end() { return _M_header; }//RB-Tree的結束迭代器為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());
}
//RB-Tree是否為空
bool empty() const { return _M_node_count == 0; }
//RB-Tree節點數
size_type size() const { return _M_node_count; }
size_type max_size() const { return size_type(-1); }
//交換兩棵RB-Tree的內容
//RB-tree只有三個表現成員，所以兩棵RB-Tree交換內容時，只需互換這3個成員
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<iterator,bool> insert_unique(const value_type& __x);
//插入節點,節點值可以與當前RB-Tree節點值相等
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);
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void insert_unique(_InputIterator __first, _InputIterator __last);
template <class _InputIterator>
void insert_equal(_InputIterator __first, _InputIterator __last);
#else /* __STL_MEMBER_TEMPLATES */
void insert_unique(const_iterator __first, const_iterator __last);
void insert_unique(const value_type* __first, const value_type* __last);
void insert_equal(const_iterator __first, const_iterator __last);
void insert_equal(const value_type* __first, const value_type* __last);
#endif /* __STL_MEMBER_TEMPLATES */
//刪除節點
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);
//清除RB-Tree
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<iterator,iterator> equal_range(const key_type& __x);
pair<const_iterator, const_iterator> equal_range(const key_type& __x) const;
public:
// Debugging.
bool __rb_verify() const;
};
//以下是操作符重載
//重載operator==運算符，使用的是STL泛型算法
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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() &&
//STL的算法equal(__x.begin(), __x.end(), __y.begin());
equal(__x.begin(), __x.end(), __y.begin());
}
//重載operator<運算符，使用的是STL泛型算法
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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());
}
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline bool
operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
return !(__x == __y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline bool
operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
return __y < __x;
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline bool
operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
return !(__y < __x);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline bool
operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
return !(__x < __y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline void
swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
__x.swap(__y);
}
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
_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;
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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)
{//參數x_為新值插入點，參數y_為插入點之父節點，參數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);//創建值為v的節點z
_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())//若y為最左節點
_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);//調整RB-Tree使其滿足性質
++_M_node_count;//節點數增加1
return iterator(__z);//返回新節點迭代器
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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) {//從根節點開始,往下尋找合適插入點
__y = __x;
//判斷新插入節點值與當前節點x值的大小,以便判斷往x的左邊走還是往右邊走
__x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
_S_left(__x) : _S_right(__x);
}
return _M_insert(__x, __y, __v);
}
// 安插新值；節點鍵值不允許重復，若重復則安插無效。
// 注意，傳回值是個pair，第一元素是個 RB-tree 迭代器，指向新增節點，
// 第二元素表示安插成功與否。
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::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;
//判斷新插入節點值與當前節點x值的大小,以便判斷往x的左邊走還是往右邊走
__comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
__x = __comp ? _S_left(__x) : _S_right(__x);
}
//離開while循環之后，y所指即為安插點的父節點，x必為葉子節點
iterator __j = iterator(__y);//令迭代器j指向插入節點之父節點y
if (__comp)//若為真
if (__j == begin())//若插入點之父節點為最左節點
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
else//否則(插入點之父節點不在最左節點)
--__j;//調整j
// 小于新值（表示遇「小」，將安插于右側）
if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
//若運行到這里，表示鍵值有重復，不應該插入
return pair<iterator,bool>(__j, false);
}
template <class _Key, class _Val, class _KeyOfValue,
class _Compare, class _Alloc>
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)))
return _M_insert(__position._M_node, __position._M_node, __v);
// first argument just needs to be non-null
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 <class _Key, class _Val, class _KeyOfValue,
class _Compare, class _Alloc>
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);
}
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
template<class _II>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_equal(_II __first, _II __last)
{
for ( ; __first != __last; ++__first)
insert_equal(*__first);
}
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
template<class _II>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_unique(_II __first, _II __last) {
for ( ; __first != __last; ++__first)
insert_unique(*__first);
}
#else /* __STL_MEMBER_TEMPLATES */
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
void
_Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_equal(const _Val* __first, const _Val* __last)
{
for ( ; __first != __last; ++__first)
insert_equal(*__first);
}
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
void
_Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_equal(const_iterator __first, const_iterator __last)
{
for ( ; __first != __last; ++__first)
insert_equal(*__first);
}
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
void
_Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_unique(const _Val* __first, const _Val* __last)
{
for ( ; __first != __last; ++__first)
insert_unique(*__first);
}
template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_unique(const_iterator __first, const_iterator __last)
{
for ( ; __first != __last; ++__first)
insert_unique(*__first);
}
#endif /* __STL_MEMBER_TEMPLATES */
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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 <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
{
pair<iterator,iterator> __p = equal_range(__x);
size_type __n = 0;
distance(__p.first, __p.second, __n);
erase(__p.first, __p.second);
return __n;
}
template <class _Key, class _Val, class _KoV, class _Compare, class _Alloc>
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;
__STL_TRY {
if (__x->_M_right)
__top->_M_right = _M_copy(_S_right(__x), __top);
__p = __top;
__x = _S_left(__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);
}
}
__STL_UNWIND(_M_erase(__top));
return __top;
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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 <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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 <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::erase(const _Key* __first, const _Key* __last)
{
while (__first != __last) erase(*__first++);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
iterator __j = iterator(__y);
return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
end() : __j;
}
//查找RB樹中是否有鍵值為k的節點
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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; /* 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
__x = _S_right(__x);
}
const_iterator __j = const_iterator(__y);
return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
end() : __j;
}
//計算RB樹中鍵值為k的節點的個數
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::count(const _Key& __k) const
{
pair<const_iterator, const_iterator> __p = equal_range(__k);
size_type __n = 0;
distance(__p.first, __p.second, __n);
return __n;
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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; /* 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))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return iterator(__y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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; /* 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))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return const_iterator(__y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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; /* Last node which is greater than __k. */
_Link_type __x = _M_root(); /* Current node. */
while (__x != 0)
if (_M_key_compare(__k, _S_key(__x)))
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return iterator(__y);
}
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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; /* Last node which is greater than __k. */
_Link_type __x = _M_root(); /* Current node. */
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 <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
inline
pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::equal_range(const _Key& __k)
{
return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k));
}
template <class _Key, class _Value, class _KoV, class _Compare, class _Alloc>
inline
pair<typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::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<const_iterator,const_iterator>(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;//若節點node為黑色,則bc為1
if (__node == __root)//判斷node是否為根節點
return __bc;
else
return __bc + __black_count(__node->_M_parent, __root);//遞歸調用
}
}
//驗證己生這棵樹是否符合RB樹條件
template <class _Key, class _Value, class _KeyOfValue,
class _Compare, class _Alloc>
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());
//一下走訪整個RB樹，針對每個節點（從最小到最大）……
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)//違背性質4
//如果一個節點是紅色的，則它的兩個孩子節點都是黑色的。
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;
//[葉子結點到root]路徑內的黑色節點數，與[最左節點至root]路徑內的黑色節點不同。不符合RB樹要求
//違背性質5
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;
}
// Class rb_tree is not part of the C++ standard. It is provided for
// compatibility with the HP STL.
template <class _Key, class _Value, class _KeyOfValue, class _Compare,
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>
{
typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
typedef typename _Base::allocator_type allocator_type;
rb_tree(const _Compare& __comp = _Compare(),
const allocator_type& __a = allocator_type())
: _Base(__comp, __a) {}
~rb_tree() {}
};
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1375
#endif
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_TREE_H */
// Local Variables:
// mode:C++
// End:
~~~
參考資料：
《STL源碼剖析》侯捷
《[STL源碼剖析---stl_tree.h閱讀筆記](http://blog.csdn.net/kangroger/article/details/38587785)》
- 前言
- 空間配置器
- Traits編程技術
- STL源碼剖析——迭代器
- 全局函數construct(),destroy(),uninitialized_copy(),uninitialized_fill(),uninitialized_fill_n()
- 序列容器之vector
- list容器的排序算法sort()
- 序列容器之list
- 序列容器之deque
- 容器配接器之stack
- 容器配接器之queue
- 容器配接器之priority_queue
- 最大堆heap
- 單向鏈表slist
- RB-Tree(紅黑樹)
- 關聯容器之set
- stl_pair.h學習
- 關聯容器之map
- 關聯容器之multiset
- 關聯容器之multimap
- 散列表hashtable
- stl_hash_fun.h學習
- 關聯容器之hash_set
- 關聯容器之hash_multiset
- 關聯容器之hash_map
- 關聯容器之hash_multimap
- 數值算法stl_numeric.h
- stl_relops.h學習
- 基本算法stl_algobase.h
- STL算法之set集合算法
- STL算法stl_algo.h
- STL算法之sort排序算法
- STL算法之find查找算法
- STL算法之merge合并算法
- STL算法之remove刪除算法
- STL算法之permutation排列組合
- STL函數對象