Ir para o conteúdo

Última atualização：2026-10-12

STL implementação de red-black tree

0. Introdução

No código-fonte da STL há dois parágrafos, cuja tradução simples é a seguinte:

Na STL, a classe Red-black tree (árvore rubro-negra) serve de base para os contêineres associativos (como set, multiset, map, multimap). Os métodos de insertion e deletion usados dentro dela baseiam-se no livro 《Introduction to Algorithms》, com duas diferenças:

(1) header aponta não só para root, mas também para o nó mais à esquerda da red-black tree, para implementar begin() em tempo constante, e também para o nó mais à direita da red-black tree, para que os algoritmos genéricos relacionados a set (como set_union etc.) possam ter desempenho linear.

(2) Quando o nó a ser removido tem dois filhos, o seu sucessor é ligado ao seu lugar, em vez de copiado; assim, os únicos iteradores invalidados são os que referenciam o nó removido.

Traduzindo as palavras acima em uma figura, como se vê a seguir: em comparação com uma red-black tree comum, há um nó header adicional, e ele é vermelho. A red-black tree comum começa no nó 100 e satisfaz as cinco propriedades abaixo: - cada nó é vermelho ou preto. - o nó raiz é preto. - cada nó folha (NULL) é preto. - se um nó é vermelho, os seus dois filhos são pretos. - para cada nó, todos os caminhos simples desse nó até os seus nós folha descendentes contêm o mesmo número de nós pretos.

Naturalmente, este rb_tree também satisfaz essas propriedades: o begin do iterador aponta para o nó raiz da red-black tree, ou seja, o pai do header, e o end aponta para o nó header.

st.png。 As reticências na figura indicam que os nós não foram todos desenhados — há outros nós, por isso foram omitidos.

1. Classe base dos nós da red-black tree

A classe base da red-black tree é muito simples; no início do arquivo são definidas as marcações de cor.

A classe base contém ponteiros para si mesma, definindo respectivamente left, right e parent, além de uma constante de marcação de cor; dentro dela há duas funções centrais, cujo objetivo é obter o menor nó e o maior nó da red-black tree. Sabemos que, para uma árvore de busca binária, obter o menor nó é descer sempre pela subárvore esquerda, e obter o maior nó é descer sempre pela subárvore direita.

// 颜色标记
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. Nós da red-black tree

Os nós da red-black tree herdam da classe base da red-black tree. 

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

3. Iterador da red-black tree

Dentro do iterador da red-black tree há um membro da classe base da red-black tree, e é por meio desse membro que as operações relacionadas ao iterador são realizadas. Ao mesmo tempo, podemos saber que esse iterador é do tipo bidirectional_iterator_tag.

Ele também contém os typedef exigidos pelo extrator.

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

Obter os dados

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

Sobrecarga do operador ++

_Self&
operator++() _GLIBCXX_NOEXCEPT
{
    _M_node = _Rb_tree_increment(_M_node);
    return *this;
}
E a camada subjacente de _Rb_tree_increment é local_Rb_tree_increment, implementada assim:

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);
}
Sobrecarga do operador --:

_Self&
operator--() _GLIBCXX_NOEXCEPT
{
    _M_node = _Rb_tree_decrement(_M_node);
    return *this;
}
Pelo mesmo raciocínio, a camada subjacente de _Rb_tree_decrement é local_Rb_tree_decrement, implementada assim:

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

Sobrecarga dos operadores == e !=, avaliando diretamente se os ponteiros de nó são iguais.

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

Outra função importante, a contagem de nós pretos:

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;
}
Mais adiante abordaremos a operação mais importante: a inserção.

4. Operações da red-black tree

Um ponto importante: dentro dela usa-se a classe base dos nós para declarar um ponteiro. Há também um _Rb_tree_impl para as operações de inicialização e de gerenciamento de memória da red-black tree. Ela contém ainda dois iteradores: um rbtree e outro reverse, o que mostra o suporte às operações rbegin e rend. 

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

Obter o nó raiz, o nó mais à esquerda e o nó mais à direita da red-black tree

Voltando à figura do início: rbt.png.

// 图中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); }
Vendo o código de novo, não fica tudo muito claro!

5. Inserção na red-black tree

5.1 Processo de rotação

A rotação à esquerda faz com que o nó direito deste nó se torne o seu pai, e o nó passará a ser o filho esquerdo do que era o seu nó direito.

Basta comparar diretamente a figura do código-fonte com o código.

No código-fonte de tree.cc, as funções de implementação são local_Rb_tree_rotate_left e local_Rb_tree_rotate_right. Abaixo, dissecamos o código-fonte em um código mais fácil de entender; veja os comentários. Vocês notarão que os nomes das funções e das variáveis diferem do código-fonte, porque o que está abaixo foi a minha própria implementação da época, mas isso não atrapalha a leitura do código-fonte — usei-a diretamente para comparação.

/**
* 当前节点的左旋转过程
* 将该节点的右节点设置为它的父节点，该节点将变成刚才右节点的左孩子
* @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
}

Pelo mesmo raciocínio, a rotação à direita é a seguinte: 

//        _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: o nó pai é vermelho e o seu tio também é vermelho; então o pai e o tio ficam pretos, e o avô fica vermelho.

rb_1.png

case 1.2 se não há tio, ou o tio é preto, dividimos em dois casos:

Caso 1.2.1: o tio y de x é preto e x é um filho direito

rb1.2.1.png

Caso 1.2.2: o tio y de x é preto e x é um filho esquerdo

rb1.2.2.png

Correspondente no código-fonte: 

_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);      // 以祖父节点右旋转
}

A outra é o processo simétrico do acima:

case 2.1: o nó pai é vermelho e o seu tio também é vermelho; então o pai e o tio ficam pretos, e o avô fica vermelho.

rb2.1.png

case 2.2 se não há tio, ou o tio é preto

rb2.2.1.png

Caso 2.2.1: o tio y de x é preto e x é um filho esquerdo

rb2.2.2.png

_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);   // 左旋转
}

Análise completa de _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 Resumo da inserção

Com base no processo de inserção acima e na análise do código-fonte, chegamos aos três casos a seguir: Suponha que P representa o nó pai, N o novo nó inserido atual, U o tio e G o avós.

case 1: U é vermelho, e P e N também são vermelhos; pode-se ajustar recursivamente de baixo para cima mudando as cores — na próxima iteração N passa a ser G, e basta continuar julgando para cima. Se por acaso a raiz acabar tingida de vermelho, pode-se forçar root a voltar a preto ao final do algoritmo.

1_1.png

case 2: U é preto; considere se N é filho esquerdo ou direito de P.

case2.1 se for filho direito, primeiro faz-se a rotação à esquerda e passa-se ao caso seguinte.

2_1.png

case2.2 pode ter derivado do caso acima, mas não necessariamente! A estratégia é: rotação à direita e mudança de cores.

rb2_2.png

Pela análise do código-fonte acima, ficamos sabendo que a inserção na red-black tree é uma transformação em espelho, e o outro caso é exatamente o inverso.

A operação de remoção é mais complexa e não foi analisada por enquanto; será acrescentada mais tarde...

6. Uso

Depois de tanta teoria, como usar?

Inclua o cabeçalho: 

#include<map>或者<set>
Definição da classe: 
_Rb_tree<int, int, _Identity<int>, less<int>> itree;
Depois, basta chamar as funções correspondentes.

Tópicos relacionados

Comentários