最終更新：2026-10-12
STL 赤黒木実装¶
0.はじめに¶
STLのソースコードには2つの段落があり、簡単に訳すと次のようになります：
STLのRed-black tree（赤黒木）classは、SLTの連想コンテナ（set、multiset、map、 multimapなど）の基盤として使われます。その中で使われているinsertionとdeletionの方法は 《Introduction to Algorithms》という書籍に基づいていますが、以下の2点が異なります：
(1)headerはrootのみならず、赤黒木の最左ノードも指します。これにより定数時間でbegin()を実現できます。さらに赤黒木の最右ノードも指します。これにより set関連の汎用アルゴリズム（set_unionなど）が線形時間の性能を持てます。
(2)削除しようとするノードが2つの子ノードを持つ場合、その後継ノードが位置に接続され、コピーされるのではありません。したがって、無効になるイテレータは、削除されたノードを参照していたイテレータだけです。
上の文章を図に訳すと、次のようになります。普通の赤黒木と比べてheaderノードが1つ多く、それは赤色です。普通の赤黒木は100ノードから始まっており、次の5つの性質を満たします： - 各ノードは赤色、または黑色である。 - 根ノードは黒色である。 - 各葉ノード（NULL）は黒色である。 - あるノードが赤色ならば、その2つの子ノードはいずれも黒色である。 - 各ノードについて、そのノードからそのすべての子孫の葉ノードへの単純パス上には、すべて同じ数の黒色ノードが含まれる。
もちろんここのrb_treeも同様にこれらの性質を満たしています。イテレータのbeginは赤黒木の根ノード、すなわちheaderの親を指し、endはheaderノードを指します。
。
図中の省略記号は、ノードをすべて描ききれておらず、他にもノードがあるため省略したことを表します。
1.赤黒木ノード基底クラス¶
赤黒木の基底クラス。非常に単純で、ファイルの先頭でカラーマーカーが定義されています。
基底クラスには自分自身へのポインタが含まれ、それぞれleft、right、parentとして定義されています。同時にカラーマーカーの定数も含まれています。その中には2つの中心的な関数があり、目的は赤黒木の中の最小ノードと最大ノードを取得することです。 二分探索木では、最小ノードの取得は左部分木をひたすら下に探索し、最大ノードの取得は右部分木をひたすら下に探索すればよいと知られています。
// 颜色标记
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.赤黒木ノード¶
赤黒木ノードは赤黒木の基底クラスを継承します。
template<typename _Val>
struct _Rb_tree_node : public _Rb_tree_node_base
{
typedef _Rb_tree_node<_Value>* _Link_type;//节点指针,指向数据节点
_Value _M_value_field;//节点数据域,即关键字
};
3.赤黒木イテレータ¶
赤黒木イテレータの中には赤黒木基底クラスのメンバが1つあり、そのメンバを通してイテレータの関連操作を行います。
同時に、このイテレータはbidirectional_iterator_tagに属することがわかります。
中には抽出機（traits）に関連する必要なtypedefも含まれています。
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;
};
データの取得
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(); }
++演算子のオーバーロード
_Rb_tree_incrementの基盤はlocal_Rb_tree_incrementで、実装は次の通りです：
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);
}
_Rb_tree_decrementの基盤はlocal_Rb_tree_decrementで、実装は次の通りです：
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);
}
==と!=演算子のオーバーロード。ノードポインタが等しいかどうかを直接判断します。
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; }
その他の重要な関数、黒ノードのカウント：
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;
}
4.赤黒木の操作¶
比較的重要なのは、中でノード基底クラスを使ってポインタを1つ宣言している点です。さらに_Rb_tree_implを1つ含み、赤黒木の初期化操作とメモリ管理操作に使われます。中には2種類のイテレータも含まれています。1つはrbtree、もう1つはreverseで、rbegin、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;
};
赤黒木の根ノード、最左、最右ノードの取得
最初の図に戻ります：
。
// 图中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); }
5.赤黒木の挿入¶
5.1 回転の過程¶
左回転とは、そのノードの右ノードをその親ノードに設定することです。そのノードは、先ほどの右ノードの左の子になります。
ソースコード中の図とコードを直接対比して見ればよいです。
tree.ccソースコードの中で、実装関数はlocal_Rb_tree_rotate_leftとlocal_Rb_tree_rotate_rightです。
以下では、ソースコードを理解しやすいコードに剖析します。詳細はコメントを参照してください。
関数名と変数名がソースコードと異なることに気づくでしょう。これは以下が当時自分で実装したものだからですが、ソースコードの読解には影響しないので、そのまま対比に使っています。
/**
* 当前节点的左旋转过程
* 将该节点的右节点设置为它的父节点，该节点将变成刚才右节点的左孩子
* @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
}
同様に、右回転は次の通りです：
// _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: 親ノードが赤色で、かつその叔父ノードも赤色の場合、父と叔父を黒色にし、祖父を赤色にします。
case 1.2 叔父ノードがない場合、またはその叔父ノードが黒色の場合、次の2つに分かれます：
ケース1.2.1：xの叔父ノードyは黒色で、xは右の子である
ケース1.2.2：xの叔父ノードyは黒色で、xは左の子である
対応するソースコードは：
_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); // 以祖父节点右旋转
}
もう1つは上述の対称な過程です：
case 2.1: 親ノードが赤色で、かつその叔父ノードも赤色の場合、父と叔父を黒色にし、祖父を赤色にします。
case 2.2 叔父ノードがない場合、またはその叔父ノードが黒色の場合
ケース2.2.1：xの叔父ノードyは黒色で、xは左の子である
_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); // 左旋转
}
_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挿入のまとめ¶
上述の挿入過程とソースコードの分析から、次の3つの場合が得られます： Pは親ノード、Nは現在新しく挿入されたノード、Uは叔父ノード、Gは祖父ノードを表すとします。
case 1:Uが赤色で、P、Nもともに赤色の場合、色を変えることで、ボトムアップに再帰的に調整できます。次回はNがGとなり、上に向かって判断するだけです。もし偶然にも根ノードが赤色に染まった場合は、アルゴリズムの最後でrootを強制的に黒に変えられます。
case 2:Uが黒色の場合、NがPの左の子か右の子かを考慮します。
case2.1 右の子の場合、まず左回転を行い、その後次の場合に入ります。
case2.2 上述のケースから変化してきた可能性もありますが、そうとは限りません！戦略は：右回転、色の変更です。
上述のソースコードの分析から、赤黒木の挿入は鏡像変換であり、もう1つの場合はちょうど逆であることがわかりました。
削除操作は比較的複雑なので、ここでは当面分析せず、後で補います。。。
6.使用¶
ここまでいろいろ述べてきましたが、どのように使うのでしょうか？
ヘッダファイルを導入します：
クラス定義： あとは対応する関数を呼び出すだけです。関連トピック¶
- STL array ソースコード解析 | C++那些事
- STL string 深入解析 | C++那些事
- STL string 面接問題解説 | C++那些事
- STL deque ソースコード解析 | C++那些事
- STL 空基底クラス最適化 EBO | C++那些事
- STL 手書きハッシュテーブル実装 | C++那些事
- STL hashtable ハッシュテーブル | C++那些事
- STL イテレータソースコード解析 | C++那些事
- STL list ソースコード解析 | C++那些事
- STL map と multimap | C++那些事