红黑树详解与实现
0. 前言
在上一篇文章中,我们从零实现了 AVL 树,深入理解了二叉搜索树的平衡思想。然而,AVL 树虽然严格平衡,但插入和删除操作频繁时,频繁的旋转会带来较大的性能损耗。
为了在'平衡性'和'性能'之间取得更好的折中,红黑树(Red-Black Tree)应运而生。它通过为每个结点引入'颜色属性',并对节点间的颜色分布施加约束,使得树在近似平衡的状态下仍能保持高效的查找、插入与删除性能。
红黑树是一种自平衡二叉搜索树,通过颜色标记和旋转操作维持近似平衡。其核心性质包括根节点黑色、无连续红色节点、任意路径黑节点数相同等。插入新节点时若违反性质,需通过变色或旋转(左旋/右旋)调整。相比 AVL 树,红黑树在频繁增删场景下性能更优,是 C++ STL map/set 的底层结构。详细解析了红黑树的定义、性质、插入逻辑及完整代码实现,并对比了与 AVL 树的性能差异。

在上一篇文章中,我们从零实现了 AVL 树,深入理解了二叉搜索树的平衡思想。然而,AVL 树虽然严格平衡,但插入和删除操作频繁时,频繁的旋转会带来较大的性能损耗。
为了在'平衡性'和'性能'之间取得更好的折中,红黑树(Red-Black Tree)应运而生。它通过为每个结点引入'颜色属性',并对节点间的颜色分布施加约束,使得树在近似平衡的状态下仍能保持高效的查找、插入与删除性能。
红黑树并不追求绝对平衡,而是通过「颜色规则 + 局部旋转」实现'动态平衡'。
这种思想也正是 C++ STL 容器
map/set的底层核心机制。
本文将从最基本的概念出发,逐步剖析红黑树的性质、插入规则、旋转逻辑,并最终完成一个完整可运行的红黑树实现。 我们还将通过与 AVL 树的性能对比,深入理解红黑树在实际工程场景中的优势与应用价值。
我们之前学习过了二叉搜索树和 AVL 树,红黑树和 AVL 树一样,也是一棵自平衡的二叉搜索树。AVL 树通过控制左右子树的高度差不超过 1 来保持平衡,而红黑树则是为每个结点增加一个存储位来表示结点的颜色,可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束。
红黑树:一种自平衡二叉搜索树,由德国计算机科学家 Rudolf Bayer 在 1972 年发明,当时被称为对称二叉 B 树,后来被 Leo J. Guibas 和 Robert Sedgewick 改进并命名为红黑树。
map 和 set 底层实现TreeMap 等库的实现红黑树的性质:
性质解读:
NIL) 都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点,而是我们说的空结点,有些书籍上也把 NIL 叫做外部结点。NIL 是为了方便准确的标识出所有路径,《算法导论》在后续讲解实现的细节中也忽略了 NIL 结点,所以我们知道一下这个概念即可。NIL 结点即为红黑树的空结点性质总结:
左根右:由于它是二叉搜索树,所以左子树的值 < 根的值 < 右子树的值; 根叶黑:根节点和叶子节点 (NIL) 都是黑色的; 不红红:一条路径上不会出现两个连续的红色节点; 黑路同:任意两条路径上的黑色节点个数相同。
因此,红黑树的性质可以简记为:左根右,根叶黑,不红红,黑路同。
树路径的计算:
如果树路径的计算不包含空节点,那么以下这棵树会被解读成红黑树,但其实这棵树不是红黑树 (违反性质 4)
红黑树路径规则推导:
bh(black height,黑色高度)2*bh(单条路径黑色结点数量最多为 bh,红色结点数量最多也为 bh)enum Colour { Red, Black };
template<class K, class V>
struct RBTreeNode {
// 三叉链
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
// 红黑树需要旋转,因此设计为三叉链,保存父节点的地址
pair<K, V> _kv; // 键值对
Colour _col; // 表示结点的颜色
// 新结点默认是红色的
RBTreeNode(const pair<K, V>& kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(Red) {}
};
std::pair<K, V> 来存储我们的键值对数据RBTreeNode<K, V>* _left:指向左孩子的指针RBTreeNode<K, V>* _right:指向右孩子的指针RBTreeNode<K, V>* _parent:指向父节点的指针RBTreeNode(const pair<K, V>& kv):
nullptr,初始化结点颜色为 Redkv 初始化类内的 _kv 成员struct 设计,默认权限为 public,方便下文的 RBTree 类访问成员思考:在节点的定义中,为什么要将节点的默认颜色给成红色的?
template<class K, class V>
class RBTree {
typedef RBTreeNode<K, V> Node;
RBTreeNode<K, V>* _root = nullptr;
public:
// ... 对外共有接口
private:
// ... 内部私有成员函数
};
typedef RBTreeNode<K, V> Node;:结点类型重定义,简化书写RBTree<K, V>* _root = nullptr:初始时根节点为空当我们对一棵空的红黑树进行插入时,直接插入并把其颜色设置为黑色即可。
(下面所讨论的插入操作都是建立在树非空的情况之上)
首先我们需要明确一点,在红黑树非空的情况下,我们插入一个节点的颜色必定是红色。
如果我们把插入节点的颜色设置为黑色的话,那么此时这棵红黑树就必然会违反黑路同的性质,插入黑色结点会对其他路径造成影响 (黑路同),之后想要把每条路上的黑色节点数量调整为一样多的话就会非常麻烦。所以从这个角度来看,树非空的情况下我们插入的节点都设置为红色。
我们插入的节点为红色,
但是,此时由于爷爷变红,可能又会导致出现两个红色节点相邻的情况,因为爷爷的父亲可能为红色。此时我们只需要把爷爷当作新插入的节点,重复上面的操作即可。下面是图片演示
如果此时插入节点的父亲节点在爷爷节点的右边 (right),插入节点在父亲节点的左边 (left),那么我们把这种情况成为 RL 型。如果是 RL 型,那么需要将以爷爷节点为根的子树进行右左双旋操作,旋转之后将 cur 和爷爷节点进行变色,插入结束。
这种情况与 LR 型完全对称,这里不再画图演示
这里的旋转操作和 AVL 树的旋转操作一致,只需把 AVL 树中的更新平衡因子的步骤去掉
// 左单旋 2 1 newNode 连成线,单纯的右边高
void RotateL(Node* parent) {
_rotateCount++; // 测试旋转次数
if (parent == nullptr || parent->_right == nullptr) return;
Node* curNode = parent->_right;
Node* curLeft = curNode->_left; // curLeft 有可能为空
// 先处理 curNode 的 left 结点,curLeft 有可能是空
parent->_right = curLeft;
if (curLeft) curLeft->_parent = parent;
// 再处理 curNode 结点
// parent 有可能是根节点,也有可能是子树的根节点
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
parent->_parent = curNode;
curNode->_left = parent;
} else {
Node* ppNode = parent->_parent; // 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子
if (parent == ppNode->_left) ppNode->_left = curNode;
else ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
parent->_parent = curNode;
curNode->_left = parent;
}
}
// 右单旋 -2 -1 newNode 连成线,单纯的左边高
void RotateR(Node* parent) {
_rotateCount++; // 测试旋转次数
// parent 为空 或 curNode 为空的情况
if (parent == nullptr || parent->_left == nullptr) return;
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
// 把 curNode 的 right 给给 parent 的 left
parent->_left = curRight;
if (curRight) curRight->_parent = parent;
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
curNode->_right = parent;
parent->_parent = curNode;
} else {
Node* ppNode = parent->_parent; // 找 parent 是 ppNode 的左还是右
if (parent == ppNode->_left) ppNode->_left = curNode;
else ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
curNode->_right = parent;
parent->_parent = curNode;
}
}
bool insert(const pair<K, V>& kv) {
// 先走二叉搜索树的插入逻辑
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = Black; // 性质 根节点是黑色的
return true;
}
// _root 不为空时,二叉搜索树的逻辑
Node* parent = nullptr;
Node* curNode = _root;
// 先找空,找到一个可以插入的位置
while (curNode) {
if (kv.first < curNode->_kv.first) {
parent = curNode;
curNode = curNode->_left;
} else if (kv.first > curNode->_kv.first) {
parent = curNode;
curNode = curNode->_right;
} else {
// 搜索树中不允许有重复的值 对于已有值,不插入
return false;
}
}
// while 循环结束后,代表找到了可以插入的位置
// 找到位置了,但父节点不知道 新结点比自己大还是比自己小
curNode = new Node(kv);
if (curNode->_kv.first < parent->_kv.first) parent->_left = curNode;
else parent->_right = curNode;
curNode->_parent = parent;
// 以上是二叉搜索树的插入逻辑,这样插入可能导致树不平衡,从而导致查找效率退化为 O(n)
// 以下是红黑树的性质控制,是对二叉搜索树 进行的 控制平衡 操作
// 控制近似平衡 ...
// while 循环控制 颜色继续往上更新
// 新插入的结点为红色 因此 parent 存在且 parent 为红色时,才需要更新颜色
while (parent && parent->_col == Red) {
Node* grandFather = parent->_parent;
// parent 在 grandFather 左的场景
if (parent == grandFather->_left) {
Node* uncle = grandFather->_right;
// 情况一 cur 为红 parent 为红 grandFather 为黑,uncle 存在且为红
if (uncle && uncle->_col == Red) {
// p 和 u 变黑,g 变红,cur 变成 grandFather 继续往上更新
// 变色
parent->_col = uncle->_col = Black;
grandFather->_col = Red;
// 继续向上处理
curNode = grandFather;
parent = curNode->_parent;
// 如果更新完后 grandFather 为红色:
// 1. g 为根节点,那么 parent 为空
// 2. g 上面还有结点
// 如果是黑色的,无需处理,进不去循环
// 如果是红色,继续处理
}
// u 不存在 或 u 存在且为黑
else {
// 左左 -> 右单旋
if (curNode == parent->_left) {
// g
// p
// c
RotateR(grandFather);
parent->_col = Black;
grandFather->_col = Red;
}
// 左右 -> 左右双旋
else {
// g
// p
// c
RotateL(parent);
RotateR(grandFather);
curNode->_col = Black;
grandFather->_col = Red;
}
break;
}
}
// parent 在 grandFather 右的场景
else {
Node* uncle = grandFather->_left;
// 情况一 cur 为红 parent 为红 grandFather 为黑,uncle 存在且为红
if (uncle && uncle->_col == Red) {
// p 和 u 变黑,g 变红,cur 变成 grandFather 继续往上更新
// 变色
parent->_col = uncle->_col = Black;
grandFather->_col = Red;
// 继续向上处理
curNode = grandFather;
parent = curNode->_parent;
// 如果更新完后 grandFather 为红色:
// 1. g 为根节点,那么 parent 为空
// 2. g 上面还有结点
// 如果是黑色的,无需处理,进不去循环
// 如果是红色,继续处理
}
// u 不存在 或 u 存在且为黑
else {
// 右右 -> 左单旋
if (curNode == parent->_right) {
// g
// p
// c
RotateL(grandFather);
parent->_col = Black;
grandFather->_col = Red;
}
// 右左 -> 右左双旋
else {
// g
// p
// c
RotateR(parent);
RotateL(grandFather);
curNode->_col = Black;
grandFather->_col = Red;
}
break;
}
}
}
// 继续向上处理 parent = curNode->_parent 如果 parent == nullptr 会结束循环
// parent == nullptr 结束循环时,curNode 为_root 结点,需要对 _root 节点变色
_root->_col = Black;
// 粗暴的处理,直接将根节点设为黑色,根节点为黑色总是正确的
return true;
}
求树的高度思路如下:
int Height() {
return _Height(_root);
}
int _Height(Node* root = _root) {
if (root == nullptr) return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool isBalance() {
return _isBalance(_root);
}
// 子函数
bool _isBalance(Node* root = _root) {
if (root == nullptr) return true;
// 根节点颜色不为黑,false
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);
}
_isBalance 实现以下功能:
CheckColour 函数,与其他路径的黑色节点数量进行比对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);
}
CheckColour 函数内部完成以下检查:
if (root->_col == Red && root->_parent && root->_parent->_col == Red)
false。nullptr 时,说明到达叶子。此时:
blacknum 是从根到当前叶子的黑节点数量;benchmark 是从根到某一条路径上统计得到的标准黑节点数(通常是第一次到达叶子时确定的值)。falseblacknum 是值传递,在每条递归路径中互不影响。形参传值会拷贝一份当前的 blacknum,在递归调用中独立变化。
也就是说:
#include "Red_Black_Tree.h"
#include "AVL_Tree.h"
#include <vector>
int main() {
const int N = 10000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++) {
v.push_back(rand() + i * i + 2); // 插入随机数据
//v.push_back(i); // 插入有序数据
}
RBTree<int, int> rbt;
for (auto e : v) {
rbt.insert(make_pair(e, e));
//cout << "Insert:" << e << "->" << t.isBalance() << endl;
}
cout << "红黑树是否平衡:" << rbt.isBalance() << endl;
cout << "红黑树的高度:" << rbt.Height() << endl;
cout << "红黑树的旋转次数:" << rbt._rotateCount << endl;
cout << endl << endl;
AVLTree<int, int> avlt;
for (auto e : v) {
avlt.insert(make_pair(e, e));
//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
}
cout << "AVL 树是否平衡:" << avlt.isBalance() << endl;
cout << "AVL 树的高度:" << avlt.height() << endl;
cout << "AVL 树的旋转次数:" << avlt._rotateCount << endl;
return 0;
}
#pragma once
#include <iostream>
using namespace std;
enum Colour { Red, Black };
template<class K, class V>
struct RBTreeNode {
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<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>
class RBTree {
public:
int _rotateCount = 0;
private:
typedef RBTreeNode<K, V> Node;
RBTreeNode<K, V>* _root = nullptr;
public:
bool insert(const pair<K, V>& kv) {
// 先走二叉搜索树的插入逻辑
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = Black; // 性质 根节点是黑色的
return true;
}
// _root 不为空时,二叉搜索树的逻辑
Node* parent = nullptr;
Node* curNode = _root;
// 先找空,找到一个可以插入的位置
while (curNode) {
if (kv.first < curNode->_kv.first) {
parent = curNode;
curNode = curNode->_left;
} else if (kv.first > curNode->_kv.first) {
parent = curNode;
curNode = curNode->_right;
} else {
// 搜索树中不允许有重复的值 对于已有值,不插入
return false;
}
}
// while 循环结束后,代表找到了可以插入的位置
// 找到位置了,但父节点不知道 新结点比自己大还是比自己小
curNode = new Node(kv);
if (curNode->_kv.first < parent->_kv.first) parent->_left = curNode;
else parent->_right = curNode;
curNode->_parent = parent;
// 以上是二叉搜索树的插入逻辑,这样插入可能导致树不平衡,从而导致查找效率退化为 O(n)
// 以下是红黑树的性质控制,是对二叉搜索树 进行的 控制平衡 操作
// 控制近似平衡 ...
// while 循环控制 颜色继续往上更新
// 新插入的结点为红色 因此 parent 存在且 parent 为红色时,才需要更新颜色
while (parent && parent->_col == Red) {
Node* grandFather = parent->_parent;
// parent 在 grandFather 左的场景
if (parent == grandFather->_left) {
Node* uncle = grandFather->_right;
// 情况一 cur 为红 parent 为红 grandFather 为黑,uncle 存在且为红
if (uncle && uncle->_col == Red) {
// p 和 u 变黑,g 变红,cur 变成 grandFather 继续往上更新
// 变色
parent->_col = uncle->_col = Black;
grandFather->_col = Red;
// 继续向上处理
curNode = grandFather;
parent = curNode->_parent;
// 如果更新完后 grandFather 为红色:
// 1. g 为根节点,那么 parent 为空
// 2. g 上面还有结点
// 如果是黑色的,无需处理,进不去循环
// 如果是红色,继续处理
}
// u 不存在 或 u 存在且为黑
else {
// 左左 -> 右单旋
if (curNode == parent->_left) {
// g
// p
// c
RotateR(grandFather);
parent->_col = Black;
grandFather->_col = Red;
}
// 左右 -> 左右双旋
else {
// g
// p
// c
RotateL(parent);
RotateR(grandFather);
curNode->_col = Black;
grandFather->_col = Red;
}
break;
}
}
// parent 在 grandFather 右的场景
else {
Node* uncle = grandFather->_left;
// 情况一 cur 为红 parent 为红 grandFather 为黑,uncle 存在且为红
if (uncle && uncle->_col == Red) {
// p 和 u 变黑,g 变红,cur 变成 grandFather 继续往上更新
// 变色
parent->_col = uncle->_col = Black;
grandFather->_col = Red;
// 继续向上处理
curNode = grandFather;
parent = curNode->_parent;
// 如果更新完后 grandFather 为红色:
// 1. g 为根节点,那么 parent 为空
// 2. g 上面还有结点
// 如果是黑色的,无需处理,进不去循环
// 如果是红色,继续处理
}
// u 不存在 或 u 存在且为黑
else {
// 右右 -> 左单旋
if (curNode == parent->_right) {
// g
// p
// c
RotateL(grandFather);
parent->_col = Black;
grandFather->_col = Red;
}
// 右左 -> 右左双旋
else {
// g
// p
// c
RotateR(parent);
RotateL(grandFather);
curNode->_col = Black;
grandFather->_col = Red;
}
break;
}
}
}
// 继续向上处理 parent = curNode->_parent 如果 parent == nullptr 会结束循环
// parent == nullptr 结束循环时,curNode 为_root 结点,需要对 _root 节点变色
_root->_col = Black;
// 粗暴的处理,直接将根节点设为黑色,根节点为黑色总是正确的
return true;
}
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() {
return _isBalance(_root);
}
bool _isBalance(Node* root = _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);
}
int Height() {
return _Height(_root);
}
int _Height(Node* root = _root) {
if (root == nullptr) return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
private:
// 左单旋 2 1 newNode 连成线,单纯的右边高
void RotateL(Node* parent) {
_rotateCount++; // 测试旋转次数
if (parent == nullptr || parent->_right == nullptr) return;
Node* curNode = parent->_right;
Node* curLeft = curNode->_left; // curLeft 有可能为空
// 先处理 curNode 的 left 结点,curLeft 有可能是空
parent->_right = curLeft;
if (curLeft) curLeft->_parent = parent;
// 再处理 curNode 结点
// parent 有可能是根节点,也有可能是子树的根节点
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
parent->_parent = curNode;
curNode->_left = parent;
} else {
Node* ppNode = parent->_parent; // 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子
if (parent == ppNode->_left) ppNode->_left = curNode;
else ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
parent->_parent = curNode;
curNode->_left = parent;
}
}
// 右单旋 -2 -1 newNode 连成线,单纯的左边高
void RotateR(Node* parent) {
_rotateCount++; // 测试旋转次数
// parent 为空 或 curNode 为空的情况
if (parent == nullptr || parent->_left == nullptr) return;
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
// 把 curNode 的 right 给给 parent 的 left
parent->_left = curRight;
if (curRight) curRight->_parent = parent;
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
curNode->_right = parent;
parent->_parent = curNode;
} else {
Node* ppNode = parent->_parent; // 找 parent 是 ppNode 的左还是右
if (parent == ppNode->_left) ppNode->_left = curNode;
else ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
curNode->_right = parent;
parent->_parent = curNode;
}
}
};
int main() {
const int N = 10000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++) {
v.push_back(rand() + i); // 插入随机数据
//v.push_back(i); // 插入有序数据
}
RBTree<int, int> rbt;
for (auto e : v) {
rbt.insert(make_pair(e, e));
//cout << "Insert:" << e << "->" << t.isBalance() << endl;
}
cout << "红黑树是否平衡:" << rbt.isBalance() << endl;
cout << "红黑树的高度:" << rbt.Height() << endl;
cout << "红黑树的旋转次数:" << rbt._rotateCount << endl;
cout << endl << endl;
AVLTree<int, int> avlt;
for (auto e : v) {
avlt.insert(make_pair(e, e));
//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
}
cout << "AVL 树是否平衡:" << avlt.isBalance() << endl;
cout << "AVL 树的高度:" << avlt.height() << endl;
cout << "AVL 树的旋转次数:" << avlt._rotateCount << endl;
return 0;
}
红黑树作为一种'近似平衡'的二叉搜索树,通过颜色标记与旋转调整,在插入与删除操作频繁的场景下有效避免了 AVL 树的高频旋转问题。
它在时间复杂度上与 AVL 树相同,都是 O(logN),但实际应用中更具工程价值,因此成为了 STL map、set、multimap、multiset 等容器的底层数据结构。
本文自底向上实现了红黑树的插入、变色与旋转机制,并通过与 AVL 树的对比,揭示了红黑树在平衡效率与维护开销上的折中之美。
✅ 红黑树的核心思想:不追求完美平衡,而是保证最长路径不超过最短路径的 2 倍;通过简单的局部旋转与变色操作实现全局近似平衡;用颜色规则取代复杂的高度平衡因子,使得结构更简洁、效率更高。
红黑树的实现也标志着我们正式跨入了 C++ STL 底层机制探索的第二阶段。
下一步,我们将基于该结构实现 map、set 等容器,深入理解 迭代器、模板参数与仿函数 在标准库中的实际应用。

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
将JSON字符串修饰为友好的可读格式。 在线工具,JSON美化和格式化在线工具,online