STL之tree的实现详解

浅浅的花香味﹌ 2022-05-29 05:23 199阅读 0赞

# 1、红黑树介绍 #

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

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

[关于树的概念以及理论请查看算法][Link 1]

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

RB-Tree：  
![这里写图片描述][Image 1]  
红黑树的实现超级复杂，这里看起来真的不容易，先放过去，后面需要看的时候，再详细看看，先不着急哦。重点讲解红黑树应该如何使用以及代码架构。红黑树通过迭代器从头到尾遍历，便可以提供排序操作。不应该通过红黑树的迭代器修改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;//节点值
    };

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

# 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管理即可。  
![这里写图片描述][70 1]  
至于内部一些插入，旋转的方法，我们暂时先不管。

/* 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

[Image 1]: 
[Link 1]: http://blog.csdn.net/u010710458/article/details/79445627
[70]: /images/20220529/f232f9c2fbc543cd83df52e3153d2b67.png
[70 1]: /images/20220529/de9da10c029348f58a13e0a945bc044c.png