1.红黑树的概念
红黑树是一种自平衡二叉搜索树，它通过特定的规则保证树的高度始终保持在 O (log n) 级别，从而确保插入、删除和查找等操作的时间复杂度为 O (log n)。
1.1红黑树的关键特性：
- 每个节点要么是红色，要么是黑色
- 根节点必须是黑色
- 所有叶子节点（NIL 节点，空节点）都是黑色
- 如果一个节点是红色，则它的两个子节点都是黑色（即不存在连续的红色节点）
- 从任意节点到其所有后代叶子节点的路径中，均包含相同数量的黑色节点
1.2红黑树保证最长路径不超过最短路径2倍的原理
黑色节点数量约束
红黑树的特性规定：从任意节点到其所有后代叶子节点的路径中，黑色节点的数量必须相同（称为 "黑高"）。这意味着所有路径的黑色节点数量相等。红色节点不连续规则
红黑树禁止两个连续的红色节点（如果一个节点是红色，其子女必须是黑色）。这意味着红色节点最多只能间隔出现。最长路径与最短路径的关系推导
- 最短路径：全部由黑色节点组成（不含红色节点），长度等于黑高（设为 h）。
- 最长路径：红色节点与黑色节点交替出现（红黑相间），由于红色节点最多与黑色节点数量相等，因此最长路径长度最多为 2h（h 个黑色节点 + h 个红色节点）。
因此，最长路径长度（2h）不会超过最短路径长度（h）的 2 倍，这一约束保证了红黑树的近似平衡性，使得树的高度始终保持在 O (log n) 级别，确保了各种操作的高效性。
1.3红黑树效率推导
红黑树的效率核心在于树高 h ≤ 2log₂(n+1)，其中 n 为节点数。推导过程如下：
定义黑高
设根节点的黑高为 bh（从根到叶的黑色节点数，不含根则为 bh-1）。
根据特性 5，所有路径的黑高相等。最短路径长度
最短路径全由黑色节点组成，长度为 bh-1（不含根）。最长路径长度
最长路径红黑交替（因无连续红节点），故长度≤2 (bh-1)（红节点最多与黑节点数量相等）。节点数下限
考虑一棵黑高为 bh 的红黑树，其节点数 n 至少为
n ≥ 2^bh - 1（类比满二叉树：黑高 bh 对应至少 2^bh-1 个节点，红节点可额外增加节点数）
树高上限推导
由 n ≥ 2^bh - 1 → bh ≤ log₂(n+1)
结合最长路径长度≤2 (bh-1)，得树高：
h ≤ 2bh ≤ 2log₂(n+1)操作效率分析
查找操作
查找路径长度与树高成正比，由 h ≤ 2log₂(n+1)，故时间复杂度为 O (log n)。插入 / 删除操作
- 基础插入 / 删除与二叉搜索树相同，时间 O (log n)。
- 平衡调整（旋转和变色）：
- 旋转操作仅需 O (1) 时间，且最多执行 2 次（因红黑树的调整范围有限）。
- 变色操作虽可能沿路径向上传播，但路径长度为 O (log n)，故总调整时间仍为 O (log n)。
因此，插入和删除的总时间复杂度为 O (log n)。
2.红黑树实现
2.1红黑树节点结构
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)
{
}
};- 红黑树相对于普通的二叉搜索树，多了父节点指针，多了标志位（颜色）
- 父节点指针便于后序在插入节点后修改祖先节点的颜色。
2.2红黑树的插入
红黑树插入的基本过程
- 插入节点不能违反，红黑树的结构规则。
- 第一个规则：每个节点非红即黑，不用考虑，用枚举即可解决
- 第二个：根节点为黑色，在插入函数中注意处理该情况
- 第三个：叶子节点为黑色，不用考虑
- 在处理最后两个规则前，我们要思考插入的新节点默认是红节点还是黑节点，如果默认插入黑节点，考虑到第五条，每个路径黑节点数量一致，所以在找到插入位置后，如果在该位置插入黑节点，那么新增节点所在路径新增一个黑节点，很难解决所有路径黑节点数量相同。
- 因此只能插入红节点，如果插入红节点的父节点是黑色，不用处理。父节点是红色，插入的节点只会影响该节点所在路径，不会影响其他的路径，更好处理。
红黑树连续红色的处理方法：变色+旋转
情况1：变色
出现该种情况的条件：
cur节点为红，parent节点为红，grandparent节点为黑，uncle节点存在且为红
解决方法：将parent节点与uncle节点变为黑，grandparent节点变为红，把grandparent节点当作新的cur，继续向上更新变色。
解释：当把parent节点和uncle节点变为黑色后，使得grandparent节点向下的子树中所有路径多一个黑节点，该子树在整个树中包含的路径比其他路径多一个黑节点，此时只需要把parent，uncle节点共同的根节点（grandparent）变为红色，这样就恢复到插入前黑节点的数量，此时还没结束，grandparent->parent节点肯能还是红的，需要对grandparent以上三个节点重复变色操作，直到grandparent的父节点为黑色，或更新到根节点。
如果更新后根节点为红色，只需要最后无脑变为黑色，根节点变黑，所有路径多一个黑节点，符合第五个规则。
情况二：单旋+变色
出现该种情况的条件：
c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点（如果u不存在那么grandparent一定没有右孩子，那么右子树只有grandparent一个黑节点，左子树也应该只有它一个黑节点，如果不是新增，parent还是红节点，parent的孩子就只能是红节点，这违反了红黑树的规则），u存在且为⿊，则 c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，变⾊将c从⿊⾊变成红⾊，更新上 来的。
分析：此时包括uncle节点在内的右子树中黑色节点个数为hb个，包括parent在内的左子树黑节点的个数为hb个，如果只变色不旋转（parent变为黑色），此时包括parent在内的左子树黑色节点为hb+1个，而uncle本来就是黑色，包括uncle在内的右子树黑色节点个数不变为hb个，左右子树黑色节点不同
旋转的目的：
把parent（红色节点）旋转到顶部成为该树的根节点，变为黑色，与原来相比红色节点减少，黑色节点不变，把原根节点旋转到右子树变为红色节点，右子树的黑色节点仍不变，左右子树黑色节点依旧相同，同时也解决了连续的红色节点的问题。
做单旋和该图的形状返回来，逻辑基本一直，旋转中心都是grandparent。
情况3：双旋+变色
出现条件：
c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点，u存在且为⿊，则 c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。
分析
p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解 决问题，需要旋转+变⾊。
如果p是g的左，c是p的右，那么先以p为旋转点进⾏左单旋，再以g为旋转点进⾏右单旋，再把c变
⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。
如果p是g的右，c是p的左，那么先以p为旋转点进⾏右单旋，再以g为旋转点进⾏左单旋，再把c变
⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则
插入代码实现
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 (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
// g
// p u
//c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{ // g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}2.3红黑树的查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}红黑树整体代码
#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)
{
}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
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 (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
// g
// p u
//c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{ // g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
if (_root == nullptr)
return true;
if (_root->_col == RED)
return false;
Node* leftMost = _root;
int blackRef = 0;
while (leftMost)
{
if (leftMost->_col == BLACK)
++blackRef;
leftMost = leftMost->_left;
}
return Check(_root, 0, blackRef);
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
private:
int _Size(Node* root)
{
return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool Check(Node* cur, int blackNum, const int blackNumRef)
{
if (cur == nullptr)
{
if (blackNum != blackNumRef)
{
cout << "黑色节点的数量不相等" << endl;
return false;
}
return true;
}
if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED)
{
cout << cur->_kv.first << "->" << "连续的红色节点" << endl;
return false;
}
if (cur->_col == BLACK)
++blackNum;
return Check(cur->_left, blackNum, blackNumRef)
&& Check(cur->_right, blackNum, blackNumRef);
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
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;
}
}
private:
Node* _root = nullptr;
};