Rabbet

悦已者

0%

The Annotated STL Sources-4

发表于 更新于 分类于
本文字数： 14k 阅读时长 ≈ 12 分钟
STL源码剖析读书笔记-关联式容器

前言

标准的STL关联式容器set(集合)和map(映射表)两大类，在观念上它们类似于数据库(实际则还要简单):每笔数据(每个元素)都有一个键值(key)和一个实值(value)。当元素插入到关联式容器时，就会以某种特定规则将这个元素放在适当的位置。因此关联式容器没有所谓的头尾的说法，所以就没有一些push_back()、push_font()等等这样的操作。
关联式容器所包含的容器
avatar

一般而论，关联式容器的内部结构都是一个balanced binary tree(平衡二叉树)，用以寻求最高的搜索效率。当然，对于平衡二叉树来说，它也是存在许多的分支。但是其中广泛运用于STL关联式容器的底层结构的主要是RB-Tree，作为关联式容器的核心，我们很是有必要来深入探索一下它。

二叉搜索树

在了解红黑树之前，大概还需要一些基本的知识准备。树作为一种十分基础的数据结构，几乎所有的操作系统都将文件存放在树状结构。树这种数据结构也具有许多的分支，如文件压缩所采用的哈夫曼树，数据库中使用的B-Tree等。对于RB-Tree来说，它就是属于二叉搜索树中的一种。
所谓二叉树搜索树,是指一颗空树或是具有以下性质的二叉树：
  1. 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
  2. 若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
  3. 任意节点的左、右子树也分别是二叉搜索树
对于二叉树，还可以细分为平衡二叉树(Balanced binary search tree)与自平衡二叉搜索树(AVL tree)。它们都很相似，却又是十分的不同。

平衡二叉搜索树

它是一种结构平衡的二叉树,其每个节点的左右两个高度差不超过一个二叉树。可以在O(logn)时间内完成插入、删除操作。
其结构如下图所示：
avatar

自平衡二叉搜索树

AVL树是最早发明的自平衡二叉搜索树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。
AVL树插入节点时，存在四种平衡破坏的情况，这里假设最深节点为X，那么对应的情况就是：
  1. 插入点位于X的左子节点的左子树——左左
  2. 插入点位于X的左子节点的右子树——左右
  3. 插入点位于X的右子节点的左子树——右左
  4. 插入点位于X的右子树的左子树——右右

那么对应这四种情况，我们也提供了两种解决方法来修复这些插入而导致的不平衡。
首先是单旋转，它主要用于对左左与右右这两种情况的处理。
avatar
其次就是双旋转，它也就是利用两次单旋转来实现的，它主要用于对左右与右左这两种情况进行处理。
avatar

RB-Tree是另一个被广泛使用的平衡二叉搜索树,它的平衡条件虽然不同于AVL-Tree,但是也同样使用了单旋转与双旋转修正操作，这些在RB-Tree的解析中也详细解析。

RB-Tree

RB-Tree不仅是一个二叉搜索树，它还必须满足以下的规则：
  1. 每个节点的颜色非黑即红
  2. 根节点颜色必须是黑色
  3. 每个叶子节点(NULL)是黑色
  4. 如果一个节点是红色，则它的子节点必须是黑色
  5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点数

如下就是一个标准的红黑树：
avatar

节点设计

RB-Tree有红黑两种颜色，并且具有左右子节点，我们可以很容易的设计出其结构风貌。具体STL中源码中如下：
__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
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base	// 继承__rb_tree_node_base
{
  typedef __rb_tree_node<Value>* link_type;
  Value value_field;	// 定义节点数据
};

红黑树的节点设计很是巧妙，将节点与数据分开定义。这种手法与list结构很是类似，__rb_tree_node_base定义了指针，__rb_tree_node定义了继承了前者，并增加了数据，这样就形成了一个完整的节点。
节点样式如下：
avatar

迭代器设计

迭代器中increment与decrement函数主要实现的就是++与–，即迭代器中的前进与后退操作。
__rb_tree_base_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
struct __rb_tree_base_iterator
{
  typedef __rb_tree_node_base::base_ptr base_ptr;
  typedef bidirectional_iterator_tag iterator_category;	// bidirectional_iterator_tag类型的迭代器
  typedef ptrdiff_t difference_type;
  base_ptr node;	// 指针节点

    // ++核心函数
    // 节点是从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;
    }
  }

    // --核心代码
    // 节点是从node节点出发, 一直寻找左节点的右孩子, 每次找到比上次小的元素
  void decrement()
  {
      // 只有根节点, 每次--都是根节点
    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;
        // 如果当前节点是父节点的左孩子就继续寻找父节点直到不再是左孩子
      while (node == y->left) {
        node = y;
        y = y->parent;
      }
      node = y;
    }
  }
};

红黑树的迭代器，通过继承 __rb_tree_base_iterator重载++与–操作(通过调用 increment()与decrement())

构造与析构

在深入到构造之前，还需要先了解一下基本类型定义。对于红黑树来说，它也有自己的空间配置器，其中也囊括了各种类型定义，维护整棵红黑树的三笔数据node_count 记录树的大小、header这是头节点，非根节点，但是头节点指向根节点以及key_compare这个仿函数。其类型定义源码如下：

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;
  ...
};

对于红黑树来说，它的构造存在两种方式：一种是以现有的RB-Tree复制一个新的RB-Tree，另一个就是产生一棵空树，如下图所示：
avatar

元素插入与删除

在红黑树中，元素的插入与删除就要涉及到红黑树的调整了。不过对于红黑树而言，调整也就不过两种方式：左旋、右旋。那么为什么需要这些操作呢？这是由于在元素的插入与删除过程中，可能会违背红黑树的性质，因而需要它们来修复平衡。其实，如果理解左旋，右旋也就没有什么问题了，毕竟左右树是对称的。

左旋操作

对于左旋操作大致需要六个步骤，这里需要设有一个前提：这里假设x的右孩子为y，这样就可以开始了：
  Step1: 将”y的左孩子”设为”x的右孩子”,即B为x的右孩子
  Step2: 将”x”设为“左孩子的父亲”,即将B的父亲设为x
  Step3: 将 “x的父亲” 设为 “y的父亲”
  Step4: 这里需要讨论父节点的三种情况：
    Case1: 如果”x的父亲”为空节点，则将y设为根节点
    Case2: 如果x是它的父节点的左孩子，则将y设为父节点的左孩子
    Case3: 如果x是父节点的右孩子，则将y设为”x的父节点的右孩子”
  Step5: 将x设为y的左孩子
  Step6: 将x的父节点设为y
如下图所示：
avatar

右旋操作

对于右旋操作大致操作也是一样的，这里也需要设有一个前提:这里假设y的左孩子为x这样就可以开始了：
  Step1: 将 “x的右孩子” 设为 “y的左孩子”，即 将B设为y的左孩子
  Step2: 将 “y” 设为 “x的右孩子的父亲”，即 将β的父亲设为y
  Step3: 将 “y的父亲” 设为 “x的父亲”
  Step4: 这里需要讨论父节点的三种情况：
    Case1: 如果”x的父亲”为空节点，则将y设为根节点
    Case2: 如果 y是它父节点的右孩子，则将x设为“y的父节点的左孩子”
    Case3: (y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
  Step5: 将 “y” 设为 “x的右孩子”
  Step6: 将 “y的父节点” 设为 “x”
如下图所示：
avatar

元素插入

一般而言，RB-Tree可以分为三个步骤：
  Step1: 将红黑树当作二叉查找树，将节点插入
  Step2: 将插入节点着色为红色
  Step3: 通过一系列的旋转或着色操作，将其变成一棵红黑树

但是，正如之前所说，插入会导致红黑树的性质被破坏。所以对应的我们除了使用左旋或右旋外，我们还应对不符合性质的节点进行染色。
插入一个新的节点，颜色默认都是红色，这样就不会破坏性质5。当插入的新节点非红黑树的根节点，且其父节点颜色为红色，这样就会破坏性质4。这是一个基本前提，之后就是需要通过旋转与染色来修正平衡。其实这里主要就是对节点x的父节点为x祖父节点的左右子树进行一个讨论。由于树是对称的，在这里我只对当x的父节点为x祖父节点的左子树进行一个展开讨论。

  前提：节点x的父节点x->parent是其祖父节点x->parent->parent的左孩子
  情况1：若其叔叔节点y存在,且为红色
    将其父节点x->parent改变成黑色
    将其叔叔节点y改变成黑色
    将其祖父节点变成红色
    把祖父节点作为当前节点,一直上溯,继续判断是否破坏RB-Tree性质.
  情况2：x的叔叔节点y是黑色且x是一个右孩子
    则以其父节点作为旋转节点,进行一次左旋
    旋转之后,节点x变成其父节点的左孩子
  情况3：x的叔叔节点y是黑色且x是一个左孩子
    情况2，通过变换也进入了情况3
    改变其父节点x->parent颜色
    改变其祖父节点x->parent->parent颜色
    对其祖父节点进行一次右旋转
具体操作，可以见如下动图：
avatar

元素操作

在这里，仅对元素的插入与搜索进行一个深入讨论。

基本元素操作

红黑树中，它所需的基本元素有很多。其中就包括：左节点、右节点、父节点、实值、键值、颜色等，具体到源码，如下所示：

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
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; }	// 当前节点的数据
  static const Key& key(link_type x) { return KeyOfValue()(value(x)); }
  static color_type& color(link_type x) { return (color_type&)(x->color); }

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

元素插入

红黑树提供了两种插入方式：insert_unique() 与 insert_equal()。前者表示被插入的键值在整棵树中必须唯一，后者则表示被插入节点的键值可以在整棵树中可以重复。具体源码解析如下：
具体源码解析

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
75
76
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;

  if (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y))) {
    z = create_node(v);	//创建值为v的节点z
    left(y) = z;                // also makes leftmost() = z when y == header
    if (y == header) {
      root() = z;
      rightmost() = z;
    }
    else if (y == leftmost())//若y为最左节点
      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);//调整RB-Tree使其满足性质
  ++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 = header;
  link_type x = root();//从根节点开始
  while (x != 0) {//从根节点开始,往下寻找合适插入点
    y = x;
	//判断新插入节点值与当前节点x值的大小,以便判断往x的左边走还是往右边走
    x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);
  }
  return __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 = header;
  link_type x = root();//从根节点开始
  bool comp = true;
  while (x != 0) {//从根节点开始,往下寻找合适插入点
    y = x;
	//判断新插入节点值与当前节点x值的大小,以便判断往x的左边走还是往右边走
    comp = key_compare(KeyOfValue()(v), key(x));
    x = comp ? left(x) : right(x);
  }
  //离开while循环之后，y所指即为安插点的父节点，x必为叶子节点
  iterator j = iterator(y);   //令迭代器j指向插入节点之父节点y
  if (comp)
    if (j == begin()) //若插入点之父节点为最左节点
      return pair<iterator,bool>(__insert(x, y, v), true);
    else //否则(插入点之父节点不在最左节点)
      --j;//调整j
 // 小于新值（表示遇「小」，将安插于右侧）
  if (key_compare(key(j.node), KeyOfValue()(v)))
    return pair<iterator,bool>(__insert(x, y, v), true);
 //若运行到这里，表示键值有重复，不应该插入
  return pair<iterator,bool>(j, false);
}

元素搜索

作为二叉搜索树的红黑树，元素的搜索可是它的拿手好戏。以下是它的源码：

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
//查找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;
}

红黑树总结

优点：
  1. 红黑树是效率相对较高的当我们插入和删除数据相对频繁的时候
  2. 红黑树是自我平衡的所有操作的复杂度最多是O(logn)
  3. 不管怎么变化，只有红黑两个常数

缺点：
  由于红黑树并不追求高度平衡，因此搜索效率并没有AVL高

总结：实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。