一、红黑树
1.概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出2倍,因而是接近平衡的。
2.性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的,则它的两个孩子结点是黑色的(没有连续的红色节点,可以有连续的黑色节点)
- 每条路径均包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
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 树高度
性能差异分析:
-
操作复杂度对比
操作类型 AVL树 红黑树 查找 O(h) O(h) 插入 O(h) O(h) 删除 O(h) O(h) -
实际效率表现
- 查找: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. 平衡调整(关键步骤)
循环条件:父节点存在且为红色(仅需处理父为红的情况)。
情况一:父节点是祖父的左孩子
-
叔叔存在且为红:
-
变色:父节点和叔叔变黑,祖父变红。
-
继续向上处理:将祖父设为当前节点(父节点、祖父节点也要调整),继续向上调整。
-
-
叔叔不存在或为黑:
-
当前节点是父的左孩子(LL型):
-
右旋祖父节点。
-
父变黑,祖父变红。
-
-
当前节点是父的右孩子(LR型):
-
先左旋父节点,转为 LL 型。
-
再右旋祖父节点。
-
当前节点变黑,祖父变红。
-
-
情况二:父节点是祖父的右孩子
-
叔叔存在且为红:处理同情况一(变色后上移)。
-
叔叔不存在或为黑:
-
当前节点是父的右孩子(RR型):
-
左旋祖父节点。
-
父变黑,祖父变红。
-
-
当前节点是父的左孩子(RL型):
-
先右旋父节点,转为 RR 型。
-
再左旋祖父节点。
-
当前节点变黑,祖父变红。
-
-
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: 仿函数,用于提取比较键值
};
关键参数说明:
参数 | 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;Node* _node;// 支持普通迭代器构造const迭代器__TreeIterator(const __TreeIterator<T, T*, T&>& it): _node(it._node) {}// 解引用操作符Ref operator*() { return _node->_data; }// 成员访问操作符Ptr operator->() { return &_node->_data; }// 前置++操作符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 容器迭代器定义
// map侧迭代器定义
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;// set侧迭代器定义
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator 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::iterator 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 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;
};