RB-tree

前言

红黑树是一颗非严格均衡的二叉树, 它的平衡性并没有 AVL 树那么好, 但是其在调整树结构时所需要的调整的次数是小于 AVL 的, 所以对于频繁的插入删除等操作上是由于 AVL 树. 如果没有了解过红黑树的话, 建议先去看一下

红黑树(一)之 原理和算法详细介绍 , 否则对于下面的内容理解起来将会较为困难

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑节点的定义

1
2
3
4
// 红黑定义
typedef bool __rb_tree_color_type;
const __rb_tree_color_type __rb_tree_red = false;	
const __rb_tree_color_type __rb_tree_black = true;

下面将 RB-tree 分为如下几个部分进行分析

  • 基本结构
  • 调整红黑树结构以及颜色的策略
  • RB-tree 的插入 删除 以及查找

RB-tree 节点以及迭代器结构

RB-tree 的节点分为两部分, 通过 __rb_tree_node_base 来设置指针, __rb_tree_node 通过继承的方式来添加节点数据, 来实现一个 RB-tree 节点的功能

__rb_tree_node_base

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct __rb_tree_node_base
{
  typedef __rb_tree_color_type color_type;	
  typedef __rb_tree_node_base* base_ptr;	

  color_type color; 	// 定义节点颜色
  base_ptr parent;		// 定义父节点
  base_ptr left;		// 定义左孩子
  base_ptr right;		// 定义右孩子

    // 查找以当前节点为根的子树的最小节点 
  static base_ptr minimum(base_ptr x)
  {
    while (x->left != 0) x = x->left;
    return x;
  }

    // 查找最大节点
  static base_ptr maximum(base_ptr x)
  {
    while (x->right != 0) x = x->right;
    return x;
  }
};

__rb_tree_node

1
2
3
4
5
6
7
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
  typedef __rb_tree_node<Value>* link_type;
  Value value_field;
};

RB-tree 迭代器

RB-tree 迭代器属于双向迭代器, 支持前进和后退操作, 但是不具有随机访问元素的能力, 并分为 __rb_tree_base_iterator 和 __rb_tree_iterator 两部分

__rb_tree_base_iterator 基本结构

其中 __rb_tree_base_iterator 利用 increment 方法实现 ++, decrement 方法实现 - - 功能, 本质就是求出当前节点的前驱与后继

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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 node; //指向节点的元素

    //求该节点的前驱 后继操作
  void increment()
  {
      //如果右节点不为空就选择右子树中最多侧的节点作为前驱
    if (node->right != 0) {
      node = node->right;
      while (node->left != 0)
        node = node->left;
    }
    else {
        //如果右子树为空, 就寻找该节点的父节点
      base_ptr y = node->parent;
      // 如果该节点是父节点的右孩子就继续往上找, 直到y节点是父节点的左孩子
      while (node == y->right) {
        node = y;
        y = y->parent;
      }
      if (node->right != y)
        node = y;
    }
  }

    //求当前节点后继
  void decrement()
  {
     //该种情况为 node == header 时也即 end() 时出现
    if (node->color == __rb_tree_red &&
        node->parent->parent == node)
      node = node->right;
    else if (node->left != 0) {
        //如果左子树不为空, 就找左子树的最右侧节点
      base_ptr y = node->left;
      while (y->right != 0)
        y = y->right;
      node = y;
    }
    else {
        //找出父节点
      base_ptr y = node->parent;
     // 如果当前 node 是 y 节点的左孩子, 那么就一直向上找到第一个非父亲节左孩子的节点
      while (node == y->left) {
        node = y;
        y = y->parent;
      }
      node = y;
    }
  }
};

__rb_tree_iterator 迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator	// 继承__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) { node = x; }	// 初始化node节点
  __rb_tree_iterator(const iterator& it) { node = it.node; }	// 初始化node节点

	// 重载指针
  reference operator*() const { return link_type(node)->value_field; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

	// 重载++与--操作, 调用 increment 和 decrement 方法
  self& operator++() { increment(); return *this; }
  self operator++(int) {
    self tmp = *this;
    increment();
    return tmp;
  }
    
  self& operator--() { decrement(); return *this; }
  self operator--(int) {
    self tmp = *this;
    decrement();
    return tmp;
  }
};

重载操作符

1
2
3
4
5
6
7
8
9
// ==与!= 比较两个tree的node是相同
inline bool operator==(const __rb_tree_base_iterator& x,
                       const __rb_tree_base_iterator& y) {
  return x.node == y.node;
}
inline bool operator!=(const __rb_tree_base_iterator& x,
                       const __rb_tree_base_iterator& y) {
  return x.node != y.node;
}

RB-tree 的迭代器也提供了 traits 编程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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 */

红黑树调整结构以及节点颜色策略

旋转操作

image-20220303214005392

由于左右旋转的方式是基本相同的, 所以这里只对右旋转进行分析

观察上图, 当对一个节点进行右旋转的时候, 需要以下几步

  1. 若 A 节点的左孩子不为空, 则将A 的左孩子指向自己左孩子的右孩子
  2. 将 原来 A 左孩子(B) 的右孩子的父亲指向 A 的左孩子
  3. 将之前左孩子(B) 的右孩子指向 A 节点
  4. 将 A 之前左孩子(B) 的父亲节点指向 A 的父亲节点
  5. A 节点的父亲节点重新指向远左孩子(B)

右旋转代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
inline void 
__rb_tree_rotate_right(__rb_tree_node_base* x, __rb_tree_node_base*& root)
{
    //y 为 x 的左孩子节点
  __rb_tree_node_base* y = x->left;
    // x 的左孩子节点指向 y 的右孩子节点
  x->left = y->right;
    // 如何 y 的右孩子节点不为 0 就将其父节点指向 x
  if (y->right != 0)
    y->right->parent = x;
    //y 的父亲节点指向 x 的父亲节点
  y->parent = x->parent;

    //如果旋转的是根节点, 那么 y 就作为新的根节点
  if (x == root)
    root = y;
    // x 作为父节点的右孩子, x 的父亲节点的右孩子节点指向 y
  else if (x == x->parent->right)
     // x 的父节点的右孩子节点指向 y
    x->parent->right = y;
  else
      //否则 x 的父亲节点的左孩子节点指向 y
    x->parent->left = y;
    // y 的右孩子节点指向 x
  y->right = x;
    // x 的父亲节点指向 y
  x->parent = y;
}

调整红黑树节点颜色

注: 该部分图片都引用自开头提供的文章链接

只有在添加和删除红黑树节点时才需要对红黑树的节点颜色进行调整

添加

这里只讨论添加完成后如何调整颜色, 对于插入操作会在分析删除插入以及查询时进行分析

首先规定, 当插入一个节点后, 给新插入节点着色为红色, 然后调整红黑树来使其依旧满足所有性质

对于新插入节点后的调整, 有下面几种情况:

  1. 当前节点的父亲节点为红色, 且当前节点的叔叔节点也是红色

处理策略:

​ Ⅰ 将父亲节点变为黑色

​ Ⅱ 将叔叔节点变为黑色

​ Ⅲ 将祖父节点变为红色

​ Ⅳ 将祖父节点设置为当前节点, 并对新的当前节点进行操作

case 1

  1. 当前节点以及父亲节点为红色, 叔叔节点为黑色且当前节点为父节点的右儿子

    处理策略

    ​ Ⅰ 将父节点作为当前节点, 对父节点进行左旋操作

    ​ Ⅱ 将新的当前节点进行左旋

    case2

  2. 当前节点以及父亲节点为红色, 叔叔节点为黑色且当前节点为父节点的左儿子

    处理策略:

    ​ Ⅰ 将父亲节点设置为黑色

    ​ Ⅱ 将当前节点的祖父节点设置为红色

    ​ Ⅲ 将祖父节点进行右旋

    case 3

通过上图可以发现其实 Case 2 后会转化为 Case 3 的情况, 所以在源码实现时可以将 Case2 和 Case3 合并起来, 事实上源码也是这样进行操作的, 并且如果父节点是祖父节点的右儿子, 操作步骤是一样的, 不过有关旋转的方向反一下就可以. 在最后由于旋转到根节点时, 根节点可能会是红色, 所以需要判断一下根节点是不是红色, 如果是红色, 那么就将根节点变为黑色

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
inline void 
__rb_tree_rebalance(__rb_tree_node_base* x, __rb_tree_node_base*& root)
{
  x->color = __rb_tree_red;
  while (x != root && x->parent->color == __rb_tree_red) {
    if (x->parent == x->parent->parent->left) {
      __rb_tree_node_base* y = x->parent->parent->right;
      if (y && y->color == __rb_tree_red) {
        x->parent->color = __rb_tree_black;
        y->color = __rb_tree_black;
        x->parent->parent->color = __rb_tree_red;
        x = x->parent->parent;
      }
      else { // 如果不存在 y 也说明 y 是黑色 (默认空节点为黑色节点)
        if (x == x->parent->right) {
          x = x->parent;
          __rb_tree_rotate_left(x, root);
        }
        x->parent->color = __rb_tree_black;
        x->parent->parent->color = __rb_tree_red;
        __rb_tree_rotate_right(x->parent->parent, root);
      }
    }
    else {
      __rb_tree_node_base* y = x->parent->parent->left;
      if (y && y->color == __rb_tree_red) {
        x->parent->color = __rb_tree_black;
        y->color = __rb_tree_black;
        x->parent->parent->color = __rb_tree_red;
        x = x->parent->parent;
      }
      else {
        if (x == x->parent->left) {
          x = x->parent;
          __rb_tree_rotate_right(x, root);
        }
        x->parent->color = __rb_tree_black;
        x->parent->parent->color = __rb_tree_red;
        __rb_tree_rotate_left(x->parent->parent, root);
      }
    }
  }
  root->color = __rb_tree_black;
}

删除

由于删除操作和调整操作是在一起实现的, 所以这里就一起进行分析

首先看删除节点, 删除就和其他 BinarySearchTree 一样

  1. 如果是最多只有一个节点, 直接删除该节点, 并将子节点接到其在父节点原来的位置上
  2. 如果有两个子节点, 则找到该节点的后继, 并利用后继去替换当前要删除的节点, 这时问题转化为了删除后继节点问题, 又由于后继只可能会拥有右儿子, 所以就转化为了情况1 进行删除

在删除后将进行调整红黑树的颜色

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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->left == 0)             // z has at most one non-null child. y == z.
    x = y->right;               // x might be null.
  else
    if (y->right == 0)          // z has exactly one non-null child.  y == z.
      x = y->left;              // x is not null.
    else {                      // z has two non-null children.  Set y to
      y = y->right;             //   z's successor.  x might be null.
      while (y->left != 0)
        y = y->left;
      x = y->right;
    }
    //如果是两非空子节点的情况, 此时 y 为 要删除节点的后继
    // 这里的替换其实是将 z 原来的父子节点关系全部接入到后继 y 的父子关系上, 然后再对 z 进行删除
  if (y != z) {               
      // relink y in place of z.  y is z's successor
    // 先将要删除节点的左儿子的父节点指向后继 y
    z->left->parent = y; 
    y->left = z->left;
    // 如果 y 不是要删除节点 z 的右儿子
    if (y != z->right) {
      x_parent = y->parent;
      if (x) x->parent = y->parent;
      y->parent->left = x;      // y must be a left child
      y->right = z->right;
      z->right->parent = y;
    } // 如果 y 是要删除节点 z 的右儿子
    else
       //那么就没有把 x 接给后继 y 父亲节点的需要
      x_parent = y;  
    if (root == z)
      root = y;
    else if (z->parent->left == z)
      z->parent->left = y;
    else 
      z->parent->right = y;
    y->parent = z->parent;
    __STD::swap(y->color, z->color); // 把 y 原来的颜色替换为要删除节点的颜色以保证平衡性
    y = z;
    // y now points to node to be actually deleted
  } 
  else {                        // y == z
    x_parent = y->parent;
    if (x) x->parent = y->parent;   
    if (root == z)
      root = x;
    else 
      if (z->parent->left == z)
        z->parent->left = x;
      else
        z->parent->right = x;
    if (leftmost == z) 
      if (z->right == 0)        // z->left must be null also
        leftmost = z->parent; //如果删除的是最小节点, 那么如果没有右子节点, 就说明其父节点为最小节点
    // makes leftmost == header if z == root
      else // 反之就去其原右子树中寻找最小节点, (此时右子树为要删除父亲节点的左子树)
        leftmost = __rb_tree_node_base::minimum(x);
    if (rightmost == z)  
      if (z->left == 0)         // z->right must be null also
        rightmost = z->parent;  
    // makes rightmost == header if z == root
      else                      // x == z->left
        rightmost = __rb_tree_node_base::maximum(x);
  } 
	.....
}

调整

在进行上面删除操作时, 我们发现其实 x_parent 这个变量在删除的时候并没有什么实际作用, 只是在记录一些值, 这个值在进行删除的时候确实没有什么作用, 其是用于进行调整时所使用的, 记录的实际是在后继被替换到要删除节点后其原右子节点的新父亲节点

对于调整, 我们先来回顾一下红黑树的 5 条性质

(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

当从红黑树中删除了一个节点后, 可能会违反特性 (2), (4), (5) , 所以在调整阶段, 需要解决上面的三个问题, 使得调整后的树满足红黑树的全部特性.

在看过红黑树的删除操作后, 我们知道, 在删除了节点 y 后, 其右儿子节点 x 占据原来 y 的位置, 如果删除的节点是一个黑色节点, 意味着在其他节点到这个节点的子树中, 黑色节点的数量将减一, 那么, 可以通过在该位置再次添加一个黑色, 这样就保证了 “特性(5)” 不会被破坏.

如此做, x 现在就不仅包含其原有颜色, 还多包含一个额外的黑色. 也即它的节点颜色为 “红加黑”, 或者 “黑加黑”, 其违反了 “特性(1)”

现在, 成功将问题从破坏了 特性(2), (4), (5) 转变为了破坏 特性(1), (2), (4). 而下面的调整策略 **__rb_tree_rebalance ** 的思想为: 将 x 所包含的额外的黑色沿树不断上移(即向根方向移动), 直到出现了下面的情况:

  • 情况一: x 此时为一个 “黑 + 红” 节点

    处理方式: 直接将 x 设置为黑色. 至此红黑树性质全部恢复

  • 情况二: x 是 “黑 + 黑” 节点, 且 x 是根节点.

    处理方式: 什么都不做, 结束. 此时红黑树的性质全部恢复

  • 情况三: x 是 “黑 + 黑” 节点, 且 x 不是根

    处理方式: 这种情况可以划分为 4 种情况, 但是在 RB-tree 的实现中进行了精简, 所以下面只介绍源码中的实现, 如果想了解上面的 4 种情况, 可以去文章开头提供的红黑树原理分析

    ==这里只以 x 为父节点左儿子, 右儿子的操作于左儿子的操作方向相反.== w 是 x 的兄弟节点

    1. x 是 “黑 + 黑” 节点, w 是红色节点(此时x的父节点和x的兄弟节点的子节点都是黑节点)

    处理方式:

    • 将 w 节点染为黑色
    • 将 x 的父亲节点染为红色
    • 将 x 的父亲节点进行左旋
    • 重新设置 x 的兄弟节点 w
    1. x 是 “黑 + 黑” 节点, w 是黑色节点(如果是空节点则默认黑色), w 的两个儿子都是黑色

    处理方式:

    • 将 w 染为红色, 将 x 的父亲设置为 x 节点, 也即将额外的一个黑色传递给其父亲

    注: 源码在实现中, 1, 2步骤之间没有使用else 分开, 而是 if 之后就是另一种情况的 if, 在我的浅略分析来看, 如果其中一种情况处理完后, 一定会满足下一步中的 w 节点为黑的情况, 如果不满足第一个条件, 说明w本身就是==黑色==, 所以经过第一种情况之后, w一定是黑色的, 故只需要判断其他条件即可

    1. x是 “黑+黑” 节点，w 节点是黑色, 且 w 的右儿子为空或者为红色

    处理方式:

    • 如果 w 有左儿子, 就将 w 的左儿子染为黑色
    • 将 w 染为红色
    • 对 w 进行右旋
    • 重新设置 x 的兄弟节点 w

    接下来就是上文中提到的 第四种情况 , 但是在实现中, 可能是保证了在对第三种情况处理完之后一定会处于第四种情况, 所以将其并入到第三种情况的操作之中, 这里补充一下这种情况:

    ​ x 是 “黑+黑” 节点，w 是黑色；w 的右儿子是红色的，w 的左儿子任意颜色

    • 将 w 的颜色染为 x 的父亲节点的颜色
    • 将 x 的父亲节点的颜色染为黑色
    • 如果 w 的右儿子存在, 则将其染为黑色
    • 将 x 的父节点左旋

    在执行完情况四的处理之后, 此时红黑树的性质就全部修正好, 此时退出循环就可以了(我并不能明白上面步骤的正确性… 如果有能力且有兴趣的同学可以去看一下证明, 在此我就只介绍如何进行修正操作了…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 if (y->color != __rb_tree_red) { 
    while (x != root && (x == 0 || x->color == __rb_tree_black))
      if (x == x_parent->left) {
        __rb_tree_node_base* w = x_parent->right;
        if (w->color == __rb_tree_red) {
          w->color = __rb_tree_black;
          x_parent->color = __rb_tree_red;
          __rb_tree_rotate_left(x_parent, root);
          w = x_parent->right;
        }
        if ((w->left == 0 || w->left->color == __rb_tree_black) &&
            (w->right == 0 || w->right->color == __rb_tree_black)) {
          w->color = __rb_tree_red;
          x = x_parent;
          x_parent = x_parent->parent;
        } else {
          if (w->right == 0 || w->right->color == __rb_tree_black) {
            if (w->left) w->left->color = __rb_tree_black;
            w->color = __rb_tree_red;
            __rb_tree_rotate_right(w, root);
            w = x_parent->right;
          }
          w->color = x_parent->color;
          x_parent->color = __rb_tree_black;
          if (w->right) w->right->color = __rb_tree_black;
          __rb_tree_rotate_left(x_parent, root);
          break;
        }
      } else {                  // same as above, with right <-> left.
        __rb_tree_node_base* w = x_parent->left;
        if (w->color == __rb_tree_red) {
          w->color = __rb_tree_black;
          x_parent->color = __rb_tree_red;
          __rb_tree_rotate_right(x_parent, root);
          w = x_parent->left;
        }
        if ((w->right == 0 || w->right->color == __rb_tree_black) &&
            (w->left == 0 || w->left->color == __rb_tree_black)) {
          w->color = __rb_tree_red;
          x = x_parent;
          x_parent = x_parent->parent;
        } else {
          if (w->left == 0 || w->left->color == __rb_tree_black) {
            if (w->right) w->right->color = __rb_tree_black;
            w->color = __rb_tree_red;
            __rb_tree_rotate_left(w, root);
            w = x_parent->left;
          }
          w->color = x_parent->color;
          x_parent->color = __rb_tree_black;
          if (w->left) w->left->color = __rb_tree_black;
          __rb_tree_rotate_right(x_parent, root);
          break;
        }
      }
    if (x) x->color = __rb_tree_black;
  }
  return y;
}

RB-tree

RB-tree 基本类型定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
protected:
  typedef void* void_pointer;
  typedef __rb_tree_node_base* base_ptr;	// 定义节点指针
  typedef __rb_tree_node<Value> rb_tree_node;	// 定义节点
  typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;	// 定义空间配置器
  typedef __rb_tree_color_type color_type;	
public:
	// 满足traits编程
  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;
protected:
  size_type node_count; // keeps track of size of tree
  link_type header;  	// 头节点, 不是根节点, 头节点是指向根节点
  Compare key_compare;	// 伪函数
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;
  ...
};

获取节点属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
	...
protected:
  link_type& root() const { return (link_type&) header->parent; }		// 获取根节点
  link_type& leftmost() const { return (link_type&) header->left; }		// 最小节点
  link_type& rightmost() const { return (link_type&) header->right; }	// 最大节点

	// 当前节点的左节点
	// 当前节点的右节点
  static link_type& left(link_type x) { return (link_type&)(x->left); }
  static link_type& right(link_type x) { return (link_type&)(x->right); }
    //获取父亲节点
  static link_type& parent(link_type x) { return (link_type&)(x->parent); }
    // 获取节点数据
  static reference value(link_type x) { return x->value_field; }	\
    // 从节点数据中获取 key 值
  static const Key& key(link_type x) { return KeyOfValue()(value(x)); }
    // 获取节点颜色
  static color_type& color(link_type x) { return (color_type&)(x->color); }

    // 对于传入的 base 指针的重载版
  static link_type& left(base_ptr x) { return (link_type&)(x->left); }
  static link_type& right(base_ptr x) { return (link_type&)(x->right); }
  static link_type& parent(base_ptr x) { return (link_type&)(x->parent); }
  static reference value(base_ptr x) { return ((link_type)x)->value_field; }
  static const Key& key(base_ptr x) { return KeyOfValue()(value(link_type(x)));} 
  static color_type& color(base_ptr x) { return (color_type&)(link_type(x)->color); }

	// 最小节点
  static link_type minimum(link_type x) { 
    return (link_type)  __rb_tree_node_base::minimum(x);
  }
  	// 最大节点
  static link_type maximum(link_type x) {
    return (link_type) __rb_tree_node_base::maximum(x);
  }
  
public:    
                                // accessors:
  Compare key_comp() const { return key_compare; }
  // begin() 获取的是最小节点
  iterator begin() { return leftmost(); }
  const_iterator begin() const { return leftmost(); }
  // end() 为头节点
  iterator end() { return header; }
  const_iterator end() const { return 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 node_count == 0; }		
    // 返回节点数
  size_type size() const { return node_count; }			
  size_type max_size() const { return size_type(-1); }	
  ...
};

构造析构函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
	...
public:                          // allocation/deallocation
  rb_tree(const Compare& comp = Compare())
    : node_count(0), key_compare(comp) { init(); }

  rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) : node_count(0), key_compare(x.key_compare)
  { 
    header = get_node();	
      //头节点默认为红色
    color(header) = __rb_tree_red;	
    if (x.root() == 0) {	// 如果x为根节点
      root() = 0;
      leftmost() = header;	// 左孩子指向根节点
      rightmost() = header;	// 右孩子指向根节点
    }
    else {
      __STL_TRY {
        root() = __copy(x.root(), header);
      }
      __STL_UNWIND(put_node(header));
      leftmost() = minimum(root());	// 左孩子始终指向最小的节点
      rightmost() = maximum(root());	// 右孩子始终指向最大的节点
    }
    node_count = x.node_count;
  }
  
  // 析构函数
  ~rb_tree() {
    clear();	// 清除或有节点
    put_node(header);	// 释放所有空间
  }
  ...
};

swap

RB-tree 交换只是交换了头节点, 节点数和用于比较的仿函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
	...
public:    
  void swap(rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& t) {
    __STD::swap(header, t.header);
    __STD::swap(node_count, t.node_count);
    __STD::swap(key_compare, t.key_compare);
  }
  ...
};
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);
}

重载运算符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 相等比较
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() && equal(x.begin(), x.end(), y.begin());
}

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());
}

// 重载=运算符
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();	
    node_count = 0;
    key_compare = x.key_compare;        
	//给每一个节点进行赋值
    if (x.root() == 0) {
      root() = 0;
      leftmost() = header;
      rightmost() = header;
    }
    else {
      root() = __copy(x.root(), header);
      leftmost() = minimum(root());
      rightmost() = maximum(root());
      node_count = x.node_count;
    }
  }
  return *this;
}

RB-tree 操作方法简介

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
	...
private:
  iterator __insert(base_ptr x, base_ptr y, const value_type& v);
	//将 x 为根的树赋值给, 父节点指向 p 的根的树
  link_type __copy(link_type x, link_type p);
    // 删除节点 x
  void __erase(link_type x);
    
public:
                                // insert/erase
    //只允许插入不存在的数据
  pair<iterator,bool> insert_unique(const value_type& x);
    //寻找要在哪一个节点下插入
  iterator insert_equal(const value_type& x);

    // 在 pos 处插入不重复的数据
  iterator insert_unique(iterator position, const value_type& x);
    // 在 pos 处插入可重复的数据
  iterator insert_equal(iterator position, const value_type& x);

   // 将两个迭代器之间的数据插入 unique(数据不可重复), equal(数据可以重复)
#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 */

    // 删除 pos 处的节点
  void erase(iterator position);
    // 删除值为 x 的节点
  size_type erase(const key_type& x);
    // 删除两个迭代器之间的元素
  void erase(iterator first, iterator last);
    // 重载的指针版本
  void erase(const key_type* first, const key_type* last);
     

public:
                                // set operations:
    // 查询值为 x 的节点
  iterator find(const key_type& x);
  const_iterator find(const key_type& x) const;
    // 值为 x 的节点数量
  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;
};

在这里只具体分析插入和删除的情况

插入方法

_insert(base_ptr x, base_ptr y, const Value& v)

以 y 为父节点插入值为 v 的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 插入
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(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;

    // 如果y是头节点, 将插入的节点设置为根节点
  if (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y))) {
    z = create_node(v);	
      // 左节点指向z
    left(y) = z;                // also makes leftmost() = z when y == header
      // y是头节点, 根节点就是z
    if (y == header) {
      root() = z;
      rightmost() = z;
    }
      // 如果y是最小节点, 则把z修改为最小节点
    else if (y == leftmost())
      leftmost() = z;           // maintain leftmost() pointing to min node
  }
  else {
    z = create_node(v);
    right(y) = z;
    if (y == rightmost())
      rightmost() = z;          // maintain rightmost() pointing to max node
  }
  parent(z) = y;
  left(z) = 0;
  right(z) = 0;
  __rb_tree_rebalance(z, header->parent);
	// 节点数增加 1
  ++node_count;	
  return iterator(z);	// 返回节点z迭代器
}

这个方法中的参数 x其实并没有什么实际用处, 只是为了方便函数的重载

insert_equal(const Value& v)

1
2
3
4
5
6
7
8
9
10
11
12
13
//找到要在哪一个节点下插入
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 = header;
  link_type x = root();
  while (x != 0) {
    y = x;
    x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);
  }
  return __insert(x, y, v);
}

不允许重复插入 pair<iterator, bool> insert_unique(const Value& v)

第二个参数如果为 true, 则说明插入成功, 反之则失败

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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 = header;
  link_type x = root();
  bool comp = true;
    // 找到合适的节点
  while (x != 0) {
    y = x;
    comp = key_compare(KeyOfValue()(v), key(x));
    x = comp ? left(x) : right(x);
  }
  iterator j = iterator(y);   
  if (comp)
    if (j == begin())     
      return pair<iterator,bool>(__insert(x, y, v), true);
    else
      --j;
    // 找到插入的节点是否已经存在了
  if (key_compare(key(j.node), KeyOfValue()(v)))
    return pair<iterator,bool>(__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.node == header->left) // begin()
    if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
      return __insert(position.node, position.node, v);
  // first argument just needs to be non-null 
    else
      return insert_unique(v).first;
  else if (position.node == header) // end()
    if (key_compare(key(rightmost()), KeyOfValue()(v)))
      return __insert(0, rightmost(), v);
    else
      return insert_unique(v).first;
  else {
    iterator before = position;
    --before;
    if (key_compare(key(before.node), KeyOfValue()(v))
        && key_compare(KeyOfValue()(v), key(position.node)))
      if (right(before.node) == 0)
        return __insert(0, before.node, v); 
      else
        return __insert(position.node, position.node, v);
    // first argument just needs to be non-null 
    else
      return insert_unique(v).first;
  }
}

允许重复插入 iterator insert_equal(iterator position, const Val& v)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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.node == header->left) // begin()
      // 如果树不为空, 且小于最小值, 就插入到最小值的左儿子
    if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
      return __insert(position.node, position.node, v);
  // first argument just needs to be non-null 
    else 
      return insert_equal(v);
  else if (position.node == header) // end()
      // 如果当前值大于最大值就插入到最大值的右儿子上
    if (!key_compare(KeyOfValue()(v), key(rightmost())))
      return __insert(0, rightmost(), v);
    else
      return insert_equal(v);
  else {
    iterator before = position;
    --before;
      // 如果新插入的值介于要插入节点和要插入节点前驱中间
    if (!key_compare(KeyOfValue()(v), key(before.node))
        && !key_compare(key(position.node), KeyOfValue()(v)))
        // 如果前驱的右儿子节点为空 就插入到前驱的右儿子上
      if (right(before.node) == 0)
        return __insert(0, before.node, v); 
      else
          // 否则插入到当前节点的左儿子上
        return __insert(position.node, position.node, v);
    // first argument just needs to be non-null 
    else
      return insert_equal(v);
  }
}

范围的可重复插入以及范围的不可重复插入

其本质就是重复调用 insert_unique 和 insert_equal

1
2
3
4
5
6
7
8
9
10
11
12
13
// 范围插入(可以重复)
template <class K, class V, class KoV, class Cmp, class Al> template<class II>
void rb_tree<K, V, KoV, Cmp, Al>::insert_equal(II first, II last) {
  for ( ; first != last; ++first)
    insert_equal(*first);
}

// 范围插入(不可重复)
template <class K, class V, class KoV, class Cmp, class Al> template<class II>
void rb_tree<K, V, KoV, Cmp, Al>::insert_unique(II first, II last) {
  for ( ; first != last; ++first)
    insert_unique(*first);
}

这里只列举了一部分重载方法

删除

  • 首先定义了单节点删除的方法, 其内部调用了 __rb_tree_rebalance_for_erase 来实现单节点的删除以及解决红黑树在删除后出现的染色规则被打破的问题

  • 重载了一个递归删除以 x 为根的子树的删除方法, 这个方法内部是没有调整方法的

  • 区间删除方法则是重复调用单节点删除方法来实现多节点的删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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.node,
                                                          header->parent,
                                                          header->left,
                                                          header->right);
  destroy_node(y);	// 释放空间
  --node_count;		// 节点数--
}

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__erase(link_type x) {
                                // erase without rebalancing
   // 递归删除x指向的所有节点
  while (x != 0) {
    __erase(right(x));
    link_type y = left(x);
    destroy_node(x);
    x = y;
  }
}

// 范围删除节点
// 调用erase函数
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>::size_type 
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::erase(const Key& x) {
  pair<iterator,iterator> p = equal_range(x);
  size_type n = 0;
	// 计算长度, erase进行删除
  distance(p.first, p.second, n);
  erase(p.first, p.second);
  return n;	// 返回删除的个数
}

复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 将以 x 为根的树复制 并将其根的父节点指向 p
 */
template <class K, class V, class KeyOfValue, class Compare, class Alloc>
typename rb_tree<K, V, KeyOfValue, Compare, Alloc>::link_type 
rb_tree<K, V, KeyOfValue, Compare, Alloc>::__copy(link_type x, link_type p) {
                                // structural copy.  x and p must be non-null.
  //复制当前子树的根节点为 top
  link_type top = clone_node(x);
  // 将 top 的父节点指向 p  
  top->parent = p;
 
  __STL_TRY {
    // x 的右子树存在, 就继续递归将 x 的右子树复制并将父节点指向 top
    if (x->right)
      top->right = __copy(right(x), top);
    p = top;
    // 令 x 指向其左儿子
    x = left(x);

    // 只要 x 节点存在
    while (x != 0) {
      // y 为复制当前 x 的节点
      link_type y = clone_node(x);
      // p 的左儿子指向 y, y 的父节点指向 p
      p->left = y;
      y->parent = p;
      // x的右儿子存在
      if (x->right)
        // 递归复制右儿子
        y->right = __copy(right(x), y);
      p = y;
      x = left(x);
    }
  }
  // 如果有节点分配失败就将所有的空间进行释放
  __STL_UNWIND(__erase(top));


  // 返回复制的当前子树的根节点
  return top;
}

find 查询方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 = header;        // Last node which is not less than k. 
  link_type x = root();        // Current node. 

	// 像二叉树一样通过节点比较
  while (x != 0) 
    if (!key_compare(key(x), k))
      y = x, x = left(x);
    else
      x = right(x);

  iterator j = iterator(y);   
  return (j == end() || key_compare(k, key(j.node))) ? end() : j;
}

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 = header; /* Last node which is not less than k. */
  link_type x = root(); /* Current node. */

  while (x != 0) {
    if (!key_compare(key(x), k))
      y = x, x = left(x);
    else
      x = right(x);
  }
  const_iterator j = const_iterator(y);   
  return (j == end() || key_compare(k, key(j.node))) ? end() : j;
}

count 方法, 计算 RB-tree 中 k 出现的次数

  • 首先其调用了 lower_bound(), upper_bound() 方法找到树中 k 中不小于 k 的第一个数字, 以及大于 k 的第一个数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 不小于k的最后一个节点
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 = header; /* Last node which is not less than k. */
  link_type x = root(); /* Current node. */

   // 如果当前根节点大于 k 说明 k 的前驱存在于 x 的左子树, 于是去 x 的左子树找
  while (x != 0) 
    if (!key_compare(key(x), k)) //(x >= k)
      y = x, x = left(x);
    else //(x < k)
        // 若根节点 x 小于 k 说明 k 的前驱要么是 x, 要么是位于 x 的右子树中
      x = right(x);

  return iterator(y);
}

// 大于k的最后一个节点 道理同上
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 = header; /* Last node which is greater than k. */
  link_type x = root(); /* Current node. */

   while (x != 0) 
       // (k < x) 说明大于 k 的最小值要么是 x 要么在 x 的左子树上
     if (key_compare(k, key(x)))
       y = x, x = left(x);
     else
         // (k >= x) 说明大于 k 的最小值一定在 x 的右子树上
       x = right(x);

   return iterator(y);
}
  • 利用 distance() 函数求出不小于 k 的第一个数字和大于 k 的第一个数字的距离, 它们的间距就为 k 在树中出现的次数
1
2
3
4
5
6
7
8
9
// 计算RB-tree中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;
}

计算当前节点到树根的链上的黑色节点数量

1
2
3
4
5
6
7
8
9
10
11
12
13
// 计算红黑树有多少个黑节点
inline int __black_count(__rb_tree_node_base* node, __rb_tree_node_base* root)
{
  if (node == 0)
    return 0;
  else {
    int bc = node->color == __rb_tree_black ? 1 : 0;
    if (node == root)
      return bc;
    else
      return bc + __black_count(node->parent, root);
  }
}

检查是否符合 RB-tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 检查是否符合rb-tree
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
bool 
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__rb_verify() const
{
    // 空树
  if (node_count == 0 || begin() == end())
    return node_count == 0 && begin() == end() &&
      header->left == header && header->right == header;
  
    // 最左节点到根节点的黑色节点数量为 len
  int len = __black_count(leftmost(), root());
    // 遍历每个节点
  for (const_iterator it = begin(); it != end(); ++it) {
    link_type x = (link_type) it.node;
    link_type L = left(x);
    link_type R = right(x);
	
      // 节点是红色如果子节点也是红色就不满足
    if (x->color == __rb_tree_red)
      if ((L && L->color == __rb_tree_red) ||
          (R && R->color == __rb_tree_red))
        return false;

    if (L && key_compare(key(x), key(L)))
      return false;
    if (R && key_compare(key(R), key(x)))
      return false;

    if (!L && !R && __black_count(x, root()) != len)
      return false;
  }

  if (leftmost() != __rb_tree_node_base::minimum(root()))
    return false;
  if (rightmost() != __rb_tree_node_base::maximum(root()))
    return false;

  return true;
}

总结:

本文粗略的分析了 RB-tree 的结构以及主要功能的实现, 其中 RB-tree 的主要掌握插入删除, 并且由于插入删除对红黑树带来的影响导致破坏了原红黑树的性质, 就要进行旋转和颜色调整, 其中的插入方法有可重复插入以及不可重复插入这些方法都会在后续对 set, map 等一些非关联容器中得到使用,