Last updated：2026-10-12

STL red-black tree implementation

0.Introduction

There are two passages in the STL source code, loosely translated as follows:

The Red-black tree class in the STL is used as the underlying structure of the STL associative containers (such as set, multiset, map, multimap). The insertion and deletion methods used inside are based on the book 《Introduction to Algorithms》, but with the following two differences:

(1) The header points not only to the root, but also to the leftmost node of the red-black tree, so that begin() can be implemented in constant time; it also points to the rightmost node of the red-black tree, so that set-related generic algorithms (such as set_union and so on) can achieve linear time performance.

(2) When the node to be deleted has two children, its successor node is linked into its position rather than copied; consequently, the only invalidated iterators are those referencing the deleted node.

The above, translated into a picture, is as follows: compared with an ordinary red-black tree there is an extra header node, and it is red. An ordinary red-black tree starts at node 100 and satisfies the following five properties: - Every node is either red or black. - The root is black. - Every leaf (NULL) is black. - If a node is red, then both its children are black. - For each node, all simple paths from the node to its descendant leaves contain the same number of black nodes.

Of course, this rb_tree likewise satisfies these properties; the iterator's begin points to the red-black tree's root — that is, the header's parent — while end points to the header node.

. The ellipsis in the figure means the nodes were not all drawn — other nodes exist, hence the omission.

1.Red-black tree node base class

The red-black tree base class is very simple; a color flag is defined at the start of the file.

The base class contains pointers to itself, defining left, right, and parent respectively, plus a color flag constant; inside there are two core functions whose purpose is to obtain the minimum and maximum nodes of the red-black tree. We know that for a binary search tree, obtaining the minimum node means searching down the left subtree continuously, and the maximum means searching down the right subtree.

// 颜色标记
enum _Rb_tree_color { _S_red = false, _S_black = true };

// 基类
struct _Rb_tree_node_base
{
// typedef重命名
typedef _Rb_tree_node_base* _Base_ptr;

// 颜色
_Rb_tree_color  _M_color;
// 指向父亲
_Base_ptr       _M_parent;
// 指向左孩子
_Base_ptr       _M_left;
// 指向右孩子
_Base_ptr       _M_right;

// 求红黑树的最小节点
static _Base_ptr
_S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
    while (__x->_M_left != 0) __x = __x->_M_left;
    return __x;
}

// 求红黑树最大节点
static _Base_ptr
_S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
{
    while (__x->_M_right != 0) __x = __x->_M_right;
    return __x;
}

};

2.Red-black tree node

The red-black tree node inherits from the red-black tree base class.

template<typename _Val>
struct _Rb_tree_node : public _Rb_tree_node_base
{
    typedef _Rb_tree_node<_Value>* _Link_type;//节点指针,指向数据节点
    _Value _M_value_field;//节点数据域,即关键字
};

3.Red-black tree iterator

Inside the red-black tree iterator there is a red-black tree base class member, through which the iterator's related operations are performed. At the same time, we can tell that this iterator is a bidirectional_iterator_tag.

It also contains the typedefs needed by the traits extractor.

template<typename _Tp>
struct _Rb_tree_iterator
{
    typedef _Tp  value_type;
    typedef _Tp& reference;
    typedef _Tp* pointer;

    typedef bidirectional_iterator_tag iterator_category;
    typedef ptrdiff_t                  difference_type;

    typedef _Rb_tree_iterator<_Tp>        _Self;
    typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
    typedef _Rb_tree_node<_Tp>*           _Link_type;

    _Base_ptr _M_node;
};   

Getting the data

reference
operator*() const _GLIBCXX_NOEXCEPT
{ return *static_cast<_Link_type>(_M_node)->_M_valptr(); }

pointer
operator->() const _GLIBCXX_NOEXCEPT
{ return static_cast<_Link_type> (_M_node)->_M_valptr(); }

Overloading the ++ operator

_Self&
operator++() _GLIBCXX_NOEXCEPT
{
    _M_node = _Rb_tree_increment(_M_node);
    return *this;
}

And _Rb_tree_increment is backed by local_Rb_tree_increment, implemented as follows:

static _Rb_tree_node_base *
local_Rb_tree_increment( _Rb_tree_node_base* __x ) throw ()
{
    if ( __x->_M_right != 0 )       /* 存在右子树,那么下一个节点为右子树的最小节点 */
    {
        __x = __x->_M_right;
        while ( __x->_M_left != 0 )
            __x = __x->_M_left;
    }else  {                        
        /* 不存在右子树,那么分为两种情况：自底往上搜索,当前节点为父节点的左孩子的时候,父节点就是后继节点； */
/* 第二种情况:_x为header节点了,那么_x就是最后的后继节点. 简言之_x为最小节点且往上回溯,一直为父节点的右孩子,直到_x变为父节点,_y为其右孩子 */
        _Rb_tree_node_base *__y = __x->_M_parent;
        while ( __x == __y->_M_right )
        {
            __x = __y;
            __y = __y->_M_parent;
        }
        if ( __x->_M_right != __y )
            __x = __y;
    }
    return (__x);
}

Overloading the -- operator:

_Self&
operator--() _GLIBCXX_NOEXCEPT
{
    _M_node = _Rb_tree_decrement(_M_node);
    return *this;
}

Similarly, _Rb_tree_decrement is backed by local_Rb_tree_decrement, implemented as follows:

static _Rb_tree_node_base *
local_Rb_tree_decrement( _Rb_tree_node_base * __x )
throw ()
{
/* header节点 */
    if ( __x->_M_color ==
         _S_red
         && __x
         ->_M_parent->_M_parent == __x )
        __x = __x->_M_right;
    else if ( __x->_M_left != 0 ) /* 左节点不为空,返回左子树中最大的节点 */
    {
        _Rb_tree_node_base *__y = __x->_M_left;
        while ( __y->_M_right != 0 )
            __y = __y->_M_right;
        __x = __y;
    }else  {
/* 自底向上找到当前节点为其父节点的右孩子,那么父节点就是前驱节点 */
        _Rb_tree_node_base *__y = __x->_M_parent;
        while ( __x == __y->_M_left )
        {
            __x = __y;
            __y = __y->_M_parent;
        }
        __x = __y;
    }
    return
        (__x);
}

Overloading the == and != operators: just compare whether the node pointers are equal.

bool
operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
{ return _M_node == __x._M_node; }

bool
operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
{ return _M_node != __x._M_node; }

Another important function, counting black nodes:

unsigned int
_Rb_tree_black_count(const _Rb_tree_node_base *__node,
                     const _Rb_tree_node_base *__root) throw() {
    if (__node == 0)
        return 0;
    unsigned int __sum = 0;
    do {
        if (__node->_M_color == _S_black)
            ++__sum;
        if (__node == __root)
            break;
        __node = __node->_M_parent;
    } while (1);
    return __sum;
}

Later we will explain the most important operation, insertion.

4.Red-black tree operations

Quite importantly, inside, a pointer is declared using the node base class. There is also a _Rb_tree_impl for the red-black tree's initialization and memory-management operations. It also contains two kinds of iterators, one rbtree and the other reverse, which shows that rbegin and rend operations are supported.

template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc = allocator<_Val> >
class _Rb_tree
{

protected:
    typedef _Rb_tree_node_base*         _Base_ptr;

 template<typename _Key_compare, 
    bool _Is_pod_comparator = __is_pod(_Key_compare)>
    struct _Rb_tree_impl : public _Node_allocator
    {
      _Key_compare      _M_key_compare;
      _Rb_tree_node_base    _M_header;
      size_type         _M_node_count; // Keeps track of size of tree.

      _Rb_tree_impl()
      : _Node_allocator(), _M_key_compare(), _M_header(),
        _M_node_count(0)
      { _M_initialize(); }

      _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
      : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
        _M_node_count(0)
      { _M_initialize(); }

    private:
      void
      _M_initialize()
      {
        this->_M_header._M_color = _S_red;
        this->_M_header._M_parent = 0;
        this->_M_header._M_left = &this->_M_header;
        this->_M_header._M_right = &this->_M_header;
      }  

    };
public: 
    typedef _Rb_tree_iterator<value_type>       iterator;
    typedef std::reverse_iterator<iterator>     reverse_iterator; 
private:
_Rb_tree_impl<_Compare> _M_impl;
};

Getting the red-black tree's root, leftmost, and rightmost nodes

Back to the figure from the beginning: .

// 图中100 节点
 _Base_ptr&
_M_root() _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_parent; }

// 图中most left标记
_Base_ptr&
_M_leftmost() _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_left; }


// 图中most right标记
 _Base_ptr&
_M_rightmost() _GLIBCXX_NOEXCEPT
{ return this->_M_impl._M_header._M_right; }
 _Link_type

 // 图中begin()标记
_M_begin() _GLIBCXX_NOEXCEPT
{ return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }

// 图中end()标记
_Link_type
_M_end() _GLIBCXX_NOEXCEPT
{ return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }

Looking at the code again — isn't everything crystal clear!

5.Red-black tree insertion

5.1 The rotation process

A left rotation sets the node's right child as its parent, and the node becomes the left child of that former right child.

Just compare the figure in the source code with the code directly.

In the tree.cc source the implementing functions are local_Rb_tree_rotate_left and local_Rb_tree_rotate_right. Below we dissect the source into easier-to-understand code; see the comments for details. You will notice the function and variable names differ from the source — that is because the code below was my own implementation at the time, but it does not hinder reading the source, so it is used directly for comparison.

/**
* 当前节点的左旋转过程
* 将该节点的右节点设置为它的父节点，该节点将变成刚才右节点的左孩子
* @param _x
*/
//    _x                      _y
//  /   \     左旋转         /  \
// T1   _y   --------->   _x    T3
//     / \              /   \
//    T2 T3            T1   T2
void leftRotate(Node *_x) {
    // step1 处理_x的右孩子
    // 右节点变为_x节点的父亲节点,先保存一下右节点
    Node *_y = _x->right;
    // T2变为node的右节点
    _x->right = _y->left;
    if (NULL != _y->left)
        _y->left->parent = _x;

    // step2 处理_y与父亲节点关系
    _y->parent = _x->parent;      // 原来_x的父亲变为_y的父亲
    // 说明原来_x为root节点,此时需要将_y设为新root节点
    // 或者判断NULL == _y->parent
    if (_x == root)
        root = _y;
    else if (_x == _x->parent->left)    // 原_x的父节点的左孩子连接新节点_y
        _x->parent->left = _y;
    else // 原_x的父节点的右孩子连接新节点_y
        _x->parent->right = _y;

    // step3 处理_x与_y关系
    _y->left = _x;      // _y的左孩子为_x
    _x->parent = _y;    // _x的父亲是_y
}

Similarly, the right rotation is as follows:

//        _x                      _y
//      /   \     右旋转         /  \
//     _y    T2 ------------->  T0  _x
//    /  \                         /  \
//   T0  T1                       T1  T2
void rightRotate(Node *_x) {
    // step1 处理_x的左孩子
    // 左节点变为_x节点的父亲节点,先保存一下左节点
    Node *_y = _x->left;
    // T1变为_x的左孩子
    _x->left = _y->right;
    if (NULL != _y->right)
        _y->right->parent = _x;

    // step2 处理_y与父节点之间的关系
    // 或者判断_x->parent==NULL
    if (_x == root)
        root = _y;
    else if (_x == _x->parent->right)
        _x->parent->right = _y;
    else
        _x->parent->left = _y;

    // step3 处理_x与_y关系
    _y->right = _x;     // _y的右孩子为_x
    _x->parent = _y;    // _x的父亲是_y
}

case 1.1: The parent is red and its uncle is also red; then set the parent and uncle to black, and the grandparent to red.

case 1.2 If there is no uncle, or the uncle is black, it splits into the following two:

Situation 1.2.1: x's uncle y is black and x is a right child

Situation 1.2.2: x's uncle y is black and x is a left child

Corresponding to this in the source code:

_Rb_tree_node_base *const __y = __xpp->_M_right;    // 得到叔叔节点
if (__y && __y->_M_color == _S_red)     // case1: 叔叔节点存在，且为红色
{
    /**
        * 解决办法是：颜色翻转，父亲与叔叔的颜色都变为黑色,祖父节点变为红色,然后当前节点设为祖父，依次网上来判断是否破坏了红黑树性质
        */
    __x->_M_parent->_M_color = _S_black;    // 将其父节点改为黑色
    __y->_M_color = _S_black;               // 将其叔叔节点改为黑色
    __xpp->_M_color = _S_red;               // 将其祖父节点改为红色
    __x = __xpp;                            // 修改_x,往上回溯
} else {        // 无叔叔或者叔叔为黑色
    if (__x == __x->_M_parent->_M_right) {          // 当前节点为父亲节点的右孩子
        __x = __x->_M_parent;
        local_Rb_tree_rotate_left(__x, __root);     // 以父节点进行左旋转
    }
    // 旋转之后,节点x变成其父节点的左孩子
    __x->_M_parent->_M_color = _S_black;            // 将其父亲节点改为黑色
    __xpp->_M_color = _S_red;                       // 将其祖父节点改为红色
    local_Rb_tree_rotate_right(__xpp, __root);      // 以祖父节点右旋转
}

The other one is the symmetric process of the above:

case 2.1: The parent is red and its uncle is also red; then set the parent and uncle to black, and the grandparent to red.

case 2.2 If there is no uncle, or the uncle is black

Situation 2.2.1: x's uncle y is black and x is a left child

_Rb_tree_node_base *const __y = __xpp->_M_left; // 保存叔叔节点
if (__y && __y->_M_color == _S_red) {       // 叔叔节点存在且为红色
    __x->_M_parent->_M_color = _S_black;    // 父亲节点改为黑色
    __y->_M_color = _S_black;               // 祖父节点改为红色
    __xpp->_M_color = _S_red;
    __x = __xpp;
} else {        // 若无叔叔节点或者其叔叔节点为黑色
    if (__x == __x->_M_parent->_M_left) {   // 当前节点为父亲节点的左孩子
        __x = __x->_M_parent;
        local_Rb_tree_rotate_right(__x, __root);    // 以父节点右旋转
    }
    __x->_M_parent->_M_color = _S_black;        // 父节点置为黑色
    __xpp->_M_color = _S_red;                   // 祖父节点置为红色
    local_Rb_tree_rotate_left(__xpp, __root);   // 左旋转
}

Full dissection of _Rb_tree_insert_and_rebalance:

void
_Rb_tree_insert_and_rebalance(const bool __insert_left,
                              _Rb_tree_node_base *__x,
                              _Rb_tree_node_base *__p,
                              _Rb_tree_node_base &__header) throw() {
    _Rb_tree_node_base * &__root = __header._M_parent;

    // Initialize fields in new node to insert.
    __x->_M_parent = __p;
    __x->_M_left = 0;
    __x->_M_right = 0;
    __x->_M_color = _S_red;

    // 处理__header部分
    // Insert.
    // Make new node child of parent and maintain root, leftmost and
    // rightmost nodes.
    // N.B. First node is always inserted left.
    if (__insert_left) {
        __p->_M_left = __x; // also makes leftmost = __x when __p == &__header

        if (__p == &__header) {
            __header._M_parent = __x;
            __header._M_right = __x;
        } else if (__p == __header._M_left)
            __header._M_left = __x; // maintain leftmost pointing to min node
    } else {
        __p->_M_right = __x;

        if (__p == __header._M_right)
            __header._M_right = __x; // maintain rightmost pointing to max node
    }

 // Rebalance.
    while (__x != __root
           && __x->_M_parent->_M_color == _S_red)   // 若新插入节点不是为RB-Tree的根节点，且其父节点color属性也是红色,即违反了性质4.
    {
        _Rb_tree_node_base *const __xpp = __x->_M_parent->_M_parent;        // 祖父节点

        if (__x->_M_parent == __xpp->_M_left)   // 父亲是祖父节点的左孩子
        {
            _Rb_tree_node_base *const __y = __xpp->_M_right;    // 得到叔叔节点
            if (__y && __y->_M_color == _S_red)     // case1: 叔叔节点存在，且为红色
            {
                /**
                 * 解决办法是：颜色翻转，父亲与叔叔的颜色都变为黑色,祖父节点变为红色,然后当前节点设为祖父，依次网上来判断是否破坏了红黑树性质
                 */
                __x->_M_parent->_M_color = _S_black;    // 将其父节点改为黑色
                __y->_M_color = _S_black;               // 将其叔叔节点改为黑色
                __xpp->_M_color = _S_red;               // 将其祖父节点改为红色
                __x = __xpp;                            // 修改_x,往上回溯
            } else {        // 无叔叔或者叔叔为黑色
                if (__x == __x->_M_parent->_M_right) {          // 当前节点为父亲节点的右孩子
                    __x = __x->_M_parent;
                    local_Rb_tree_rotate_left(__x, __root);     // 以父节点进行左旋转
                }
                // 旋转之后,节点x变成其父节点的左孩子
                __x->_M_parent->_M_color = _S_black;            // 将其父亲节点改为黑色
                __xpp->_M_color = _S_red;                       // 将其祖父节点改为红色
                local_Rb_tree_rotate_right(__xpp, __root);      // 以祖父节点右旋转
            }
        } else {        // 父亲是祖父节点的右孩子
            _Rb_tree_node_base *const __y = __xpp->_M_left; // 保存叔叔节点
            if (__y && __y->_M_color == _S_red) {       // 叔叔节点存在且为红色
                __x->_M_parent->_M_color = _S_black;    // 父亲节点改为黑色
                __y->_M_color = _S_black;               // 祖父节点改为红色
                __xpp->_M_color = _S_red;
                __x = __xpp;
            } else {        // 若无叔叔节点或者其叔叔节点为黑色
                if (__x == __x->_M_parent->_M_left) {   // 当前节点为父亲节点的左孩子
                    __x = __x->_M_parent;
                    local_Rb_tree_rotate_right(__x, __root);    // 以父节点右旋转
                }
                __x->_M_parent->_M_color = _S_black;        // 父节点置为黑色
                __xpp->_M_color = _S_red;                   // 祖父节点置为红色
                local_Rb_tree_rotate_left(__xpp, __root);   // 左旋转
            }
        }
    }
    //若新插入节点为根节点,则违反性质2
    //只需将其重新赋值为黑色即可
    __root->_M_color = _S_black;
}

5.2 Insertion summary

From the insertion process and source analysis above, we derive the following three cases: Let P stand for the parent node, N for the newly inserted node, U for the uncle, and G for the grandparent.

case 1: U is red, and P and N are also red; then, by changing colors and adjusting recursively bottom-up, next time N becomes G, and we just keep judging upward. If the root happens to get colored red, the algorithm can force root back to black at the very end.

case 2: U is black; consider whether N is P's left or right child.

case2.1 If it is a right child, first do a left rotation, then move on to the next case.

case2.2 May have evolved from the case above, but not necessarily! The strategy: rotate right and change colors.

From the source analysis above we learn that red-black tree insertion is a mirror transformation; the other case is exactly the reverse.

The deletion operation is rather complex, so it is not analyzed here for now; to be added later...

6.Usage

After all that, how do we use it?

Include the header:

#include<map>或者<set>

Class definition:

_Rb_tree<int, int, _Identity<int>, less<int>> itree;

Then just call the corresponding functions.

Related Topics

• STL array source code analysis | C++那些事
• STL string deep dive | C++那些事
• STL string interview questions in depth | C++那些事
• STL deque source code analysis | C++那些事
• STL empty base optimization EBO | C++那些事
• STL hand-written hash table implementation | C++那些事
• STL hashtable hash table | C++那些事
• STL iterator source code analysis | C++那些事
• STL list source code analysis | C++那些事
• STL map and multimap | C++那些事

Comments