Última actualización：2026-10-12

STL implementación de árbol rojo-negro

0.Introducción

En el código fuente de STL hay dos párrafos que, traducidos brevemente, dicen lo siguiente:

En STL, la clase red-black tree (árbol rojo-negro) se usa como contenedor asociativo (por ejemplo set, multiset, map, multimap). Los métodos de insertion y deletion que emplea se basan en el libro 《Introduction to Algorithms》, pero con dos diferencias:

(1) header apunta no solo a root, sino también al nodo más a la izquierda del árbol rojo-negro, para implementar begin() en tiempo constante, y apunta también al nodo más a la derecha del árbol rojo-negro, para que los algoritmos genéricos relacionados con set (como set_union, etc.) puedan tener un comportamiento de tiempo lineal.

(2) Cuando el nodo que va a borrarse tiene dos hijos, su nodo sucesor se enlaza en su posición en lugar de copiarse, de modo que los únicos iteradores que se invalidan son los que referencian al nodo borrado.

Lo anterior, traducido a dibujo, queda así: en comparación con el árbol rojo-negro normal hay un nodo header adicional, que además es rojo. El árbol rojo-negro normal empieza en el nodo 100 y satisface las cinco propiedades siguientes: - Cada nodo es rojo o negro. - El nodo raíz es negro. - Cada nodo hoja (NULL) es negro. - Si un nodo es rojo, sus dos hijos son negros. - Para cada nodo, todos los caminos simples desde ese nodo hasta sus nodos hoja descendientes contienen el mismo número de nodos negros.

Naturalmente, este rb_tree también satisface estas propiedades: el begin del iterador apunta a la raíz del árbol rojo-negro, es decir, al padre de header, y el end apunta al nodo header.

。 Los puntos suspensivos del dibujo indican que los nodos no están dibujados por completo y que quedan otros, por eso se omiten.

1.Clase base de los nodos del árbol rojo-negro

La clase base del árbol rojo-negro es muy sencilla; al principio del fichero se define el marcador de color.

La clase base contiene punteros a sí misma: define left, right y parent, e incluye además una constante como marcador de color; dentro hay dos funciones núcleo, cuyo propósito es obtener el nodo mínimo y el nodo máximo del árbol rojo-negro. Sabemos que para un árbol binario de búsqueda obtener el nodo mínimo consiste en bajar siempre por el subárbol izquierdo, y obtener el máximo en bajar siempre por el subárbol derecho.

// 颜色标记
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.Nodo del árbol rojo-negro

El nodo del árbol rojo-negro hereda de la clase base del árbol rojo-negro.

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 del árbol rojo-negro

Dentro del iterador del árbol rojo-negro hay un miembro que es la clase base del árbol rojo-negro, y a través de ese miembro se realizan las operaciones relacionadas con el iterador. Al mismo tiempo, podemos saber que este iterador pertenece a la categoría bidirectional_iterator_tag.

También incluye los typedef que necesita la máquina de extracción (traits).

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

Obtener los datos

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 del operador ++

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

Y la base de _Rb_tree_increment es local_Rb_tree_increment, implementada así:

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 del operador --:

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

Análogamente, la base de _Rb_tree_decrement es local_Rb_tree_decrement, implementada así:

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 de los operadores == y !=: se limitan a comparar si los punteros a nodo son iguales.

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

Otra función importante, el conteo de nodos negros:

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

Más adelante expondremos la operación más importante: la inserción.

4.Operaciones del árbol rojo-negro

Algo importante: dentro se usa la clase base de nodo para declarar un puntero. Incluye también un _Rb_tree_impl para las operaciones de inicialización del árbol rojo-negro y de gestión de memoria. Contiene además dos tipos de iterador, uno de rbtree y otro reverse, lo que indica que admite las operaciones rbegin y 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;
};

Obtener la raíz, el nodo más a la izquierda y el nodo más a la derecha del árbol rojo-negro

Volvamos al dibujo del principio: .

// 图中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); }

¡Al mirar de nuevo el código todo resulta clarísimo!

5.Inserción en el árbol rojo-negro

5.1 Proceso de rotación

La rotación izquierda consiste en establecer el nodo derecho de este nodo como su nodo padre, y este nodo pasará a ser el hijo izquierdo de aquel que era su nodo derecho.

Basta con comparar directamente el dibujo del código fuente con el código.

En el código fuente tree.cc las funciones que lo implementan son local_Rb_tree_rotate_left y local_Rb_tree_rotate_right. A continuación diseccionamos el código fuente en un código más fácil de entender; véanse los comentarios. Veréis que los nombres de función y de variables difieren de los del código fuente, porque lo que sigue es una implementación propia de la época, pero no estorba la lectura del código fuente, así que la uso directamente para comparar.

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

Análogamente, la rotación derecha:

//        _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: el nodo padre es rojo y su nodo tío también es rojo; entonces el padre y el tío se ponen negros, y el abuelo rojo.

case 1.2 Si no hay nodo tío o el nodo tío es negro, se divide en los dos casos siguientes:

Caso 1.2.1: el nodo tío y de x es negro y x es un hijo derecho

Caso 1.2.2: el nodo tío y de x es negro y x es un hijo izquierdo

Correspondiente al código fuente:

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

El otro es el proceso simétrico del anterior:

case 2.1: el nodo padre es rojo y su nodo tío también es rojo; entonces el padre y el tío se ponen negros, y el abuelo rojo.

case 2.2 Si no hay nodo tío o el nodo tío es negro

Caso 2.2.1: el nodo tío y de x es negro y x es un hijo izquierdo

_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álisis completo 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.Resumen de la inserción

Según el proceso de inserción anterior y el análisis del código fuente obtenemos los tres casos siguientes: Supongamos que P representa el nodo padre, N el nodo recién insertado, U el nodo tío y G el nodo abuelo.

case 1: U es rojo, y P y N también son rojos; se puede resolver cambiando colores y ajustando recursivamente de abajo hacia arriba: la próxima vez N pasa a ser G y basta con seguir juzgando hacia arriba. Si por casualidad la raíz queda teñida de rojo, al final del algoritmo se puede forzar root a negro.

case 2: U es negro; hay que considerar si N es hijo izquierdo o hijo derecho de P.

case2.1 Si es hijo derecho, primero se hace una rotación izquierda y se pasa al caso siguiente.

case2.2 Puede provenir del caso anterior, ¡pero no necesariamente! La estrategia es: rotación derecha y cambio de colores.

Del análisis del código fuente anterior se deduce que la inserción en el árbol rojo-negro es una transformación especular; el otro caso es justamente el contrario.

La operación de borrado es más compleja y de momento no se analiza aquí; se añadirá más adelante...

6.Uso

Después de tanto dicho, ¿cómo se usa?

Incluir la cabecera:

#include<map>或者<set>

Definición de la clase:

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

Y después basta con llamar a las funciones correspondientes.

Temas relacionados

• Análisis del código fuente de STL array | C++那些事
• Análisis profundo de STL string | C++那些事
• STL string preguntas de entrevista explicadas | C++那些事
• Análisis del código fuente de STL deque | C++那些事
• STL optimización de clase base vacía EBO | C++那些事
• STL implementación de una tabla hash escrita a mano | C++那些事
• STL hashtable tabla hash | C++那些事
• Análisis del código fuente de los iteradores STL | C++那些事
• Análisis del código fuente de STL list | C++那些事
• STL map y multimap | C++那些事

Comentarios