C++红黑树是一种自平衡二叉搜索树，利用颜色标记节点以维持近似平衡。其核心规则涵盖根节点颜色、红色节点子节点限制及路径黑节点数量一致性。插入操作需处理变色、单旋及双旋三种情形以修复违规。本文阐述了红黑树结构、查找效率分析、插入算法细节及验证方法，并提供了完整的 C++ 模板代码示例，适用于理解 STL 容器底层机制。
红黑树是一种二叉搜索树，它的每个节点增加一个存储代表着该节点的颜色，和它的名字一样，节点的颜色可以是红色或者是黑色。通过对任何一条根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。
红黑树是被很多条规则进行束缚的二叉搜索树，通过这些规则，可以保证红黑树没有一条路径会比其他路径长出 2 倍，并且保持其相对平衡，下面我来讲述一下这些规则。
以上便就是红黑树的四条规则，其实《算法导论》上也是补充了一个知识点：每个叶子节点（NULL）都是黑色的规则。他这里所指的叶子节点不是传统意义上的叶子节点，而是我们所说的空节点，有些书籍上也把 NULL 叫做外部节点。NULL 是为了方便准确的标志处所有路径，《算法导论》在后续实现的细节中忽略了 NULL 节点，所以我们知道这个概念即可。
由规则 4 可以知道，每条路径上有着数量相同的黑色节点，所以在极端场景下，就比如上面最后一个图，一条路上全都是黑色节点，最短路径其实就是一条路上全是黑色节点，我们将最短路径的长度记作 bh。
在看规则 2 和规则三，我们可以清楚的知道，一条路上不会出现连续的红色节点，所以我们容易知道最长路径应该是一红一黑交织组成，所以最长路径的长度是 2bh。
根据红黑树的规则，我们可以知道一般情况下的红黑树的路径是由数量不等的红黑节点组成的，一红一黑交织进行和全是黑的是不太容易出现的，所以假设红黑树一条路径的长度为 h，所以 bh<=h<=2bh，即红黑树的最长路径不会是最短路径的两倍。
我们假设红黑树的节点个数为 N，最短路径的长度为 h，所以可知：2^h - 1 <= N < 2^2*h - 1，由此可以推出 h 大约等于 logN，也就是红黑树查找的效率问题最差也是 2 * logN，时间复杂度终归还是 O(log(N))。
红黑树的表达相对 AVL 树是要更抽象一些的，AVL 树可以根据高度更加直观的看出树的平衡，而红黑树则是需要根据四条规则的颜色进行约束，间接的实现近似平衡，他们的效率都是同一档次的，但是相对而言，插入相同数量的节点，红黑树的旋转次数变的更少了，因为它对平衡的把控并不是那么的严格。
在我们书写平衡树的代码之前，通常我们需要先完善一下它的结构，就比如其中最基础的，它的每个节点应该存储什么的数据，红黑树也是一个典型的三叉链，所以它的节点需要包含它的父节点以及左右孩子节点，并且由于红黑树是通过颜色进行平衡的位置，我们还需要设置好一个联合体来确定节点的颜色，我们默认颜色就是红色，并且红黑树也是通过 Key 和 Value 进行存放数据的，Key 就好比我们开车进入商场停车场的车牌号，而 Value 就是记录进入停车场的时间的，由此来确定需要缴纳多少钱。所以由此来看 Key 就是一个标记，而红黑树真正的核心应该是 Value。下面我来展示一下红黑树结构相关的代码。
enum Colour { RED, BLACK }; // 这里我们默认按 key/value 结构实现
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) ,_col(RED) {}
};
template<class K,class V> class RBTree
{
typedef RBTreeNode<K,V> Node;
public:
private:
Node* _root = nullptr;
};
红黑树的查找和二叉搜索树的查找是一样的，代码也是比较类似的，它们的效率都是 log(N)，所以我就不在细讲了。
Node* Find(const K& key)
{
Node* cur = _root; //代替根节点去遍历
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return NULL;
}
下面我们就进入到了红黑树最难的部分（删除不算）：红黑树的插入，红黑树的插入的复杂程度还是和 AVL 数比较类似的，但是我个人感觉红黑树相对 AVL 树更加抽象一些，因为它不仅仅涉及到了旋转，还有变色的操作，依次来维持它的那四条规则，接下来我们进入红黑树的插入讲解。
在讲插入过程的时候事先说明一下：假设我们把新增的节点叫做 c(cur)，c 的父亲则标记为 p（parent），p 的父亲节点标记为 g（grandfather），p 的兄弟节点叔叔为 u（uncle）。
插入一个值是按照二叉搜索树的规则来进行的，插入后的值我们需要让其符合红黑树的四条规则。如果是空树插入，那么插入的必然就是黑色节点，因为根节点必须是黑色的；如果是非空树插入，那么插入的节点一定是红色的，因为第四条规则约束着，如果插入的是黑色节点，那么第四条规则就被破坏了。非空树在插入的时候，插入的节点必须是红色节点，如果其父节点是黑色的，那么并没有违法规则，插入成功。如果其父节点是红色的，那么就违反了第三条规则。进一步的分析，c 是红色，p 也是红色，那么 g 必然是黑色的（如果 g 也是红色的那么就说明在没有插入 c 的时候此树已经违反规则了），这三个的颜色都已经定了，所以关键的变化还得看 u 的变化，分别需要分为以下四种情况讨论，在讨论之前，我先把插入的相关代码放到下面（和二叉搜索树差不多）。
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK; //根节点一定是黑色的
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
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; //这个一定不可以忘掉
}
如上图所示，如果 c 是红的，p 为红，g 为黑，u 存在并且是红色的话，那么我们就需要进行变色处理，即将 p 和 u 都变为黑色，g 变红。再把 g 当做新的 c，继续往上进行更新。可能很多读者不晓得我这么做的原因，下面我将进行解释。
因为 p 和 u 均是红色，g 是黑色，把 p 和 u 都变为黑色，左右子树都多增加了一个黑色节点，g 变为了红色，因为着 p 和 u 所在的支路上黑色节点的个数是没有变化的，这样就没有违反规则四，并且同时解决了红色节点的孩子还是红色节点的问题；至于为何让 g 变为新的 c，因为 g 的父节点我们并不知晓是什么颜色的，倘若还是黑色，那就皆大欢喜，不用在往上进行遍历了；但是如果是红色，那么我们还需进行变色处理。不过还有一种情况，就是 g 就是整棵树的根，那么我们就需要把 g 变为黑色，因为红黑树的根节点是黑色的。
当然，上图是属于第一种变色的特殊情况，和 AVL 树类似，我们还需了解抽象状态下的 AVL 树的变色，如下图所示。
上图则是对变色进行了比较抽象的表达，d，e，f 代表着每条路径上有 hb 个黑色节点的子树，a/b 则代表着每条路径上拥有 hb-1 个黑色节点的根为红的子树，其中 hb>=0，下面这个情况就形象的代表了当我们在 a 或者 b 中进行了一次变色，传递到上面时，可能也会让上面进行变色处理。当然，情况一仅仅设计了变色的处理，而不涉及旋转，所以左右子树都是相同的变色处理，以上就是情况一的讲解，下面我们进入代码的讲解。
此时我们还需要划分此时的父亲节点是左子树还是右子树，下面我们就单拿左子树为例，因为左右子树都是差不多的，掌握了一种，另一种也是会更为轻松的掌握。
刚开始，我们需要先把 g 节点表示出来，即 p 节点的父亲节点，因为我们进行变色处理以后，需要往上进行更新，所以变色的操作应该是一次次循环的过程。
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
}
我们需要通过 if 语句确认 p 节点是在左边的，之后我们需要把 u 节点表示出来，如果此时 u 节点存在并且 u 节点就是红色的，那么就符合情况一，之后我们先把 p 和 u 节点都染成黑色的，再把 g 节点变为红色的，做完这些操作以后，我们就需要更新一下 c 和 p 节点了更新结束，代表一次变色成功，继续往上进行更新。
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
//单纯的变色处理
grandfather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
//在往上进行查询
cur = grandfather;
parent = cur->_parent;
}
}
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent; //先来节点都是左边的情况
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
//单纯的变色处理
grandfather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
//在往上进行查询
cur = grandfather;
parent = cur->_parent;
}
}
}
if(grandparent->_right == parent)
{
Node* uncle = grandfather->_left;
if (uncle&& uncle->_col == RED)
{
grandfather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
//在往上进行查询节点是否正确
cur = grandfather;
parent = cur->_parent;
}
}
又看到了我们的老朋友：单旋了，上次我们和它见面还是 AVL 树，没想到到了红黑树，它又来追杀我们了，不过红黑树的单旋其实和 AVL 树是类似的，这意味着我们可以直接使用 AVL 树的单旋代码，下面我通过一个特殊的例子来给各位讲解情况二。
如果 c 是红色，p 是红色，g 为黑，u 不存在或者 u 是黑色的时候，这个时候我们就不能单单依靠表变色进行红黑树的修正了，因为这样会违反规则四；如果 u 不存在，那么 c 一定就是新的节点；如果 u 是黑的，那么 c 一定不是新的节点，而是因为之前 c 本来就是黑色的节点，但是由于进行了变色处理，导致 c 变成了红色节点。
如果 p 是 g 的左子树，如上图所示，c 是 p 的左子树，那么我们就以 g 为旋转点，先进行一次右单旋，如下图所示。
此时我们需要让 g 变为红色，p 变为黑色即可。此时 p 变成了这棵子树新的根了，这样子树黑色节点的数量不变，没有连续的红色节点，并且还不需要往上进行更新了，因为 p 的父亲无论是啥都没会违反这些规则了。
如果 p 是 g 的右子树，c 是 p 的右，如上图所示，那么我们还是以 g 为旋转点，但是是左单旋，如下图所示。
此时我们需要让 p 变为黑色，g 变为红色即可，p 变为了新子树的根，这样子树的黑色节点的数量并没有改变，没有连续的红色节点，并且还不需要往上进行更新了。
当然，我们学完了特殊情况，还需要知晓一些抽象情况，下面我就放上一张图片，希望各位读者自行阅读。
首先我们需要先知晓，此时的情况二也是在循环之中的，此时我们还是以右单旋为例进行讲解，当 c 为 p 的左孩子时，意味着此时我们需要单旋进行处理（前提是 u 节点为黑色或者是空），那么此时我们需要进行单旋处理，单旋的话我们直接把 AVL 树的单旋 copy 过来即可（忘了的看我上一篇文章），之后在进行相应的变色处理即可。下面我把两个完整代码展示出来。
if(uncle -> col == black || uncle == nullptr)
{
if(parent -> left == cur)
{
//右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
break; //无须在往上走了
}
}
if(uncle -> col == black || uncle == nullptr)
{
if(parent -> right == cur)
{
//进行左单旋处理
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
}
既然都有单旋这种情况了，那么双旋也是必不可少的，当然，双旋的代码还是和 AVL 树是一样的，减少了很大部分的工作量。
情况三的颜色情况其实和情况二是类似的，它们均是 c 和 p 都是红色，g 为黑色，u 是不存在或者为黑色，所以下面我们进入双旋情况的讲解。
如果 p 是 g 的左，c 是 p 的右，此时我们仅仅依靠单旋是不可以进行红黑树的纠正的，所以此时我们就需要通过双旋进行调整，我们先以 p 为旋转点进行一次左旋，在以 g 进行一次右旋，如下图所示。
此时我们仅需让 c 变为黑色，g 变为红色即可，c 变成了这棵树新的根，这样做黑色节点的数目没有改变，没有连续的红色节点了，因为 g 是黑色，此时无论他的父节点是什么，都不会影响结果了。
如果此时 p 是 g 的有孩子，c 是 p 的左孩子，这个时候我们也是需要双旋进行处理的，先以 p 为旋转点进行右旋，再以 g 为旋转点进行左旋，之后把 c 变为黑色，g 为红色即可。
以上是红黑树情况二的特殊情况，下面我们来看看一般情况，即抽象表达，看一看下图的图，我相信你会懂的。
我个人认为情况三的代码比较容易，各位读者通过我上面的讲解应该就知晓代码如何书写了，所以我下面直接放代码。
//左右双旋转
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
general_father->_col = RED;
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
general_father->_col = RED;
此时我们已经讲述完了红黑树相关知识点的讲解，可能有很多读者想知道自己写的红黑树是否是正确的，下面我将给各位讲述一下如何验证自己写的红黑树。此时我们需要检验四条规则，如果满足这四条规则，那么说明这棵树就是一颗非常棒的红黑树。
bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
// 前序遍历走到空时，意味着一条路径走完了
if (refNum != blackNum)
{
cout << "存在黑色结点的数量不相等的路径" << endl;
return false;
}
return true;
}
// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << "存在连续的红色结点" << endl;
return false;
}
if (root->_col == BLACK)
{
blackNum++;
}
return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}
#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
#include<ctime>
namespace wang
{
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) ,_col(RED) {}
};
template<class K, class V> class RBTree
{
typedef RBTreeNode<K, V> Node;
private:
void RotateR(Node* parent)
{
Node* subl = parent->_left;
Node* sublR = subl->_right;
parent->_left = sublR;
if (sublR)
{
sublR->_parent = parent;
}
Node* ppnode = parent->_parent;
subl->_right = parent;
parent->_parent = subl;
if (ppnode == nullptr)
{
_root = subl;
subl->_parent = ppnode;
}
else
{
if (subl->_kv.first > ppnode->_kv.first)
{
ppnode->_right = subl;
}
else
{
ppnode->_left = subl;
}
subl->_parent = ppnode;
}
}
void RotateL(Node* parent)
{
Node* subL = parent->_right;
Node* subLL = subL->_left;
Node* ppnode = parent->_parent;
parent->_right = subLL;
if (subLL)
{
subLL->_parent = parent;
}
subL->_left = parent;
parent->_parent = subL;
if (ppnode == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (subL->_kv.first > ppnode->_kv.first)
{
ppnode->_right = subL;
}
else
{
ppnode->_left = subL;
}
subL->_parent = ppnode;
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
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)
{
grandfather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (parent->_left == cur)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle&& uncle->_col == RED)
{
grandfather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return NULL;
}
void InOrder()
{
_InOrder(_root);
}
bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
if (refNum != blackNum)
{
cout << "存在黑色结点的数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << "存在连续的红色结点" << endl;
return false;
}
if (root->_col == BLACK)
{
blackNum++;
}
return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}
bool IsBalance()
{
if (_root == nullptr) return true;
if (_root->_col == RED) return false;
int refNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++refNum;
}
cur = cur->_left;
}
return Check(_root, 0, refNum);
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
protected:
int _Size(Node* root)
{
if (root == nullptr) return 0;
return _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;
}
private:
Node* _root = nullptr;
};
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 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