第3章：map/set - 赤黒木
はじめに
mapとsetは、平衡二分探索木（赤黒木）を使用して実装される連想コンテナです。本章では、赤黒木の理論と実装を学びます。
---
1. 赤黒木の理論
1.1 二分探索木の問題
通常の二分探索木は、入力順序によって偏る可能性があります：
理想的な木: 偏った木（最悪ケース）:
4 1
/ \ \
2 6 2
/ \ / \ \
1 3 5 7 3
\
4
高さ: O(log n) 高さ: O(n)
1.2 赤黒木の性質
Leo J. Guibas と Robert Sedgewick が1978年に発表した赤黒木は、以下の5つの性質を持ちます：
1. 各ノードは赤か黒
2. ルートは黒
3. 全ての葉（NIL）は黒
4. 赤ノードの子は両方とも黒
5. 各ノードから葉までの黒ノード数は同じ（黒高さ）
B:8
/ \
R:4 B:12
/ \ / \
B:2 B:6 R:10 R:14
B = Black, R = Red
1.3 計算量の保証
赤黒木の高さは最大で 2 * log₂(n+1) に制限されます：
| 操作 | 平均 | 最悪 | |------|------|------| | 検索 | O(log n) | O(log n) | | 挿入 | O(log n) | O(log n) | | 削除 | O(log n) | O(log n) |
---
2. ノードの構造
2.1 ノードの定義
enum RBColor { RED, BLACK };
template<typename T>
struct RBNode {
T data;
RBNode* parent;
RBNode* left;
RBNode* right;
RBColor color;
RBNode(const T& val)
: data(val), parent(NULL), left(NULL), right(NULL), color(RED) {}
};
2.2 NILノード
NILノードは、全ての葉を表すセンチネルです：
template<typename T, typename Compare, typename Alloc>
class RBTree {
private:
typedef RBNode<T> node_type;
typedef node_type* node_pointer;
node_pointer _root;
node_pointer _nil; // センチネル（黒、共有）
size_t _size;
Compare _comp;
Alloc _alloc;
public:
RBTree(const Compare& comp = Compare(),
const Alloc& alloc = Alloc())
: _root(NULL), _size(0), _comp(comp), _alloc(alloc) {
// NILノードを作成
_nil = _alloc.allocate(1);
_nil->color = BLACK;
_nil->parent = NULL;
_nil->left = NULL;
_nil->right = NULL;
_root = _nil;
}
};
---
3. 回転操作
3.1 左回転
x y
/ \ / \
a y => x c
/ \ / \
b c a b
y が x の右の子
→ y が新しい親になり、x が y の左の子になる
template<typename T, typename Compare, typename Alloc>
void RBTree<T, Compare, Alloc>::_left_rotate(node_pointer x) {
node_pointer y = x->right;
// y の左部分木を x の右部分木にする
x->right = y->left;
if (y->left != _nil) {
y->left->parent = x;
}
// y の親を x の親にする
y->parent = x->parent;
if (x->parent == _nil) {
_root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
// x を y の左の子にする
y->left = x;
x->parent = y;
}
3.2 右回転
y x
/ \ / \
x c => a y
/ \ / \
a b b c
template<typename T, typename Compare, typename Alloc>
void RBTree<T, Compare, Alloc>::_right_rotate(node_pointer y) {
node_pointer x = y->left;
// x の右部分木を y の左部分木にする
y->left = x->right;
if (x->right != _nil) {
x->right->parent = y;
}
// x の親を y の親にする
x->parent = y->parent;
if (y->parent == _nil) {
_root = x;
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
// y を x の右の子にする
x->right = y;
y->parent = x;
}
---
4. 挿入
4.1 挿入アルゴリズム
template<typename T, typename Compare, typename Alloc>
typename RBTree<T, Compare, Alloc>::node_pointer
RBTree<T, Compare, Alloc>::insert(const T& val) {
// 1. 通常のBST挿入
node_pointer z = _create_node(val);
node_pointer y = _nil;
node_pointer x = _root;
while (x != _nil) {
y = x;
if (_comp(z->data, x->data)) {
x = x->left;
} else if (_comp(x->data, z->data)) {
x = x->right;
} else {
// 重複キー（mapの場合は挿入しない）
_destroy_node(z);
return x;
}
}
z->parent = y;
if (y == _nil) {
_root = z;
} else if (_comp(z->data, y->data)) {
y->left = z;
} else {
y->right = z;
}
z->left = _nil;
z->right = _nil;
z->color = RED;
++_size;
// 2. 赤黒木の性質を修復
_insert_fixup(z);
return z;
}
4.2 挿入後の修復
挿入後に赤黒木の性質が崩れる可能性があるケース：
Case 1: 叔父が赤
g(B) g(R)
/ \ / \
p(R) u(R) => p(B) u(B)
/ /
z(R) z(R)
Case 2: 叔父が黒、zが右の子
g(B) g(B)
/ \ / \
p(R) u(B) => z(R) u(B)
\ /
z(R) p(R)
Case 3: 叔父が黒、zが左の子
g(B) p(B)
/ \ / \
p(R) u(B) => z(R) g(R)
/ \
z(R) u(B)
template<typename T, typename Compare, typename Alloc>
void RBTree<T, Compare, Alloc>::_insert_fixup(node_pointer z) {
while (z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
node_pointer y = z->parent->parent->right; // 叔父
if (y->color == RED) {
// Case 1: 叔父が赤
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
// Case 2: 叔父が黒、zが右の子
z = z->parent;
_left_rotate(z);
}
// Case 3: 叔父が黒、zが左の子
z->parent->color = BLACK;
z->parent->parent->color = RED;
_right_rotate(z->parent->parent);
}
} else {
// 対称的なケース（左右を入れ替え）
node_pointer y = z->parent->parent->left;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
_right_rotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
_left_rotate(z->parent->parent);
}
}
}
_root->color = BLACK;
}
---
5. 削除
5.1 削除アルゴリズム
削除は挿入より複雑です：
template<typename T, typename Compare, typename Alloc>
void RBTree<T, Compare, Alloc>::erase(node_pointer z) {
node_pointer y = z;
node_pointer x;
RBColor y_original_color = y->color;
if (z->left == _nil) {
// Case 1: 左の子がない
x = z->right;
_transplant(z, z->right);
} else if (z->right == _nil) {
// Case 2: 右の子がない
x = z->left;
_transplant(z, z->left);
} else {
// Case 3: 両方の子がある
y = _minimum(z->right); // 後続ノードを見つける
y_original_color = y->color;
x = y->right;
if (y->parent == z) {
x->parent = y;
} else {
_transplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
_transplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
_destroy_node(z);
--_size;
if (y_original_color == BLACK) {
_erase_fixup(x);
}
}
template<typename T, typename Compare, typename Alloc>
void RBTree<T, Compare, Alloc>::_transplant(node_pointer u, node_pointer v) {
if (u->parent == _nil) {
_root = v;
} else if (u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
v->parent = u->parent;
}
5.2 削除後の修復
template<typename T, typename Compare, typename Alloc>
void RBTree<T, Compare, Alloc>::_erase_fixup(node_pointer x) {
while (x != _root && x->color == BLACK) {
if (x == x->parent->left) {
node_pointer w = x->parent->right; // 兄弟
if (w->color == RED) {
// Case 1: 兄弟が赤
w->color = BLACK;
x->parent->color = RED;
_left_rotate(x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
// Case 2: 兄弟の両方の子が黒
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) {
// Case 3: 兄弟の右の子が黒
w->left->color = BLACK;
w->color = RED;
_right_rotate(w);
w = x->parent->right;
}
// Case 4: 兄弟の右の子が赤
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
_left_rotate(x->parent);
x = _root;
}
} else {
// 対称的なケース
// ...
}
}
x->color = BLACK;
}
---
6. mapの実装
6.1 クラス定義
namespace ft {
template<typename Key, typename T,
typename Compare = std::less<Key>,
typename Alloc = std::allocator<std::pair<const Key, T> > >
class map {
public:
typedef Key key_type;
typedef T mapped_type;
typedef std::pair<const Key, T> value_type;
typedef Compare key_compare;
typedef Alloc allocator_type;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
// value_compare（ペアのfirstを比較）
class value_compare {
friend class map;
protected:
Compare comp;
value_compare(Compare c) : comp(c) {}
public:
bool operator()(const value_type& x, const value_type& y) const {
return comp(x.first, y.first);
}
};
private:
typedef RBTree<value_type, value_compare,
typename Alloc::template rebind<RBNode<value_type> >::other>
tree_type;
tree_type _tree;
key_compare _comp;
public:
typedef typename tree_type::iterator iterator;
typedef typename tree_type::const_iterator const_iterator;
typedef ft::reverse_iterator<iterator> reverse_iterator;
typedef ft::reverse_iterator<const_iterator> const_reverse_iterator;
// コンストラクタ
explicit map(const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
template<typename InputIterator>
map(InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
map(const map& x);
// ...
};
} // namespace ft
6.2 主要メンバ関数
// operator[]
template<typename Key, typename T, typename Compare, typename Alloc>
typename map<Key, T, Compare, Alloc>::mapped_type&
map<Key, T, Compare, Alloc>::operator[](const key_type& k) {
iterator it = find(k);
if (it == end()) {
it = insert(ft::make_pair(k, mapped_type())).first;
}
return it->second;
}
// insert
template<typename Key, typename T, typename Compare, typename Alloc>
std::pair<typename map<Key, T, Compare, Alloc>::iterator, bool>
map<Key, T, Compare, Alloc>::insert(const value_type& val) {
iterator it = find(val.first);
if (it != end()) {
return std::make_pair(it, false);
}
return std::make_pair(_tree.insert(val), true);
}
// find
template<typename Key, typename T, typename Compare, typename Alloc>
typename map<Key, T, Compare, Alloc>::iterator
map<Key, T, Compare, Alloc>::find(const key_type& k) {
return _tree.find(ft::make_pair(k, mapped_type()));
}
---
7. イテレータの実装
7.1 木のイテレータ
template<typename T>
class RBTreeIterator {
public:
typedef T value_type;
typedef T& reference;
typedef T* pointer;
typedef std::bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
private:
typedef RBNode<T>* node_pointer;
node_pointer _node;
node_pointer _nil;
public:
RBTreeIterator() : _node(NULL), _nil(NULL) {}
RBTreeIterator(node_pointer node, node_pointer nil)
: _node(node), _nil(nil) {}
reference operator*() const { return _node->data; }
pointer operator->() const { return &(_node->data); }
// インクリメント（次のノードに移動）
RBTreeIterator& operator++() {
if (_node->right != _nil) {
// 右部分木がある場合、右部分木の最小値
_node = _node->right;
while (_node->left != _nil) {
_node = _node->left;
}
} else {
// 右部分木がない場合、親を辿る
node_pointer p = _node->parent;
while (p != _nil && _node == p->right) {
_node = p;
p = p->parent;
}
_node = p;
}
return *this;
}
RBTreeIterator operator++(int) {
RBTreeIterator tmp = *this;
++(*this);
return tmp;
}
// デクリメント（前のノードに移動）
RBTreeIterator& operator--() {
if (_node->left != _nil) {
_node = _node->left;
while (_node->right != _nil) {
_node = _node->right;
}
} else {
node_pointer p = _node->parent;
while (p != _nil && _node == p->left) {
_node = p;
p = p->parent;
}
_node = p;
}
return *this;
}
bool operator==(const RBTreeIterator& other) const {
return _node == other._node;
}
bool operator!=(const RBTreeIterator& other) const {
return _node != other._node;
}
};
---
まとめ
本章で学んだこと：
- 赤黒木の性質: 5つの不変条件
- 回転操作: 左回転、右回転
- 挿入: BST挿入と赤黒木の修復
- 削除: 複雑なケース分け
- mapの構造: 赤黒木を使用した実装
- イテレータ: 木を順序付きで走査
次章では、stack（コンテナアダプタ）を学びます。