C++ 红黑树原理与实现详解

本文介绍 C++ 红黑树的概念、性质及实现。红黑树是一种自平衡二叉搜索树，通过颜色约束保证路径长度不超过两倍，时间复杂度为 O(logN)。重点讲解了插入操作中的变色与旋转逻辑（单旋、双旋），并提供了完整的 C++ 代码示例及验证方法。相比 AVL 树，红黑树在插入场景下性能更优。

清心发布于 2026/3/30更新于 2026/4/131 浏览

红黑树的概念

红黑树是一棵二叉搜索树，它的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出 2 倍，因而是接近平衡的。

规则

每个结点不是红色就是黑色
根结点是黑色的
如果一个结点是红色的，则它的两个子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点
对于任意一个结点，从该结点到其所有 NULL 结点的简单路径上，均包含相同数量的黑色结点

文章配图

为上面的红黑树，有多少条路径？

答案是 10 条，因为要走到空才算一条。

在上面的规则与图中我们发现，根节点一定为黑，那么最短路径就是全黑，最长路径就是黑红黑红相间，这就实现了最短路径与最长路径是二倍的关系。

红黑树的效率

假设 N 是红黑树中结点数量，h 最短路径的长度，那么 $2^h - 1 \le N < 2^{2h} - 1$，由此推出 $h \approx \log_2 N$ 到 $2 * \log_2 N$，也就是意味着红黑树增删查改最坏也就是走最长路径，那么时间复杂度还是 O(logN)。红黑树的表达相对 AVL 树要抽象一些，AVL 树通过高度差直观的控制了平衡。红黑树通过 4 条规则的颜色约束，间接的实现近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。

红黑树的实现

红黑树实现的大致思路与前面的 AVL 类似，只不过前面的 bf 变成了此处的 color。

红黑树的大致框架

// 枚举值表示颜色
enum Colour { RED, BLACK };
// 这里我们默认按 key/value 结构实现
template<class K, class V>
struct RBTreeNode {
    // 这里更新控制平衡也要加入 parent 指针
    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 {
     RBTreeNode<K, V> Node;
:
:
    Node* _root = ;
};

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown 转 HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。在线工具，Markdown 转 HTML在线工具，online

HTML 转 Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML 转 Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

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 为空 cur = new Node(kv); cur->_col = RED; if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } // 链接父亲 cur->_parent = parent; // 变色情况 // 连续红色， // 1. 父亲为红色，连续红色 (记住，父亲都要变黑) 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 = grandfather->_parent; } else { // 单旋 + 变色 (叔叔不存在或为黑，两种情况对应的 cur 是插入还是变色为红不一样，不过处理都一样) if (cur == parent->_left) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } // 双旋 else if (cur == parent->_right) { RotateR(parent); RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else break; } } else { // 叔叔存在且为红 Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 继续往上找 cur = grandfather; parent = grandfather->_parent; } else { // 单旋 + 变色 (叔叔不存在或为黑，两种情况对应的 cur 是插入还是变色为红不一样，不过处理都一样) if (cur == parent->_right) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } // 双旋孩子与父亲在与自己相对父亲的不同子树上 else if (cur == parent->_left) { RotateL(parent); RotateR(grandfather); parent->_col = BLACK; cur->_col = BLACK; grandfather->_col = RED; } else break; } } } _root->_col = BLACK; return true; }

#pragma once #include <assert.h> #include <iostream> using namespace std; enum Colour { RED, BLACK }; template<class K, class V> struct RBTreeNode { // 这里更新控制平衡也要加入 parent 指针 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 为空 cur = new Node(kv); cur->_col = RED; if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } // 链接父亲 cur->_parent = parent; // 变色情况 // 连续红色， // 1. 父亲为红色，连续红色 (记住，父亲都要变黑) 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 = grandfather->_parent; } else { // 单旋 + 变色 (叔叔不存在或为黑，两种情况对应的 cur 是插入还是变色为红不一样，不过处理都一样) if (cur == parent->_left) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } // 双旋 else if (cur == parent->_right) { RotateR(parent); RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else break; } } else { // 叔叔存在且为红 Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 继续往上找 cur = grandfather; parent = grandfather->_parent; } else { // 单旋 + 变色 (叔叔不存在或为黑，两种情况对应的 cur 是插入还是变色为红不一样，不过处理都一样) if (cur == parent->_right) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } // 双旋孩子与父亲在与自己相对父亲的不同子树上 else if (cur == parent->_left) { RotateL(parent); RotateR(grandfather); parent->_col = BLACK; cur->_col = BLACK; grandfather->_col = RED; } else break; } } } _root->_col = BLACK; return true; } void RotateR(Node* parent) { // 已经确定好是右旋了 Node* subL = parent->_left; Node* subLR = subL->_right; // 存起，防止出现下面 parent 为子树 Node* tmpparent = parent->_parent; parent->_parent = subL; parent->_left = subLR; subL->_right = parent; // subLR 是否空 if (subLR) subLR->_parent = parent; // parent 也可能为根 if (parent == _root) { _root = subL; subL->_parent = nullptr; } // parent 为子树 else { // 再判断 parent 为左子树还是右子树 if (tmpparent->_left == parent) { tmpparent->_left = subL; } else if (tmpparent->_right == parent) { tmpparent->_right = subL; } // 最后链接父亲 subL->_parent = tmpparent; } } // 左旋与右旋类似 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; // 存起，防止出现下面 parent 为子树 Node* tmpparent = parent->_parent; parent->_parent = subR; parent->_right = subRL; subR->_left = parent; // subRL 是否空 if (subRL) subRL->_parent = parent; // parent 也可能为根 if (parent == _root) { _root = subR; subR->_parent = nullptr; } // parent 为子树 else { // 再判断 parent 为左子树还是右子树 if (tmpparent->_left == parent) { tmpparent->_left = subR; } else if (tmpparent->_right == parent) { tmpparent->_right = subR; } // 最后链接父亲 subR->_parent = tmpparent; } } void InOrder() { _InOrder(_root); cout << endl; } 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: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } bool IsBalance() { if (_root == nullptr) return true; if (_root->_col == RED) return false; // 参考值 int num = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) ++num; cur = cur->_left; } return Check(_root, 0, num); } private: bool Check(Node* root, int blacknum, int num) { if (root == nullptr) { // 前序遍历到空，走完 if (num != blacknum) return false; return true; } // 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了 if (root->_col == RED && root->_parent->_col == RED) // 第一个判断条件 root 为红节点排除了 root 为根节点，出现父节点为空指针的情况 { cout << root->_kv.first << "存在连续的红节点" << endl; } if (root->_col == BLACK) ++blacknum; return Check(root->_left, blacknum, num) && Check(root->_right, blacknum, num); } int _Height(Node* root) { if (root == nullptr) return 0; int left = _Height(root->_left); int right = _Height(root->_right); return left > right ? left + 1 : right + 1; } int _Size(Node* root) { return _Size(root->_left) + _Size(root->_right) + 1; } private: Node* _root = nullptr; };

C++ 红黑树原理与实现详解

红黑树的概念

规则

红黑树的效率

红黑树的实现

红黑树的大致框架

更多推荐文章

相关免费在线工具

红黑树插入

插入一个值大概过程

变色/旋转

叔叔节点存在且为红 (变色)

叔叔节点不存在或者为黑 (单旋 + 变色)

双旋

红黑树的查找

红黑树的验证

总结

完整代码

C++ 红黑树原理与实现详解

红黑树的概念

规则

红黑树的效率

红黑树的实现

红黑树的大致框架

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

红黑树插入

插入一个值大概过程

变色/旋转

叔叔节点存在且为红 (变色)

叔叔节点不存在或者为黑 (单旋 + 变色)

双旋

红黑树的查找

红黑树的验证

总结

完整代码