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

介绍 C++ 红黑树的概念、五条基本规则及平衡性证明。详细阐述节点结构、查找操作及插入过程中的三种调整情况（变色、单旋、双旋）。提供完整类实现代码，包含旋转、插入、查找及平衡验证逻辑，分析时间复杂度为 O(log N)。

二进制发布于 2026/3/30更新于 2026/4/131 浏览

红黑树概述

红黑树是一种自平衡二叉搜索树，广泛应用于 C++ STL 的 map 和 set 容器。它通过颜色约束确保树的高度近似平衡，从而保证查找、插入和删除操作的时间复杂度为 O(log N)。

红黑树概念

1.1. 红黑树是什么

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

1.2. 红黑树的规则

每个节点不是黑色的就是红色的。
根节点必须是黑色的。
如果一个节点是红色的，则它的两个孩子节点必须是黑色的，即任意一条路径上不会出现连续的红色节点。
对于任意的一个节点，从该节点到其所有 NULL 节点的简单路径上，均包含着相同数目的黑色节点。
每个叶子节点（NULL）都是黑色的。

1.3. 红黑树如何确保最长路径不超过最短路径的两倍

由规则 4 可知，每条路径上有数量相同的黑色节点。在极端场景下，最短路径是全黑节点，记作 bh。根据规则 2 和 3，最长路径是一红一黑交织组成，长度为 2bh。因此，红黑树的最长路径不会是最短路径的两倍。

1.4. 红黑树的效率问题

假设红黑树的节点个数为 N，最短路径的长度为 h，可知：2^h - 1 <= N < 2^(2h) - 1，由此推出 h 大约等于 logN。红黑树的查找效率最差也是 2 * logN，时间复杂度为 O(log N)。相比 AVL 树，红黑树对平衡的把控不那么严格，插入相同数量的节点时旋转次数更少。

红黑树的实现

2.1. 红黑树的结构

红黑树节点需要包含父节点指针、左右孩子指针以及颜色属性。默认颜色为红色，通过 Key 和 Value 存放数据。

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:
    Node* _root = nullptr;
};

2.2. 红黑树的查找

相关免费在线工具

加密/解密文本

使用加密算法（如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->_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; }

#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; return true; } 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 nullptr; } 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; }; void TestRBTree1() { RBTree<int, int> t; int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : a) t.Insert({ e, e }); t.InOrder(); cout << t.IsBalance() << endl; } void TestRBTree2() { const int N = 1000000; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; i++) v.push_back(rand() + i); size_t begin2 = clock(); RBTree<int, int> t; for (auto e : v) t.Insert(make_pair(e, e)); size_t end2 = clock(); cout << t.IsBalance() << endl; cout << "RBTree Insert:" << end2 - begin2 << endl; cout << "RBTree Height:" << t.Height() << endl; cout << "RBTree Size:" << t.Size() << endl; size_t begin1 = clock(); for (size_t i = 0; i < N; i++) t.Find((rand() + i)); size_t end1 = clock(); cout << "RBTree Find:" << end1 - begin1 << endl; } }

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

红黑树概述

红黑树概念

1.1. 红黑树是什么

1.2. 红黑树的规则

1.3. 红黑树如何确保最长路径不超过最短路径的两倍

1.4. 红黑树的效率问题

红黑树的实现

2.1. 红黑树的结构

2.2. 红黑树的查找

更多推荐文章

相关免费在线工具

红黑树的插入

3.1. 插入大致过程

情况一：变色

情况二：单旋 + 变色

情况三：双旋 + 变色

红黑树的验证

红黑树的删除

完整代码

小结

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

红黑树概述

红黑树概念

1.1. 红黑树是什么

1.2. 红黑树的规则

1.3. 红黑树如何确保最长路径不超过最短路径的两倍

1.4. 红黑树的效率问题

红黑树的实现

2.1. 红黑树的结构

2.2. 红黑树的查找

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

更多推荐文章

相关免费在线工具

红黑树的插入

3.1. 插入大致过程

情况一：变色

情况二：单旋 + 变色

情况三：双旋 + 变色

红黑树的验证

红黑树的删除

完整代码

小结