【C++】 红黑树封装 STL set/map 超详细解析

  红黑树封装 STL set/map 超详细解析  

一、STL 为什么用红黑树封装 set/map？

满足 set/map 的核心需求：

STL 设计思想：红黑树作为通用底层结构，set 和 map 只是它的 “适配器”，就像栈 / 队列适配 deque 一样。

二、红黑树封装 set/map 核心原理（最关键）

1. 底层共用一棵红黑树

C++ STL 中：

• set：存储唯一有序的 key
• map：存储唯一有序的 key + 对应 value

它们底层共用同一个红黑树模板，只通过存储数据类型区分：

• set 红黑树节点：存储 Key
• map 红黑树节点：存储 pair<const Key, Value>

2. 封装核心：萃取器（key_of_value）

        红黑树只需要key 进行排序和比较，但 map 存的是键值对，因此需要一个 “萃取器” 告诉红黑树：

• 给我你的数据，我从中提取出 key 用于排序。

        这是 set 和 map 唯一的本质区别！

三、set /map/multiset /multimap 封装区别

唯一区别：插入时是否检查 key 重复，其他逻辑完全一致。

四、STL 底层源码结构

1. 红黑树模板（通用底层）

// 简化版 STL 红黑树
template <class Key, // 键类型
class Value, // 存储值类型（set=Key, map=pair<Key,T>）
class KeyOfValue, // key 萃取器：从 Value 中提取 Key
class Compare> // 比较函数（默认 less<Key>）
class rb_tree {
public:
// 核心接口（set/map 直接调用）
iterator insert(const Value& val); // 插入
iterator find(const Key& key); // 查找
void erase(iterator pos); // 删除
// … 其他接口
};

2. set 封装（适配器）

template <class Key, class Compare = less<Key>>
class set {
public:
// 定义萃取器：Value 就是 Key，直接返回
struct KeyOfValue {
const Key& operator()(const Key& k) { return k; }
};

private:
// 底层红黑树
using RepType = rb_tree<Key, Key, KeyOfValue, Compare>;
RepType tree; // 聚合实现，不是继承！

public:
// 接口直接转发给红黑树
pair<iterator, bool> insert(const Key& k) {
return tree.insert(k);
}
iterator find(const Key& k) { return tree.find(k); }
// … 其他接口
};

3. map 封装（适配器）

template <class Key, class T, class Compare = less<Key>>
class map {
public:
using ValueType = pair<const Key, T>;
// 萃取器：从 pair 中提取 first 作为 key
struct KeyOfValue {
const Key& operator()(const ValueType& v) { return v.first; }
};

private:
using RepType = rb_tree<Key, ValueType, KeyOfValue, Compare>;
RepType tree;

public:
// 转发接口
pair<iterator, bool> insert(const ValueType& v) {
return tree.insert(v);
}
// [] 运算符重载：map 独有
T& operator[](const Key& k) {
return (*insert({k, T()}).first).second;
}
// …
};

五、set 和 map 的关键差异总结（面试必问）

六、红黑树封装的优势

七、常见面试题

八、代码实现

RBTree.h

enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
};

// 实现步骤：
// 1、实现红⿊树
// 2、封装map和set框架，解决KeyOfT
// 3、iterator
// 4、const_iterator
// 5、key不⽀持修改的问题
// 6、operator[]

template<class T, class Ref, class Ptr>
struct TreeIterator
{
typedef RBTreeNode<T> Node;
typedef TreeIterator<T, Ref, Ptr> Self;
Node* _node;
private:
Node* _root = nullptr;
public:
TreeIterator(Node* node)
:_node(node)
{}

Ref operator*()
{
return _node->_data;
}

Ptr operator->()
{
return &_node->_data;
}

bool operator != (const Self& s) const
{
return _node != s._node;
}

bool operator == (const Self& s) const
{
return _node == s._node;
}

Self& operator–()
{
if (_node == nullptr)//如果当前节点为空，⾛到中序最后⼀个结点，整棵树的最右结点
{
Node* max = _root;
while (max && max->_right)
{
max = max->_right;
}

_node = max;
}
else if (_node->_left)// 左⼦树不为空，中序左⼦树最后⼀个
{
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}

_node = max;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}

_node = parent;
}
return *this;
}

Self& operator++()
{
// 当前节点右不为空，下一个就是右子树的中序第一个（最左节点）
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}

_node = min;
}
else// 当前节点右为空，下一个孩子是父亲左的那个祖先节点
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}

_node = parent;
}

return *this;
}
};

template<class K,class T,class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef TreeIterator<T, T&, T*> Iterator;
typedef TreeIterator<T, const T&, const T*> ConstIterator;
private:
Node* _root = nullptr;
public:
Iterator Begin()
{
Node* min = _root;
while (min && min->_left)
{
min = min->_left;
}

return Iterator(min);
}

Iterator End()
{
return Iterator(nullptr);
}

pair<Iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;

return { Iterator(_root), true };
}
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data)< kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return { Iterator(cur), false };
}
}

cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;

if (kot(parent->_data)< kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;

while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// 叔叔存在且为红->变色
if (uncle && uncle->_col == RED)//情况1：变? c为红，p为红，g为?，u存在且为红
{
// g
// p u
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}

else
{
if (cur == parent->_left) // 情况2：单旋+变? c为红，p为红，g为?，u不存在或者u存在且为?
{
// g
// p u
//c
// 右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //情况3：双旋+变? c为红，p为红，g为?，u不存在或者u存在且为?，u不存在，
{
// g
// p u
// c
// 左右单旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else // grandfather->_right == parent
{
// g
// u p
Node* uncle = grandfather->_left;
// 叔叔存在且为红，-》变色即可
if (uncle && uncle->_col == RED)//情况1：变? c为红，p为红，g为?，u存在且为红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;

// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else// 情况2：单旋+变? c为红，p为红，g为?，u不存在或者u存在且为?
{
// 情况二：叔叔不存在或者存在且为黑
// 旋转+变色

if (cur == parent->_right)
{
// g
// u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} //情况3：双旋+变? c为红，p为红，g为?，u不存在或者u存在且为?，u不存在，
else
{// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return {Iterator(newnode), true};
}
private:
Node* Find(const K& key)
{
KeyOfT kot;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else if (kot(cur->_data) > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;

parent->_left = subLR;
if (subLR)
subLR->_parent = parent;

Node* parentParent = parent->_parent;

subL->_right = parent;
parent->_parent = subL;

if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}

subL->_parent = parentParent;
}
}

void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;

parent->_right = subRL;
if (subRL)
subRL->_parent = parent;

Node* parentParent = parent->_parent;

subR->_left = parent;
parent->_parent = subR;

if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}

subR->_parent = parentParent;
}
}
};

补充：STL 红黑树真正实现：用 哨兵节点 (header) 当 end ()

两种 end () 实现对比（最清晰）

Set和Map封装

#include"RBTree.h"

namespace bit
{
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
iterator begin()
{
return _t.Begin();
}

iterator end()
{
return _t.End();
}

pair<iterator, bool> insert(const K& k)
{
return _t.Insert(k);
}
private:
RBTree<K, const K, SetKeyOfT> _t;
};
};

namespace bit
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
iterator begin()
{
return _t.Begin();
}

iterator end()
{
return _t.End();
}

pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}

V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}

private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
};