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

C++红黑树是一种自平衡二叉搜索树，通过颜色约束保证最长路径不超过最短路径的两倍。文章详细介绍了红黑树的五条性质、插入操作的三种调整情况（变色、单旋、双旋）以及验证方法，并提供了完整的 C++ 模板代码实现。删除操作因逻辑复杂，本文补充了其核心处理流程概述。

数字游民发布于 2026/2/60 浏览

前言

红黑树是 C++ STL 中 map 和 set 的基础数据结构之一，也是平衡二叉搜索树的典型代表。本文将深入探讨其设计原理、核心规则及 C++ 实现细节。

1.红黑树的概念

1.1.红黑树是什么

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

1.2.红黑树的规则

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

以上便是红黑树的五条规则。下面展示几张红黑树的示意图：

文章配图

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

由规则 4 可知，每条路径上有着数量相同的黑色节点。在极端场景下，一条路上全都是黑色节点，最短路径长度记作 bh。

结合规则 2 和规则 3，一条路上不会出现连续的红色节点，所以最长路径应该是一红一黑交织组成，长度为 2bh。

根据红黑树的规则，一般情况下的红黑树路径是由数量不等的红黑节点组成的。假设红黑树一条路径的长度为 h，所以 bh <= h <= 2bh，即红黑树的最长路径不会是最短路径的两倍。

1.4.红黑树的效率问题

假设红黑树的节点个数为 N，最短路径的长度为 h，所以可知：2^h - 1 <= N < 2^(2*h) - 1，由此可以推出 h 大约等于 logN。红黑树查找的效率最差也是 O(log N)，时间复杂度终归还是 O(log(N))。

红黑树的表达相对 AVL 树要更抽象一些，AVL 树可以根据高度更加直观地看出树的平衡，而红黑树则是需要根据四条规则的颜色进行约束，间接地实现了近似平衡。他们的效率都是同一档次的，但是相对而言，插入相同数量的节点，红黑树的旋转次数变得更少了，因为它对平衡的把控并不是那么严格。

2.红黑树的实现

2.1.红黑树的结构

红黑树是一个典型的三叉链，节点需要包含父节点以及左右孩子节点。由于红黑树是通过颜色进行平衡的，我们需要设置好一个枚举来确定节点的颜色，默认颜色为红色。红黑树通过 Key 和 Value 存放数据，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;

    ( pair<K, V>& kv) :_kv(kv), _left(), _right(), _parent(), _col(RED) {}
};

< ,  >
  {
     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; // 根节点一定是黑色的 } 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> 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 nullptr; } void InOrder() { _InOrder(_root); } bool Check(Node* root, int blackNum, const int refNum) { if (root == nullptr) { if (refNum != blackNum) return false; return true; } if (root->_col == RED && root->_parent->_col == RED) 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 << endl; }

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

前言

1.红黑树的概念

1.1.红黑树是什么

1.2.红黑树的规则

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

1.4.红黑树的效率问题

2.红黑树的实现

2.1.红黑树的结构

更多推荐文章

相关免费在线工具

2.2.红黑树的查找

3.红黑树的插入

3.1.红黑树插入一个值的大致过程

4.红黑树的验证

4.1.如何验证

4.2.相关代码

5.红黑树的删除

6.完整代码

7.小结

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

前言

1.红黑树的概念

1.1.红黑树是什么

1.2.红黑树的规则

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

1.4.红黑树的效率问题

2.红黑树的实现

2.1.红黑树的结构

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

更多推荐文章

相关免费在线工具

2.2.红黑树的查找

3.红黑树的插入

3.1.红黑树插入一个值的大致过程

4.红黑树的验证

4.1.如何验证

4.2.相关代码

5.红黑树的删除

6.完整代码

7.小结