C++----红黑树map和set的封装

一、红黑树

1.概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

2.性质

1. 每个结点不是红色就是黑色 
2. 根节点是黑色的  
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（没有连续的红色节点，可以有连续的黑色节点）
4. 每条路径均包含相同数目的黑色结点  
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

3.红黑树 VS AVL树

红黑树 vs AVL 树核心对比：

1.平衡条件差异

• AVL 树：严格平衡（任意节点左右子树高度差≤1）
• 红黑树：弱平衡（最长路径≤2 倍最短路径）

2.高度特性

• AVL 树：高度 h=O (log n)
• 红黑树：高度 h=O (2 log n) → 实际测试中通常为 1.2-1.4 倍 AVL 树高度

性能差异分析：

1. 操作复杂度对比

   操作类型	AVL树	红黑树
   查找	O(h)	O(h)
   插入	O(h)	O(h)
   删除	O(h)	O(h)

2. 实际效率表现

• 查找：AVL 树略优（高度更低）
• 插入 / 删除：红黑树更优（旋转次数少）
• 综合性能：红黑树在动态场景更高效

效率差异原因：

1.旋转成本对比

• AVL 树：每次插入可能需多次旋转（平均 1.02 次）
• 红黑树：最多 3 次旋转（平均 0.2 次）
• 旋转操作对缓存不友好（破坏空间局部性）

2.常数因子影响

• 红黑树节点需维护颜色字段（增加少量内存）
• AVL 树需维护平衡因子（同样增加内存）
• 红黑树的颜色检查比 AVL 树的平衡因子计算更高效

4.实现思路与代码

节点结构定义

// 定义颜色枚举类型，包含红色和黑色两种颜色
enum Colour
{RED,BLACK
};// 定义红黑树节点的模板结构体
template<class K, class V>
struct RBTreeNode
{// 指向左子节点的指针RBTreeNode<K, V>* _left;// 指向右子节点的指针RBTreeNode<K, V>* _right;// 指向父节点的指针，用于回溯操作，方便在插入和删除时调整树的结构RBTreeNode<K, V>* _parent;// 存储键值对，键类型为K，值类型为Vpair<K, V> _kv;// 节点的颜色，使用前面定义的枚举类型Colour _col;// 构造函数，用于创建新节点// 节点颜色初始化为红色，因为插入红色节点对红黑树性质的破坏相对较小RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};// 定义红黑树的模板结构体
template<class K, class V>
struct RBTree
{// 重定义节点类型，方便后续使用typedef RBTreeNode<K, V> Node;
public:// 这里可以添加插入、删除、查找等操作的函数声明和实现// ......private:// 红黑树的根节点指针，初始化为空指针Node* _root = nullptr;public:// 记录旋转操作的次数，用于调试和性能分析int _rotateCount = 0;
};

1. 颜色枚举类型 Colour

定义了两种颜色：红色（RED）和黑色（BLACK）。红黑树通过节点的颜色来维护树的弱平衡性质。

2. 节点结构体 RBTreeNode

• 指针成员：
  • _left 和 _right 分别指向左右子节点，用于构建树的层次结构。
  • _parent 指向父节点，这在插入和删除操作中非常重要，因为在调整树的结构时，需要回溯到父节点甚至更高层的节点来进行旋转和颜色调整。
• 键值对 _kv：存储实际的数据，键类型为 K，值类型为 V。红黑树可以作为一种关联容器，通过键来快速查找对应的值。
• 颜色成员 _col：节点的颜色，使用 Colour 枚举类型表示。新节点默认初始化为红色，因为插入红色节点时，只要父节点不是红色，就不会破坏红黑树的性质，相比插入黑色节点，调整的复杂度更低。

3. 红黑树结构体 RBTree

• 根节点指针 _root：指向红黑树的根节点，初始化为空指针，表示空树。
• 旋转计数变量 _rotateCount：用于记录旋转操作的次数。旋转操作是红黑树调整结构的关键步骤，通过旋转可以在不破坏红黑树性质的前提下，平衡树的高度，减少查找、插入和删除操作的时间复杂度。这个变量可以用于调试和性能分析，帮助我们了解红黑树在不同操作下的调整情况。

插入

代码

    bool Insert(const pair<K, V>& kv){//空树处理if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}//寻找插入位置Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}//插入新节点cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//平衡调整（关键步骤）while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left)//情况一：父节点是祖父的左孩子{Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)// 叔叔存在且为红{// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在 或 存在且为黑{if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // 情况二：父节点是祖父的右孩子{Node* uncle = grandfather->_left;// uncle存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;// 确保根节点为黑return true;}

思路分析

1. 空树处理

• 若根节点 _root 为空，直接创建新节点作为根，颜色设为黑色。

2. 寻找插入位置

• 从根节点开始遍历，比较键值：

  • 若插入键 > 当前节点键，向右子树查找

  • 若插入键 < 当前节点键，向左子树查找

  • 若键已存在，返回插入失败

3. 插入新节点

• 创建新节点（颜色为红色），链接到父节点的左/右子节点，并设置父指针。

4. 平衡调整（关键步骤）

循环条件：父节点存在且为红色（仅需处理父为红的情况）。

情况一：父节点是祖父的左孩子

• 叔叔存在且为红：

  1. 变色：父节点和叔叔变黑，祖父变红。

  2. 继续向上处理：将祖父设为当前节点（父节点、祖父节点也要调整），继续向上调整。

• 叔叔不存在或为黑：

  • 当前节点是父的左孩子（LL型）：

    1. 右旋祖父节点。

    2. 父变黑，祖父变红。

  • 当前节点是父的右孩子（LR型）：

    1. 先左旋父节点，转为 LL 型。

    2. 再右旋祖父节点。

    3. 当前节点变黑，祖父变红。

情况二：父节点是祖父的右孩子

• 叔叔存在且为红：处理同情况一（变色后上移）。

• 叔叔不存在或为黑：

  • 当前节点是父的右孩子（RR型）：

    1. 左旋祖父节点。

    2. 父变黑，祖父变红。

  • 当前节点是父的左孩子（RL型）：

    1. 先右旋父节点，转为 RR 型。

    2. 再左旋祖父节点。

    3. 当前节点变黑，祖父变红。

5. 确保根节点为黑

• 最终将根节点颜色设为黑色。

旋转操作

左单旋和右单旋

private:void RotateL(Node* parent){++_rotateCount;Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){++_rotateCount;Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}

红黑树的左单旋和右单旋跟AVL树的思路一样，唯一不同的是最后不需要调整平衡因子。

平衡验证

代码

private:bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)路径黑色节点数是否一致。return false;return true;}if (root->_col == BLACK){++blacknum;}//是否存在连续红色节点。if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK)//确保根节点为黑色。{return false;}// 统计最左路径黑色节点数作为基准值。int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);//调用 CheckColour 递归验证。}public:bool IsBalance(){return IsBalance(_root);}

思路分析

1.IsBalance 入口函数：

• 确保根节点为黑色。

• 统计最左路径黑色节点数作为基准值。

• 调用 CheckColour 递归验证。

2.CheckColour 递归检查：

• 路径黑色节点数是否一致。

• 是否存在连续红色节点。

二、map和set的封装实现

1.红黑树改造

1.1 节点结构改造

template<class T>
struct RBTreeNode {RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;          // 存储数据（set存key，map存pair）Colour _col;      // 节点颜色RBTreeNode(const T& data): _data(data), _col(RED), _left(nullptr), _right(nullptr), _parent(nullptr) {}
};

设计要点：

• 使用模板参数T统一存储数据类型

• set实例化时T=K，map实例化时T=pair<const K,V>

• 保持红黑树基础结构（三叉链、颜色标记）

1.2 红黑树模板参数设计

template<class K, class T, class KeyOfT>
class RBTree {// K: 键值类型// T: 节点数据类型// KeyOfT: 仿函数，用于提取比较键值typedef RBTreeNode<T> Node;
public:// 同一个类模板，传的不同的参数实例化出的不同类型typedef __TreeIterator<T, T*, T&> iterator;typedef __TreeIterator<T, const T*, const T&> const_iterator;//...（省略插入、查找、删除等操作）
};

关键参数说明：

参数	set实例化	map实例化
K	Key类型	Key类型
T	Key类型	pair<const Key, Value>
KeyOfT	SetKeyOfT（返回自身）	MapKeyOfT（返回pair.first）

1.3 仿函数实现细节

// Set侧的键值提取
struct SetKeyOfT {const K& operator()(const K& key) {return key;  // 直接返回Key本身}
};// Map侧的键值提取
struct MapKeyOfT {const K& operator()(const pair<K, V>& kv) {return kv.first;  // 仅提取pair中的Key部分}
};

作用：

• 统一比较接口，避免直接比较pair类型的对象

• 保证比较逻辑的一致性（只使用Key部分进行比较）

2.迭代器系统实现

2.1 迭代器核心结构

template<class T, class Ptr, class Ref>
struct __TreeIterator {typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ptr, Ref> Self;typedef __TreeIterator<T, T*, T&> Iterator;Node* _node;// 支持普通迭代器构造const迭代器__TreeIterator(const __TreeIterator<T, T*, T&>& it): _node(it._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->_left){Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;}else{// 孩子是父亲的右的那个节点Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}// 前置++操作符Self& operator++() {if (_node->_right) {// 右子树存在，找右子树最左节点Node* subLeft = _node->_right;while (subLeft->_left) {subLeft = subLeft->_left;}_node = subLeft;} else {// 右子树不存在，向上查找祖先（下一个访问的是孩子父亲是左的那个祖先）Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right) {cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};

遍历特性：

• 实现红黑树的中序遍历（升序访问）

• 时间复杂度：均摊O(1)

• 空间复杂度：O(1)（无需栈结构）

2.2 迭代器在树中的应用

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&> const_iterator;iterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return const_iterator(leftMin);}const_iterator end() const{return const_iterator(nullptr);}//省略其他操作};

2.3 容器迭代器定义 

// map侧迭代器定义
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;// set侧迭代器定义
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

关键差异：

容器	迭代器类型	可修改性
map	普通迭代器	可修改value，不可修改key
set	const迭代器	完全不可修改元素

3.插入操作深度解析

3.1 插入函数改造

pair<iterator, bool> Insert(const T& data)
{// [1] 空树处理if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}// [2] 查找插入位置Node* parent = nullptr;Node* cur = _root;KeyOfT kot;while (cur) {parent = cur;if (kot(cur->_data) < kot(data))cur = cur->_right;else if (kot(cur->_data) > kot(data))cur = cur->_left;elsereturn make_pair(iterator(cur), false);}// [3] 创建新节点cur = new Node(data);cur->_col = RED;  // 新节点初始为红色// ... 连接节点 ...// [4] 平衡调整（核心逻辑）while (parent && parent->_col == RED) {// 处理红红冲突// 包含颜色翻转、旋转等操作...}_root->_col = BLACK;  // 确保根节点为黑色return make_pair(iterator(newnode), true);
}

关键改进点：

• 返回值改为pair<iterator, bool>，便于获取插入位置

• 使用KeyOfT仿函数统一比较逻辑

3.2 返回值处理

// map侧直接转发
pair<iterator, bool> insert(const pair<K, V>& kv) {return _t.Insert(kv);
}// set侧需要处理const迭代器
pair<iterator, bool> insert(const K& key) {auto ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);
}

特殊处理：

• set的iterator本质是const_iterator，防止修改Key值

• 通过迭代器构造函数实现普通迭代器到const迭代器的转换（具体实现见迭代器核心结构处的代码）

4.容器完整实现

map完整实现

template<class K, class V>
class map {struct MapKeyOfT {const K& operator()(const pair<const K, V>& kv) {return kv.first;}};typedef RBTree<K, pair<const K, V>, MapKeyOfT> RBTree;
public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin() { return _t.begin(); }iterator end() { return _t.end(); }V& operator[](const K& key) {pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv) {return _t.Insert(kv);}private:RBTree _t;
};

set完整实现

template<class K>
class set {struct SetKeyOfT {const K& operator()(const K& key) {return key;}};typedef RBTree<K, K, SetKeyOfT> RBTree;
public:typedef typename RBTree::const_iterator const_iterator;typedef typename RBTree<K, pair<const K, V>,SetKeyOfT>::const_iterator const_iterator;iterator begin() const { return _t.begin(); }iterator end() const { return _t.end(); }pair<iterator, bool> insert(const K& key) {auto ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);}private:RBTree _t;
};