前言
本文介绍如何使用红黑树封装出 set 与 map。
一、STL 源码分析
首先，库里面 stl_set 与 stl_map 中：
对于 set 来说，key_type 是 key，value_type 也是 key，也就是说 set 是一个 rbTree<Key, Key> 的模型。
对于 map 来说，key_type 是 key，但是 value_type 是 pair<const key, T>，也就是说 map 是一个 rbTree<Key, pair<Key, Value>> 的模型。
我们再来看一下 rb_tree 的结构：
rb_tree 中，前两个参数是 <key, value>，而 __rb_tree_node<value> 里面的参数传的是 value，因此我们可以总结出，这里 map 的结点中存储的是 pair<key, value>，而 set 的结点中存储的是 key。
那么到底为什么是这样的结构呢？我们将在下面的讲解中逐一解释。
二、红黑树的构建
对于红黑树的构建，之前的文章有详细的讲解。当然，我们之前红黑树是默认存储 pair，现在要同时满足 map 与 set，因此一些地方需要改变，之后总结的时候会给出完整的更改后的代码。
#pragma once
#include <iostream>
using namespace std;
enum Colour { RED, BLACK };
template<class K, class V>
struct RBTreeNode {
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};
template<class K, class V>
class RBTree {
typedef RBTreeNode<K, V> Node;
:
{
(_root == ) {
_root = (kv);
_root->_col = BLACK;
;
}
Node* cur = _root;
Node* parent = ;
(cur) {
(kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
}
(kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
{
;
}
}
cur = (kv);
cur->_col = RED;
(cur->_kv.first < parent->_kv.first) {
parent->_left = cur;
}
{
parent->_right = cur;
}
cur->_parent = parent;
(parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
(parent == grandfather->_left) {
Node* uncle = grandfather->_right;
(uncle && uncle->_col == RED) {
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
{
(cur == parent->_left) {
(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
{
(parent);
(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
;
}
}
{
Node* uncle = grandfather->_left;
(uncle && uncle->_col == RED) {
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
{
(cur == parent->_right) {
(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
{
(parent);
(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
;
}
}
}
_root->_col = BLACK;
;
}
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
(curleft)
{
curleft->_parent = parent;
}
cur->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = cur;
(ppnode == ) {
_root = cur;
cur->_parent = ;
}
{
(ppnode->_left == parent) {
ppnode->_left = cur;
}
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
}
{
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright;
(curright) {
curright->_parent = parent;
}
cur->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = cur;
(ppnode == ) {
cur->_parent = ;
_root = cur;
}
{
(ppnode->_left == parent) {
ppnode->_left = cur;
}
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
}
{
(root == ) {
(blacknum != benchmark) ;
;
}
(root->_col == BLACK) {
++blacknum;
}
(root->_col == RED && root->_parent && root->_parent->_col == RED) {
cout << root->_kv.first << << endl;
;
}
(root->_left, blacknum, benchmark) && (root->_right, blacknum, benchmark);
}
{
(_root);
}
{
(root == ) ;
(root->_col != BLACK) {
;
}
benchmark = ;
Node* cur = _root;
(cur) {
(cur->_col == BLACK) ++benchmark;
cur = cur->_left;
}
(root, , benchmark);
}
:
Node* _root = ;
};
