首页 > 代码库 > 《STL源码剖析》学习笔记系列之五——关联式容器(1)

《STL源码剖析》学习笔记系列之五——关联式容器(1)

RB-tree(红黑树)

1.1简介

     RB-tree属于二叉搜索树,即节点的键值一定大于其左孩子节点的键值,小于其右孩子节点的键值。RB-tree还有以下四个特征:

1、         每个节点非黑即红。

2、         根节点为黑色。

3、         如果节点为红,其子节点必须为黑。

4、         任一节点至NULL(即尾端)的任何路径,所含黑节点数必须相同。

由以上规则可知,新增的节点必须为红,且新增节点的父节点必须为黑。若插入的新节点后,不符合上述条件,则需要对树进行调整,使之符合RB-tree的条件。如下图所示:

 

1.2 节点数据结构

     RB-tree节点和其迭代器均分为两层,均有一个基类和子类。节点代码如下:

typedef bool _rb_tree_color_type;

const _rb_tree_color_typen _rb_tree_red=false;

const _rb_tree_color_typen _rb_tree_black=true;

struct _rb_tree_node_base

{

       typedef _rb_tree_color_typecolor_type;

       typedef _rb_tree_node_base*base_ptr;

       color_type color;

       base_ptr parent;

       base_ptr left;

       base_ptr right;

}

 

template<class value>

struct _rb_tree_node:public _rb_tree_node_base

{

       typedef_rb_tree_node<value>* link_type;

       value value_field;

}

 

RB-tree一个非常具有特色的地方就是其头结点和根节点,两者互为父子节点。如下图所示:


1.3 基本函数方法

RB-tree主要的操作为插入、删除、查找。其中插入有两种情况,区别在于是否允许相同键值。插入的同时存在树形的调整,左旋和右旋操作。

1、Insert_unique(): 运算插入操作,节点键值不允许重复。

2、Insert_equal(): 运算插入操作,节点键值允许重复。

3、_rb_tree_rebalance(): 重新令树形平衡,改变颜色及旋转树形。

4、_rb_tree_rotate_left()\_rb_tree_rotate_right():左旋函数和右旋函数。

5、leftmost(): 返回最左边的元素,树中键值最小的元素,header->left

6、rightmost():返回最右边的元素,树中键值最大的元素,header->right

 

1.4、set\multiset

    set和multiset均采用RB-tree作为底层数据结构,且都采用RB-tree的相关接口函数实现自己的功能。另外两者有自动排序功能。。键值和实值相同。

    两者唯一的区别是:set插入元素的操作采用底层机制RB-tree的insert_unique(),而后者采用insert_equal()。

1.5、map\multimap

     map和 multimap均采用RB-tree作为底层数据结构,且都采用RB-tree的相关接口函数实现自己的功能。另外两者有自动排序功能。默认为递增排序。键值和实值不相同。

    两者唯一的区别是: map插入元素的操作采用底层机制RB-tree的insert_unique(),而后者采用insert_equal()。

《STL源码剖析》学习笔记系列之五——关联式容器(1)