Rb-tree
红黑树（R-B TREE，全称：Red-Black Tree），本身是一棵二叉查找树，在其基础上附加了两个要求：
- 树中的每个结点增加了一个用于存储颜色的标志域；
- 树中没有一条路径比其他任何路径长出两倍，整棵树要接近于“平衡”的状态。
红黑树对于结点的颜色设置不是任意的，需满足以下性质的二叉查找树才是红黑树：
- 树中的每个结点颜色不是红的，就是黑的；
- 根结点的颜色是黑的；
- 所有为 nil 的叶子结点的颜色是黑的；（注意：叶子结点说的只是为空（nil 或 NULL）的叶子结点！）
- 如果此结点是红的，那么它的两个孩子结点全部都是黑的；
- 对于每个结点，从该结点到到该结点的所有子孙结点的所有路径上包含有相同数目的黑结点；
对于一棵具有 n 个结点的红黑树，树的高度至多为：2lg(n+1)
由此可推出红黑树进行查找操作时的时间复杂度为O(lgn)，因为对于高度为 h 的二叉查找树的运行时间为O(h)，而包含有 n 个结点的红黑树本身就是最高为 lgn（简化之后）的查找树（h=lgn），所以红黑树的时间复杂度为O(lgn)
红黑树的旋转
当使用红黑树进行插入或者删除结点的操作时，可能会破坏红黑树的 5 条性质，从而变成了一棵普通树，此时就可以通过对树中的某些子树进行旋转，从而使整棵树重新变为一棵红黑树。
旋转操作分为左旋和右旋，同二叉排序树转平衡二叉树的旋转原理完全相同。例如图表示的是对一棵二叉查找树中局部子树进行左旋和右旋操作：
左旋：如图所示，左旋时 y 结点变为该部分子树的根结点，同时 x 结点（连同其左子树 a）移动至 y 结点的左孩子。若 y 结点有左孩子 b，由于 x 结点需占用其位置，所以调整至 x 结点的右孩子处。
左旋操作的具体实现函数：
//T表示为树根，x 表示需要进行左旋的子树的根结点
void rbTree_left_rotate( RBT_Root* T, RB_TREE* x){
RB_TREE* y = x->right;//找到根结点的右子树
x->right = y->left;//将右子树的左孩子移动至结点 x 的右孩子处
if(x->right != T->nil){//如果 x 的右子树不是nil，需重新连接 右子树的双亲结点为 x
x->right->p = x;
}
y->p = x->p;//设置 y 的双亲结点为 x 的双亲结点
//重新设置 y 的双亲结点同 y 的连接，分为 2 种情况：1、原 x 结点本身就是整棵树的数根结点，此时只需要将 T 指针指向 y；2、根据 y 中关键字同其父结点关键字的值的大小，判断 y 是父结点的左孩子还是右孩子
if(y->p == T->nil){
T->root = y;
}else if(y->key < y->p->key){
y->p->left = y;
}else{
y->p->right = y;
}
y->left = x;//将 x 连接给 y 结点的左孩子处
x->p = y;//设置 x 的双亲结点为 y。
}
节点定义如下：
typedef enum {RED, BLACK} ColorType;
typedef struct RB_TREE{
int key;
struct RB_TREE * left;
struct RB_TREE * right;
struct RB_TREE * p;
ColorType color;
}RB_TREE;
typedef struct RBT_Root{
RB_TREE* root;
RB_TREE* nil;
}RBT_Root;
右旋：同样如上图所示，同左旋是同样的道理，x 结点变为根结点，同时 y 结点连同其右子树 c 作为 x 结点的右子树，原 x 结点的右子树 b 变为 y 结点的左子树。
右旋的具体代码实现：
void rbTree_right_rotate( RBT_Root* T, RB_TREE* x){
RB_TREE * y = x->left;
x->left = y->right;
if(T->nil != x->left){
x->left->p = x;
}
y->p = x->p;
if(y->p == T->nil){
T->root = y;
}else if(y->key < y->p->key){
y->p->left= y;
}else{
y->p->right = y;
}
y->right = x;
x->p = y;
}
红黑树中插入新结点
当创建一个红黑树或者向已有红黑树中插入新的数据时，只需要按部就班地执行以下 3 步：
- 由于红黑树本身是一棵二叉查找树，所以在插入新的结点时，完全按照二叉查找树插入结点的方法，找到新结点插入的位置；
- 将新插入的结点结点初始化，颜色设置为红色后插入到指定位置；（将新结点初始化为红色插入后，不会破坏红黑树第 5 条的性质）
- 由于插入新的结点，可能会破坏红黑树第 4 条的性质（若其父结点颜色为红色，就破坏了红黑树的性质），此时需要调整二叉查找树，想办法通过旋转以及修改树中结点的颜色，使其重新成为红黑树！
插入结点的第 1 步和第 2 步都非常简单，关键在于最后一步对树的调整！在红黑树中插入结点时，根据插入位置的不同可分为以下 3 种情况：
-
插入位置为整棵树的树根。处理办法：只需要将插入结点的颜色改为黑色即可。
-
插入位置的双亲结点的颜色为黑色。处理方法：此种情况不需要做任何工作，新插入的颜色为红色的结点不会破坏红黑树的性质。
-
插入位置的双亲结点的颜色为红色。处理方法：由于插入结点颜色为红色，其双亲结点也为红色，破坏了红黑树第 4 条性质，此时需要结合其祖父结点和祖父结点的另一个孩子结点（父结点的兄弟结点，此处称为“叔叔结点”）的状态，分为 3 种情况讨论:
-
当前结点的父节点是红色，且“叔叔结点”也是红色：破坏了红黑树的第 4 条性质，解决方案为：将父结点颜色改为黑色；将叔叔结点颜色改为黑色；将祖父结点颜色改为红色；下一步将祖父结点认做当前结点，继续判断，处理结果如下图所示：
- 分析：此种情况下，由于父结点和当前结点颜色都是红色，所以为了不产生冲突，将父结点的颜色改为黑色。但是虽避免了破坏第 4 条，但是却导致该条路径上的黑高度增加了 1 ，破坏了第 5 条性质。但是在将祖父结点颜色改为红色、叔叔结点颜色改为黑色后，该部分子树没有破坏第 5 条性质。但是由于将祖父结点的颜色改变，还需判断是否破坏了上层树的结构，所以需要将祖父结点看做当前结点，继续判断。
-
当前结点的父结点颜色为红色，叔叔结点颜色为黑色，且当前结点是父结点的右孩子。解决方案：将父结点作为当前结点做左旋操作。
- 在进行以父结点为当前结点的左旋操作后，此种情况就转变成了第 3 种情况，处理过程跟第 3 种情况同步进行。
-
当前结点的父结点颜色为红色，叔叔结点颜色为黑色，且当前结点是父结点的左孩子。解决方案：将父结点颜色改为黑色，祖父结点颜色改为红色，从祖父结点处进行右旋处理。如下图所示：
- 分析：在此种情况下，由于当前结点 F 和父结点 S 颜色都为红色，违背了红黑树的性质 4，此时可以将 S 颜色改为黑色，有违反了性质 5，因为所有通过 S 的路径其黑高度都增加了 1 ，所以需要将其祖父结点颜色设为红色后紧接一个右旋，这样这部分子树有成为了红黑树。（上图中的有图虽看似不是红黑树，但是只是整棵树的一部分，以 S 为根结点的子树一定是一棵红黑树）
-
红黑树中插入结点的具体实现代码：
void RB_Insert_Fixup(RBT_Root* T, RB_TREE* x){
//首先判断其父结点颜色为红色时才需要调整；为黑色时直接插入即可，不需要调整
while (x->p->color == RED) {
//由于还涉及到其叔叔结点，所以此处需分开讨论，确定父结点是祖父结点的左孩子还是右孩子
if (x->p == x->p->p->left) {
RB_TREE * y = x->p->p->right;//找到其叔叔结点
//如果叔叔结点颜色为红色，此为第 1 种情况，处理方法为：父结点颜色改为黑色；叔叔结点颜色改为黑色；祖父结点颜色改为红色，将祖父结点赋值为当前结点，继续判断；
if (y->color == RED) {
x->p->color = BLACK;
y->color = BLACK;
x->p->p->color = RED;
x = x->p->p;
}else{
//反之，如果叔叔结点颜色为黑色，此处需分为两种情况：1、当前结点时父结点的右孩子；2、当前结点是父结点的左孩子
if (x == x->p->right) {
//第 2 种情况：当前结点时父结点的右孩子。解决方案：将父结点作为当前结点做左旋操作。
x = x->p;
rbTree_left_rotate(T, x);
}else{
//第 3 种情况：当前结点是父结点的左孩子。解决方案：将父结点颜色改为黑色，祖父结点颜色改为红色，从祖父结点处进行右旋处理。
x->p->color = BLACK;
x->p->p->color = RED;
rbTree_right_rotate(T, x->p->p);
}
}
}else{//如果父结点时祖父结点的右孩子，换汤不换药，只需将以上代码部分中的left改为right即可，道理是一样的。
RB_TREE * y = x->p->p->left;
if (y->color == RED) {
x->p->color = BLACK;
y->color = BLACK;
x->p->p->color = RED;
x = x->p->p;
}else{
if (x == x->p->left) {
x = x->p;
rbTree_right_rotate(T, x);
}else{
x->p->color = BLACK;
x->p->p->color = RED;
rbTree_left_rotate(T, x->p->p);
}
}
}
}
T->root->color = BLACK;
}
//插入操作分为 3 步：1、将红黑树当二叉查找树，找到其插入位置；2、初始化插入结点，将新结点的颜色设为红色；3、通过调用调整函数，将二叉查找树重新改为红黑树
void rbTree_insert(RBT_Root**T, int k){
//1、找到其要插入的位置。解决思路为：从树的根结点开始，通过不断的同新结点的值进行比较，最终找到插入位置
RB_TREE * x, *p;
x = (*T)->root;
p = x;
while(x != (*T)->nil){
p = x;
if(k<x->key){
x = x->left;
}else if(k>x->key){
x = x->right;
}else{
printf("\n%d已存在\n",k);
return;
}
}
//初始化结点，将新结点的颜色设为红色
x = (RB_TREE *)malloc(sizeof(RB_TREE));
x->key = k;
x->color = RED;
x->left = x->right =(*T)->nil;
x->p = p;
//对新插入的结点，建立与其父结点之间的联系
if((*T)->root == (*T)->nil){
(*T)->root = x;
}else if(k < p->key){
p->left = x;
}else{
p->right = x;
}
//3、对二叉查找树进行调整
RB_Insert_Fixup((*T),x);
}
红黑树中删除结点
在红黑树中删除结点，思路更简单，只需要完成 2 步操作：
- 将红黑树按照二叉查找树删除结点的方法删除指定结点；
- 重新调整删除结点后的树，使之重新成为红黑树；（还是通过旋转和重新着色的方式进行调整）
在二叉查找树删除结点时，分为 3 种情况：
- 若该删除结点本身是叶子结点，则可以直接删除；
- 若只有一个孩子结点（左孩子或者右孩子），则直接让其孩子结点顶替该删除结点；
- 若有两个孩子结点，则找到该结点的右子树中值最小的叶子结点来顶替该结点，然后删除这个值最小的叶子结点。
以上三种情况最终都需要删除某个结点，此时需要判断删除该结点是否会破坏红黑树的性质。判断的依据是：
-
如果删除结点的颜色为红色，则不会破坏；
-
如果删除结点的颜色为黑色，则肯定会破坏红黑树的第 5 条性质，此时就需要对树进行调整，调整方案分 4 种情况讨论：
-
删除结点的兄弟结点颜色是红色，调整措施为：将兄弟结点颜色改为黑色，父亲结点改为红色，以父亲结点来进行左旋操作，同时更新删除结点的兄弟结点（左旋后兄弟结点发生了变化），如下图所示：
-
删除结点的兄弟结点及其孩子全部都是黑色的，调整措施为：将删除结点的兄弟结点设为红色，同时设置删除结点的父结点标记为新的结点，继续判断；
-
删除结点的兄弟结点是黑色，其左孩子是红色，右孩子是黑色。调整措施为：将兄弟结点设为红色，兄弟结点的左孩子结点设为黑色，以兄弟结点为准进行右旋操作，最终更新删除结点的兄弟结点；
-
删除结点的兄弟结点是黑色，其右孩子是红色（左孩子不管是什么颜色），调整措施为：将删除结点的父结点的颜色赋值给其兄弟结点，然后再设置父结点颜色为黑色，兄弟结点的右孩子结点为黑色，根据其父结点做左旋操作，最后设置替换删除结点的结点为根结点；
-
红黑树删除结点具体实现代码为：
void rbTree_transplant(RBT_Root* T, RB_TREE* u, RB_TREE* v){
if(u->p == T->nil){
T->root = v;
}else if(u == u->p->left){
u->p->left=v;
}else{
u->p->right=v;
}
v->p = u->p;
}
void RB_Delete_Fixup(RBT_Root**T,RB_TREE*x){
while(x != (*T)->root && x->color == BLACK){
if(x == x->p->left){
RB_TREE* w = x->p->right;
//第 1 种情况：兄弟结点是红色的
if(RED == w->color){
w->color = BLACK;
w->p->color = RED;
rbTree_left_rotate((*T),x->p);
w = x->p->right;
}
//第2种情况：兄弟是黑色的，并且兄弟的两个儿子都是黑色的。
if(w->left->color == BLACK && w->right->color == BLACK){
w->color = RED;
x = x->p;
}
//第3种情况
if(w->left->color == RED && w->right->color == BLACK){
w->left->color = BLACK;
w->color = RED;
rbTree_right_rotate((*T),w);
w = x->p->right;
}
//第4种情况
if (w->right->color == RED) {
w->color = x->p->color;
x->p->color = BLACK;
w->right->color = BLACK;
rbTree_left_rotate((*T),x->p);
x = (*T)->root;
}
}else{
RB_TREE* w = x->p->left;
//第 1 种情况
if(w->color == RED){
w->color = BLACK;
x->p->color = RED;
rbTree_right_rotate((*T),x->p);
w = x->p->left;
}
//第 2 种情况
if(w->left->color == BLACK && w->right->color == BLACK){
w->color = RED;
x = x->p;
}
//第 3 种情况
if(w->left->color == BLACK && w->right->color == RED){
w->color = RED;
w->right->color = BLACK;
w = x->p->left;
}
//第 4 种情况
if (w->right->color == BLACK){
w->color=w->p->color;
x->p->color = BLACK;
w->left->color = BLACK;
rbTree_right_rotate((*T),x->p);
x = (*T)->root;
}
}
}
x->color = BLACK;//最终将根结点的颜色设为黑色
}
void rbTree_delete(RBT_Root* *T, int k){
if(NULL == (*T)->root){
return ;
}
//找到要被删除的结点
RB_TREE * toDelete = (*T)->root;
RB_TREE * x = NULL;
//找到值为k的结点
while(toDelete != (*T)->nil && toDelete->key != k){
if(k<toDelete->key){
toDelete = toDelete->left;
}else if(k>toDelete->key){
toDelete = toDelete->right;
}
}
if(toDelete == (*T)->nil){
printf("\n%d 不存在\n",k);
return;
}
//如果两个孩子，就找到右子树中最小的结点，将之代替，然后直接删除该结点即可
if(toDelete->left != (*T)->nil && toDelete->right != (*T)->nil){
RB_TREE* alternative = rbt_findMin((*T), toDelete->right);
k = toDelete->key = alternative->key;//这里只对值进行复制，并不复制颜色，以免破坏红黑树的性质
toDelete = alternative;
}
//如果只有一个孩子结点（只有左孩子或只有右孩子），直接用孩子结点顶替该结点位置即可（没有孩子结点的也走此判断语句）。
if(toDelete->left == (*T)->nil){
x = toDelete->right;
rbTree_transplant((*T),toDelete,toDelete->right);
}else if(toDelete->right == (*T)->nil){
x = toDelete->left;
rbTree_transplant((*T),toDelete,toDelete->left);
}
//在删除该结点之前，需判断此结点的颜色：如果是红色，直接删除，不会破坏红黑树；若是黑色，删除后会破坏红黑树的第 5 条性质，需要对树做调整。
if(toDelete->color == BLACK){
RB_Delete_Fixup(T,x);
}
//最终可以彻底删除要删除的结点，释放其占用的空间
free(toDelete);
}
Rb-tree与BST的对比
红黑树虽隶属于二叉查找树，但是二叉查找树的时间复杂度会受到其树深度的影响，而红黑树可以保证在最坏情况下的时间复杂度仍为O(lgn)。当数据量多到一定程度时，使用红黑树比二叉查找树的效率要高。
同平衡二叉树相比较，红黑树没有像平衡二叉树对平衡性要求的那么苛刻。
经过对红黑树的原理与简单实现的分析，下面对SGI STL中红黑树的主要结构的实现进行分析。分析的源码采用的是GCC6.4.1支持的SGI STL，基于c++11的实现。
RB-tree 的节点结构：
enum _Rb_tree_color { _S_red = false, _S_black = true };
struct _Rb_tree_node_base
{
typedef _Rb_tree_node_base* _Base_ptr;
typedef const _Rb_tree_node_base* _Const_Base_ptr;
_Rb_tree_color _M_color; //节点颜色，非红即黑
_Base_ptr _M_parent; //父节点
_Base_ptr _M_left; //左子节点
_Base_ptr _M_right; //右子节点
//找到最小值，根据BST特性，向左遍历即可
static _Base_ptr
_S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
while (__x->_M_left != 0) __x = __x->_M_left;
return __x;
}
static _Const_Base_ptr
_S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
while (__x->_M_left != 0) __x = __x->_M_left;
return __x;
}
//找到最大值，根据BST特性，向右遍历即可
static _Base_ptr
_S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
while (__x->_M_right != 0) __x = __x->_M_right;
return __x;
}
static _Const_Base_ptr
_S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
while (__x->_M_right != 0) __x = __x->_M_right;
return __x;
}
};
_Rb_tree_header:
Rb-tree中一个重要的设计实现方法就是Header节点，header的父节点指向根节点，左子节点指向最左节点，右子节点指向最大节点。每次插入新节点时不但要依照RB-tree的规则来调整节点，还要维护header的正确性。
struct _Rb_tree_header
{
//设计的特殊节点，header的父节点指向根节点，左子节点指向最左节点，右子节点指向最大节点。每次插入新节点时要维护header的正确性
_Rb_tree_node_base _M_header;
//记录树的大小（节点数目）
size_t _M_node_count;
_Rb_tree_header() _GLIBCXX_NOEXCEPT
{
_M_header._M_color = _S_red;
_M_reset();
}
#if __cplusplus >= 201103L
_Rb_tree_header(_Rb_tree_header&& __x) noexcept
{
if (__x._M_header._M_parent != nullptr)
_M_move_data(__x);
else
{
_M_header._M_color = _S_red;
_M_reset();
}
}
#endif
void
_M_move_data(_Rb_tree_header& __from)
{
_M_header._M_color = __from._M_header._M_color;
_M_header._M_parent = __from._M_header._M_parent;
_M_header._M_left = __from._M_header._M_left;
_M_header._M_right = __from._M_header._M_right;
_M_header._M_parent->_M_parent = &_M_header;
_M_node_count = __from._M_node_count;
__from._M_reset();
}
void
_M_reset()
{
_M_header._M_parent = 0;
_M_header._M_left = &_M_header;
_M_header._M_right = &_M_header;
_M_node_count = 0;
}
};
Rb-tree 迭代器结构
//Rb-tree 迭代器
template<typename _Tp>
struct _Rb_tree_iterator
{
typedef _Tp value_type;
typedef _Tp& reference;
typedef _Tp* pointer;
//双向迭代器
typedef bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
typedef _Rb_tree_iterator<_Tp> _Self;
typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
typedef _Rb_tree_node<_Tp>* _Link_type;
_Rb_tree_iterator() _GLIBCXX_NOEXCEPT
: _M_node() { }
explicit
_Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
: _M_node(__x) { }
reference
operator*() const _GLIBCXX_NOEXCEPT
{ return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
pointer
operator->() const _GLIBCXX_NOEXCEPT
{ return static_cast<_Link_type> (_M_node)->_M_valptr(); }
//operator++调用increment(),基于BST的节点排列规则
_Self&
operator++() _GLIBCXX_NOEXCEPT
{
_M_node = _Rb_tree_increment(_M_node);
return *this;
}
_Self
operator++(int) _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
_M_node = _Rb_tree_increment(_M_node);
return __tmp;
}
//operator++调用decrement(),基于BST的节点排列规则
_Self&
operator--() _GLIBCXX_NOEXCEPT
{
_M_node = _Rb_tree_decrement(_M_node);
return *this;
}
_Self
operator--(int) _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
_M_node = _Rb_tree_decrement(_M_node);
return __tmp;
}
bool
operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
{ return _M_node == __x._M_node; }
bool
operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
{ return _M_node != __x._M_node; }
_Base_ptr _M_node;
};
Rb-tree 主要结构
//Rb-tree结构
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc = allocator<_Val> >
class _Rb_tree
{
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
protected:
typedef _Rb_tree_node_base* _Base_ptr;
typedef const _Rb_tree_node_base* _Const_Base_ptr;
typedef _Rb_tree_node<_Val>* _Link_type;
typedef const _Rb_tree_node<_Val>* _Const_Link_type;
private:
// 仿函数使用节点内存池，当池空的时候调用alloc分配节点
struct _Reuse_or_alloc_node
{
_Reuse_or_alloc_node(_Rb_tree& __t)
: _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
{
if (_M_root)
{
_M_root->_M_parent = 0;
if (_M_nodes->_M_left)
_M_nodes = _M_nodes->_M_left;
}
else
_M_nodes = 0;
}
_Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
~_Reuse_or_alloc_node()
{ _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
template<typename _Arg>
_Link_type
operator()(_Arg&& __arg)
{
_Link_type __node = static_cast<_Link_type>(_M_extract());
if (__node)
{
_M_t._M_destroy_node(__node);
_M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
return __node;
}
return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
}
private:
_Base_ptr
_M_extract()
{
if (!_M_nodes)
return _M_nodes;
_Base_ptr __node = _M_nodes;
_M_nodes = _M_nodes->_M_parent;
if (_M_nodes)
{
if (_M_nodes->_M_right == __node)
{
_M_nodes->_M_right = 0;
if (_M_nodes->_M_left)
{
_M_nodes = _M_nodes->_M_left;
while (_M_nodes->_M_right)
_M_nodes = _M_nodes->_M_right;
if (_M_nodes->_M_left)
_M_nodes = _M_nodes->_M_left;
}
}
else // __node is on the left.
_M_nodes->_M_left = 0;
}
else
_M_root = 0;
return __node;
}
_Base_ptr _M_root; //_Reuse_or_alloc_node根节点
_Base_ptr _M_nodes;
_Rb_tree& _M_t;
}; //end of struct _Reuse_or_alloc_node
public:
typedef _Key key_type;
typedef _Val value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Alloc allocator_type;
_Node_allocator&
_M_get_Node_allocator() _GLIBCXX_NOEXCEPT
{ return *static_cast<_Node_allocator*>(&this->_M_impl); }
const _Node_allocator&
_M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
{ return *static_cast<const _Node_allocator*>(&this->_M_impl); }
allocator_type
get_allocator() const _GLIBCXX_NOEXCEPT
{ return allocator_type(_M_get_Node_allocator()); }
protected:
//配置空间方法
_Link_type
_M_get_node()
{ return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
void
_M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
{ _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
//构造内存方法
template<typename... _Args>
void
_M_construct_node(_Link_type __node, _Args&&... __args)
{
__try
{
::new(__node) _Rb_tree_node<_Val>;
_Alloc_traits::construct(_M_get_Node_allocator(),
__node->_M_valptr(),
std::forward<_Args>(__args)...);
}
__catch(...)
{
__node->~_Rb_tree_node<_Val>();
_M_put_node(__node);
__throw_exception_again;
}
}
template<typename... _Args>
_Link_type
_M_create_node(_Args&&... __args)
{
_Link_type __tmp = _M_get_node(); //配置空间
_M_construct_node(__tmp, std::forward<_Args>(__args)...);//构造内存
return __tmp;
}
void
_M_destroy_node(_Link_type __p) noexcept
{
_Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
__p->~_Rb_tree_node<_Val>();
}
void
_M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
{
_M_destroy_node(__p);
_M_put_node(__p);
}
//复制一个节点
template<typename _NodeGen>
_Link_type
_M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
{
_Link_type __tmp = __node_gen(*__x->_M_valptr());
__tmp->_M_color = __x->_M_color;
__tmp->_M_left = 0;
__tmp->_M_right = 0;
return __tmp;
}
protected:
template<typename _Key_compare,
bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
struct _Rb_tree_impl
: public _Node_allocator
, public _Rb_tree_key_compare<_Key_compare>
, public _Rb_tree_header
{
typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
_Rb_tree_impl() = default;
_Rb_tree_impl(_Rb_tree_impl&&) = default;
_Rb_tree_impl(const _Rb_tree_impl& __x)
: _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
, _Base_key_compare(__x._M_key_compare)
{ }
_Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
: _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
{ }
};
_Rb_tree_impl<_Compare> _M_impl;
protected:
//header的父节点指向根节点，左子节点指向最左节点，右子节点指向最大节点。每次插入新节点时要维护header的正确性
//方便取得header的成员
_Base_ptr&
_M_root() _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_parent; }
_Const_Base_ptr
_M_root() const _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_parent; }
_Base_ptr&
_M_leftmost() _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_left; }
_Const_Base_ptr
_M_leftmost() const _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_left; }
_Base_ptr&
_M_rightmost() _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_right; }
_Const_Base_ptr
_M_rightmost() const _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_right; }
_Link_type
_M_begin() _GLIBCXX_NOEXCEPT
{ return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
_Const_Link_type
_M_begin() const _GLIBCXX_NOEXCEPT
{
return static_cast<_Const_Link_type>
(this->_M_impl._M_header._M_parent);
}
_Base_ptr
_M_end() _GLIBCXX_NOEXCEPT
{ return &this->_M_impl._M_header; }
_Const_Base_ptr
_M_end() const _GLIBCXX_NOEXCEPT
{ return &this->_M_impl._M_header; }
static const_reference
_S_value(_Const_Link_type __x)
{ return *__x->_M_valptr(); }
static const _Key&
_S_key(_Const_Link_type __x)
{ return _KeyOfValue()(_S_value(__x)); }
//取得节点x的成员
static _Link_type
_S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{ return static_cast<_Link_type>(__x->_M_left); }
static _Const_Link_type
_S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
{ return static_cast<_Const_Link_type>(__x->_M_left); }
static _Link_type
_S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{ return static_cast<_Link_type>(__x->_M_right); }
static _Const_Link_type
_S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
{ return static_cast<_Const_Link_type>(__x->_M_right); }
static const_reference
_S_value(_Const_Base_ptr __x)
{ return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
static const _Key&
_S_key(_Const_Base_ptr __x)
{ return _KeyOfValue()(_S_value(__x)); }
static _Base_ptr
_S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{ return _Rb_tree_node_base::_S_minimum(__x); }
static _Const_Base_ptr
_S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
{ return _Rb_tree_node_base::_S_minimum(__x); }
static _Base_ptr
_S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{ return _Rb_tree_node_base::_S_maximum(__x); }
static _Const_Base_ptr
_S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
{ return _Rb_tree_node_base::_S_maximum(__x); }
public:
typedef _Rb_tree_iterator<value_type> iterator;
typedef _Rb_tree_const_iterator<value_type> const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
private:
template<typename _Arg, typename _NodeGen>
iterator
_M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
iterator
_M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
template<typename _Arg>
iterator
_M_insert_lower(_Base_ptr __y, _Arg&& __v);
template<typename _Arg>
iterator
_M_insert_equal_lower(_Arg&& __x);
iterator
_M_insert_lower_node(_Base_ptr __p, _Link_type __z);
iterator
_M_insert_equal_lower_node(_Link_type __z);
template<typename _NodeGen>
_Link_type
_M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
template<typename _NodeGen>
_Link_type
_M_copy(const _Rb_tree& __x, _NodeGen& __gen)
{
_Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
_M_leftmost() = _S_minimum(__root);
_M_rightmost() = _S_maximum(__root);
_M_impl._M_node_count = __x._M_impl._M_node_count;
return __root;
}
_Link_type
_M_copy(const _Rb_tree& __x)
{
_Alloc_node __an(*this);
return _M_copy(__x, __an);
}
void
_M_erase(_Link_type __x);
iterator
_M_lower_bound(_Link_type __x, _Base_ptr __y,
const _Key& __k);
const_iterator
_M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
const _Key& __k) const;
iterator
_M_upper_bound(_Link_type __x, _Base_ptr __y,
const _Key& __k);
const_iterator
_M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
const _Key& __k) const;
public:
_Rb_tree() = default;
_Rb_tree(const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_impl(__comp, _Node_allocator(__a)) { }
_Rb_tree(const _Rb_tree& __x)
: _M_impl(__x._M_impl)
{
if (__x._M_root() != 0)
_M_root() = _M_copy(__x);
}
_Rb_tree(const allocator_type& __a)
: _M_impl(_Compare(), _Node_allocator(__a))
{ }
_Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
: _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
{
if (__x._M_root() != nullptr)
_M_root() = _M_copy(__x);
}
_Rb_tree(_Rb_tree&&) = default;
_Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
: _Rb_tree(std::move(__x), _Node_allocator(__a))
{ }
_Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
~_Rb_tree() _GLIBCXX_NOEXCEPT
{ _M_erase(_M_begin()); }
_Rb_tree&
operator=(const _Rb_tree& __x);
// 存取方法
_Compare
key_comp() const
{ return _M_impl._M_key_compare; }
//Rb-tree的头节点为最左节点
iterator
begin() _GLIBCXX_NOEXCEPT
{ return iterator(this->_M_impl._M_header._M_left); }
const_iterator
begin() const _GLIBCXX_NOEXCEPT
{ return const_iterator(this->_M_impl._M_header._M_left); }
iterator
end() _GLIBCXX_NOEXCEPT
{ return iterator(&this->_M_impl._M_header); }
const_iterator
end() const _GLIBCXX_NOEXCEPT
{ return const_iterator(&this->_M_impl._M_header); }
reverse_iterator
rbegin() _GLIBCXX_NOEXCEPT
{ return reverse_iterator(end()); }
const_reverse_iterator
rbegin() const _GLIBCXX_NOEXCEPT
{ return const_reverse_iterator(end()); }
reverse_iterator
rend() _GLIBCXX_NOEXCEPT
{ return reverse_iterator(begin()); }
const_reverse_iterator
rend() const _GLIBCXX_NOEXCEPT
{ return const_reverse_iterator(begin()); }
bool
empty() const _GLIBCXX_NOEXCEPT
{ return _M_impl._M_node_count == 0; }
size_type
size() const _GLIBCXX_NOEXCEPT
{ return _M_impl._M_node_count; }
size_type
max_size() const _GLIBCXX_NOEXCEPT
{ return _Alloc_traits::max_size(_M_get_Node_allocator()); }
void
swap(_Rb_tree& __t)
_GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
// Insert分为允许节点重复/不允许重复两类方法
#if __cplusplus >= 201103L
template<typename _Arg>
pair<iterator, bool>
_M_insert_unique(_Arg&& __x);
template<typename _Arg>
iterator
_M_insert_equal(_Arg&& __x);
template<typename _Arg, typename _NodeGen>
iterator
_M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
template<typename _Arg>
iterator
_M_insert_unique_(const_iterator __pos, _Arg&& __x)
{
_Alloc_node __an(*this);
return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
}
template<typename _Arg, typename _NodeGen>
iterator
_M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
template<typename _Arg>
iterator
_M_insert_equal_(const_iterator __pos, _Arg&& __x)
{
_Alloc_node __an(*this);
return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
}
template<typename... _Args>
pair<iterator, bool>
_M_emplace_unique(_Args&&... __args);
template<typename... _Args>
iterator
_M_emplace_equal(_Args&&... __args);
template<typename... _Args>
iterator
_M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
template<typename... _Args>
iterator
_M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
template<typename _InputIterator>
void
_M_insert_unique(_InputIterator __first, _InputIterator __last);
template<typename _InputIterator>
void
_M_insert_equal(_InputIterator __first, _InputIterator __last);
private:
void
_M_erase_aux(const_iterator __position);
void
_M_erase_aux(const_iterator __first, const_iterator __last);
public:
_GLIBCXX_ABI_TAG_CXX11
iterator
erase(const_iterator __position)
{
__glibcxx_assert(__position != end());
const_iterator __result = __position;
++__result;
_M_erase_aux(__position);
return __result._M_const_cast();
}
_GLIBCXX_ABI_TAG_CXX11
iterator
erase(iterator __position)
{
__glibcxx_assert(__position != end());
iterator __result = __position;
++__result;
_M_erase_aux(__position);
return __result;
}
size_type
erase(const key_type& __x);
_GLIBCXX_ABI_TAG_CXX11
iterator
erase(const_iterator __first, const_iterator __last)
{
_M_erase_aux(__first, __last);
return __last._M_const_cast();
}
void
erase(const key_type* __first, const key_type* __last);
void
clear() _GLIBCXX_NOEXCEPT
{
_M_erase(_M_begin());
_M_impl._M_reset();
}
// Set operations.
iterator
find(const key_type& __k);
const_iterator
find(const key_type& __k) const;
size_type
count(const key_type& __k) const;
iterator
lower_bound(const key_type& __k)
{ return _M_lower_bound(_M_begin(), _M_end(), __k); }
const_iterator
lower_bound(const key_type& __k) const
{ return _M_lower_bound(_M_begin(), _M_end(), __k); }
iterator
upper_bound(const key_type& __k)
{ return _M_upper_bound(_M_begin(), _M_end(), __k); }
const_iterator
upper_bound(const key_type& __k) const
{ return _M_upper_bound(_M_begin(), _M_end(), __k); }
pair<iterator, iterator>
equal_range(const key_type& __k);
pair<const_iterator, const_iterator>
equal_range(const key_type& __k) const;
template<typename _Kt,
typename _Req =
typename __has_is_transparent<_Compare, _Kt>::type>
iterator
_M_find_tr(const _Kt& __k)
{
const _Rb_tree* __const_this = this;
return __const_this->_M_find_tr(__k)._M_const_cast();
}
template<typename _Kt,
typename _Req =
typename __has_is_transparent<_Compare, _Kt>::type>
const_iterator
_M_find_tr(const _Kt& __k) const
{
auto __j = _M_lower_bound_tr(__k);
if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
__j = end();
return __j;
}
template<typename _Kt,
typename _Req =
typename __has_is_transparent<_Compare, _Kt>::type>
size_type
_M_count_tr(const _Kt& __k) const
{
auto __p = _M_equal_range_tr(__k);
return std::distance(__p.first, __p.second);
}
template<typename _Kt,
typename _Req =
typename __has_is_transparent<_Compare, _Kt>::type>
iterator
_M_lower_bound_tr(const _Kt& __k)
{
const _Rb_tree* __const_this = this;
return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
}
template<typename _Kt,
typename _Req =
typename __has_is_transparent<_Compare, _Kt>::type>
const_iterator
_M_lower_bound_tr(const _Kt& __k) const
{
auto __x = _M_begin();
auto __y = _M_end();
while (__x != 0)
if (!_M_impl._M_key_compare(_S_key(__x), __k))
{
__y = __x;
__x = _S_left(__x);
}
else
__x = _S_right(__x);
return const_iterator(__y);
}
template<typename _Kt,
typename _Req =
typename __has_is_transparent<_Compare, _Kt>::type>
iterator
_M_upper_bound_tr(const _Kt& __k)
{
const _Rb_tree* __const_this = this;
return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
}
template<typename _Kt,
typename _Req =
typename __has_is_transparent<_Compare, _Kt>::type>
const_iterator
_M_upper_bound_tr(const _Kt& __k) const
{
auto __x = _M_begin();
auto __y = _M_end();
while (__x != 0)
if (_M_impl._M_key_compare(__k, _S_key(__x)))
{
__y = __x;
__x = _S_left(__x);
}
else
__x = _S_right(__x);
return const_iterator(__y);
}
template<typename _Kt,
typename _Req =
typename __has_is_transparent<_Compare, _Kt>::type>
pair<iterator, iterator>
_M_equal_range_tr(const _Kt& __k)
{
const _Rb_tree* __const_this = this;
auto __ret = __const_this->_M_equal_range_tr(__k);
return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
}
template<typename _Kt,
typename _Req =
typename __has_is_transparent<_Compare, _Kt>::type>
pair<const_iterator, const_iterator>
_M_equal_range_tr(const _Kt& __k) const
{
auto __low = _M_lower_bound_tr(__k);
auto __high = __low;
auto& __cmp = _M_impl._M_key_compare;
while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
++__high;
return { __low, __high };
}
bool
__rb_verify() const;
_Rb_tree&
operator=(_Rb_tree&&)
noexcept(_Alloc_traits::_S_nothrow_move()
&& is_nothrow_move_assignable<_Compare>::value);
template<typename _Iterator>
void
_M_assign_unique(_Iterator, _Iterator);
template<typename _Iterator>
void
_M_assign_equal(_Iterator, _Iterator);
private:
void
_M_move_data(_Rb_tree& __x, std::true_type)
{ _M_impl._M_move_data(__x._M_impl); }
void
_M_move_data(_Rb_tree&, std::false_type);
void
_M_move_assign(_Rb_tree&, std::true_type);
void
_M_move_assign(_Rb_tree&, std::false_type);
#endif
};
nst_this = this;
auto __ret = __const_this->_M_equal_range_tr(__k);
return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
}
template<typename _Kt,
typename _Req =
typename __has_is_transparent<_Compare, _Kt>::type>
pair<const_iterator, const_iterator>
_M_equal_range_tr(const _Kt& __k) const
{
auto __low = _M_lower_bound_tr(__k);
auto __high = __low;
auto& __cmp = _M_impl._M_key_compare;
while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
++__high;
return { __low, __high };
}
bool
__rb_verify() const;
_Rb_tree&
operator=(_Rb_tree&&)
noexcept(_Alloc_traits::_S_nothrow_move()
&& is_nothrow_move_assignable<_Compare>::value);
template<typename _Iterator>
void
_M_assign_unique(_Iterator, _Iterator);
template<typename _Iterator>
void
_M_assign_equal(_Iterator, _Iterator);
private:
void
_M_move_data(_Rb_tree& __x, std::true_type)
{ _M_impl._M_move_data(__x._M_impl); }
void
_M_move_data(_Rb_tree&, std::false_type);
void
_M_move_assign(_Rb_tree&, std::true_type);
void
_M_move_assign(_Rb_tree&, std::false_type);
#endif
};