1、红黑树介绍

关联容器都有一个key（键）和一个value（值）。当元素被插入到关联式容器中时，内部结构依照其键值的大小，以特定的规则将元素放到合适的位置（实现查找算法吧）。
一般关联时容器内部结构是一个平衡二叉树，用于在恶劣的环境下获得良好的搜寻效率。平衡二叉树的实现有：AVL-tree、RB-tree、AA-tree。用的最广的就是RB-tree，不论是在Nginx还是Linux内核任务调度，都使用广泛，所以在STL中也不例外。

关联式容器分为set(集合)和map（映射）两大类，以及衍生出来的multiset（多键集合）和multimap（多键映射）。这些容器都是通过红黑树实现。所以这节就详细讲讲STL里面各种树的实现。

关于树的概念以及理论请查看算法

平衡二叉搜索树：
AVL-Tree：保证任何节点的左右子树高度相差最大1。

RB-Tree：

红黑树的实现超级复杂，这里看起来真的不容易，先放过去，后面需要看的时候，再详细看看，先不着急哦。重点讲解红黑树应该如何使用以及代码架构。红黑树通过迭代器从头到尾遍历，便可以提供排序操作。不应该通过红黑树的迭代器修改key值。红黑树是通过比较key建成的平衡二叉树，所以不允许随意更改key值，但是可以修改节点里面对应的data值，这就是为set和map提供了思路。

2、红黑树迭代器

所谓迭代器，就是提供一种遍历容器内部元素的方法，在内存连续的容器内指针就是天然的迭代器，因为天然支持++、– 、+= 、== 、!=等操作。但是红黑树的迭代器不能直接使用指针，因为其节点在内存中分配是不连续的。那么如何制造一个类，使得也可以提供如同天然指针的操作呢？那么必然就是定义一个对应的类，然后将上述相应的操作符重载，这就是所谓的迭代器模式了，红黑树也是如此的。
红黑树迭代器使用的两层，这真的是没有一点必要，何必这样设计了，通过一个迭代器重载不就可以了吗？估计是为了简单一点吧。
第一层：
这是基本迭代器，注意里面仅仅含有一个变量node指向__rb_tree_node_base。
因为二叉树里面是排好序的，所以increment使得node指向红黑树中比当前key值大一个的节点，decrement则是使得node指向红黑树中比当前key值小一个的节点

struct __rb_tree_base_iterator
{
  typedef __rb_tree_node_base::base_ptr base_ptr;//指向一个__rb_tree_node_base
  typedef bidirectional_iterator_tag iterator_category;
  typedef ptrdiff_t difference_type;
  base_ptr node;//指向一个__rb_tree_node_base
  void increment();//找到比node大的第一个节点
  void decrement();//找到比node小的第一个节点
};  

第二层迭代器：
继承了第一层里面的方法，然后实现了操作符重载，使得红黑树迭代器支持如同天然指针的一样的操作。例如通过ite++操作符遍历红黑树，就将key值从小到大对应着遍历出来。

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_node指针定义

  __rb_tree_iterator() {}//构造函数
  __rb_tree_iterator(link_type x) { node = x; }//这里有蹊跷，设计继承和基类之间的关系，父类指针给了基类会产生什么情况？编译器自动转换，不需要强制
  __rb_tree_iterator(const iterator& it) { node = it.node; }

  //相当于指向结构体的成员
  reference operator*() const { return link_type(node)->value_field; }//link_type(node)调用__rb_tree_node的构造函数，基类转换成父类必须强制转换成父类
  pointer operator->() const { return &(operator*()); }
  self& operator++() { increment(); return *this; }//++ite,increment()将node修改为大一点的节点指针，返回引用
  self operator++(int) {//ite++
    self tmp = *this;//返回__rb_tree_iterator对象，迭代器里面有成员支持对应的操作。
    increment();
    return tmp;
  }    
  self& operator--() { decrement(); return *this; }//--ite
  self operator--(int) {//ite--
    self tmp = *this;
    decrement();
    return tmp;
  }
};  

3、红黑树数据结构

对应与迭代器，也有两层数据结构，这直接写一层不就得了，还要写两层，真是有病哦。具体不清楚为啥要写两层，但是咱们可以来剖析。
第一层数据结构：
包含父子节点以及颜色信息，包含求最大和最小值的方法而已。

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; //父节点，RB树必须知道父节点
  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;
  }
};

第二层数据结构：
继承了第一层，并添加了value_field数据域这个信息，当然这里使用的都是模板，当时候，客户存储的数据都放在value_field中。

template <class Value>//一个节点定义，包含__rb_tree_node_base和value_field
struct __rb_tree_node : public __rb_tree_node_base
{
  typedef __rb_tree_node<Value>* link_type;//一个__rb_tree_node指针定义
  Value value_field;//节点值
};

下图是迭代器和节点之间的对应关系。迭代器里面仅仅需要指向节点的指针，加上实现自增、自减操作符即可。很容易。

4、红黑树模板类

模板类，具体搞清楚红黑树的数据结构，以及内部模板参数应该如何设定，里面的具体一些插入、旋转等等实现红黑树的操作没必要去看。
1、Key是键的类型。
2、Value是键和值的合体类型。一般节点里面有键和值。红黑树里面将键和值合并成一个Value。
3、KeyOfValue：告诉如何从Value中拿出key，这通常是一个仿函数。
4、Compare：因为插入和查找都是通过比较key的，所以必须红黑树如何比较key。
5、Alloc：内存分配器，通常使用默认内存分配器。
这几个参数重点搞清楚Key和Value的区别。

6、header相当于指向红黑树的头节点，此头节点里面存储了最左节点，最右节点，以及红黑树根节点，所以仅仅需要这一个节点即可管理一颗红黑树。
7、node_count记录红黑树中节点的个数。
8、key_compare定义一个仿函数对象，通过函数调用来比较对应的键值。
下图显示了header的使用方法，一颗红黑树，通过一个header管理即可。

至于内部一些插入，旋转的方法，我们暂时先不管。

/*
Key是键的类型。 
Value是键和值的合体类型
KeyOfValue：告诉如何从Value中拿出key。
Compare：如何比较key。
Alloc：内存分配器
*/  
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:
  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 __rb_tree_iterator<value_type, reference, pointer> iterator;//迭代器定义
  typedef __rb_tree_iterator<value_type, const_reference, const_pointer> 
          const_iterator;//常量迭代器定义  
protected:
  link_type get_node() { return rb_tree_node_allocator::allocate(); }//分配一个节点内存
  void put_node(link_type p) { rb_tree_node_allocator::deallocate(p); }//释放一个节点内存
  link_type create_node(const value_type& x) {//在内存上面构造节点
    link_type tmp = get_node();
    __STL_TRY {
      construct(&tmp->value_field, x);
    }
    __STL_UNWIND(put_node(tmp));
    return tmp;
  }

  link_type clone_node(link_type x) {//克隆一个节点，值和色
    link_type tmp = create_node(x->value_field);
    tmp->color = x->color;
    tmp->left = 0;
    tmp->right = 0;
    return tmp;
  }

  void destroy_node(link_type p) {//删除一个节点，释放内存，析构函数。
    destroy(&p->value_field);
    put_node(p);
  }

protected:
  //类中只有三个数据表现自己
  size_type node_count; //记录数节点数量
  link_type header;     //实现一个技巧
  Compare key_compare;  //节点间的键值大小比较函数，仿函数，也就是仿函数
  //类数据就这个三个。
  //4 + 4 + 1 = 9 --->124字节对齐
  //仿函数为空，默认都是1字节。 
  .............  
}

4、红黑树几个重要方法

iterator begin() { return leftmost(); }//RB树的起头为最左节点（指向数值最小的节点），类里面含有一个起始迭代器和结束结束迭代器，用来管理树
iterator end() { return header; }//RB树的终点，最右边节点（指向数值最大的节点），头结点使用，使其实现左闭右开的用法。

  //将x插入到RB-tree中（保持节点key值独一无二），返回一个pair对象，里面存储对应迭代器和成功与否。
 pair<iterator,bool> insert_unique(const value_type& x);

 //key值可以重复
  //将x插入到RB-tree中（允许节点值重复），返回插入的新节点的迭代器。
 iterator insert_equal(const value_type& x);

使用红黑树demo

#include <bits/stl_tree.h>
int main(void)
{
    _Rb_tree<int , int , _Identity<int> , less<int> > itree;
    cout << itree.empty() << endl;//1
    cout << itree.size() << endl;//0

    itree._M_insert_unique(3);
    itree._M_insert_unique(8);
    itree._M_insert_unique(5);
    itree._M_insert_unique(9);
    itree._M_insert_unique(13);
    itree._M_insert_unique(5);//没有作用，因为unique插入

    cout << itree.empty() << endl;//0
    cout << itree.size() << endl;//5
    cout << itree.count(5);//1 找出红黑树中节点为5的个数

    itree._M_insert_equal(5);
    itree._M_insert_equal(5);

    cout << itree.size() << endl;//7
    cout << itree.count(5) << endl;//3 找出红黑树中节点为5的个数

注意使用红黑树需要传递5个参数进去，_Rb_tree<int , int , _Identity<int> , less<int> >，第一个为int表示我的键是int类型，第二个也为int表示我的key和data合起来也是int，那么也就是key就是data，这个树里面没有存储数据。第三个告诉红黑树如何从value取出key，这个函数就是直接返回键。第四个是如何比较键值，第五个采用默认参数。

template <class T>
struct identity : public unary_function<T, T> {
  const T& operator()(const T& x) const { return x; }
};//同样的，直接返回x