数据结构：红黑树原理与实现

本文介绍红黑树的定义、五条规则（实际四条核心约束）、时间复杂度及插入实现。包含变色、单旋、双旋三种调整情况，并提供了完整的 C++ 代码示例，涵盖节点结构、插入逻辑、旋转操作及查找功能。

山野诗人发布于 2026/3/29更新于 2026/4/131 浏览

红黑树

1. 红黑树

1.1 红黑树的定义

红黑树是一棵二叉搜索树，它的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，最长的不超过最短的 2 倍（近似平衡）。

1.2 红黑树的规则

每个结点不是红色就是黑色
根结点是黑色的
如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点。
对于任意一个结点，从该结点到其所有 NULL 结点的简单路径上，均包含相同数量的黑色结点。 最长路径（一黑一红） <= 2*最短路径（全黑）（四条规则约束）数路径要数到空结点。（NIL 结点数路径）

1.3 红黑树的效率：

最短路径 logN，最长路径 2*logN，时间复杂度就是 O(logN)。

2. 红黑树的实现

2.1 红黑树的插入

(插入红色结点，按照二叉搜索树的规则，和四条红黑树的规则）

2.1.1 情况 1:变色

c 为红，p 为红，g 为黑，u 存在且为红，则将 p 和 u 变黑，g 变红。在把 g 当做新的 c，继续往上更新。情况 1 只变色，不旋转。所以无论 c 是 p 的左还是右，p 是 g 的左还是右，都是上面的变色处理方式。

2.1.2 情况 2：单旋 + 变色

c 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑，u 不存在，则 c 一定是新增结点，u 存在且为黑，则 c 一定不是新增，c 之前是黑色的，是在 c 的子树中插入，符合情况 1，变色将 c 从黑色变成红色，更新上来的。

2.1.3 情况 3：双旋 + 变色

c 为红，p 为红，g 为黑，u 不存在或者 u 存在且为黑，u 不存在，则 c 一定是新增结点，u 存在且为黑，则 c 一定不是新增，c 之前是黑色的，是在 c 的子树中插入，符合情况 1，变色将 c 从黑色变成红色，更新上来的。

2.2 红黑树的插入代码实现

// test.cpp
#include <iostream>
#include <vector>
using namespace std;
#include "RBTree.h"
// void TestRBTree1()
// {
//     RBTree<int, int> t;
//     // 常规的测试用例
//     // int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//     // 特殊的带有双旋场景的测试用例
//     int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3, 5, 66, 33, 543, 54, 2, 435, 321, 32, 43, 4324, 534 };
//     for (auto e : a)
//     {











































{
    
    bit::();
    bit::();
     ;
}

相关免费在线工具

加密/解密文本

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

// RBTree.h enum Colour { RED, BLACK }; template<class T> struct RBTreeNode { T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col; RBTreeNode(const T& data) : _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {} }; template<class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: bool Insert(const T& data) { if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return true; } KeyOfT kot; Node* parent = nullptr; Node* cur = _root; while (cur) { if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else if (kot(cur->_data) > kot(data)) { parent = cur; cur = cur->_left; } else { return false; } } // 新插入红色节点 cur = new Node(data); cur->_col = RED; if (kot(parent->_data) < kot(data)) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; if (parent == grandfather->_left) { Node* uncle = grandfather->_right; // 1、u 存在且为红 if (uncle && uncle->_col == RED) { // 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 继续往上处理 cur = grandfather; parent = cur->_parent; } else // 2、u 不存在或者 u 存在且为黑 { if (cur == parent->_left) { // g // p u // c RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // p u // c RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else // (parent == grandfather->_right) { Node* uncle = grandfather->_left; // 1、u 存在且为红 if (uncle && uncle->_col == RED) { // 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 继续往上处理 cur = grandfather; parent = cur->_parent; } else // 2、u 不存在或者 u 存在且为黑 { if (cur == parent->_right) { // g // u p // c RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { // g // u p // c RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; } void InOrder() { _InOrder(_root); cout << endl; } int Height() { return _Height(_root); } int Size() { return _Size(_root); } Node* Find(const K& key) { KeyOfT kot; Node* cur = _root; while (cur) { if (kot(cur->_data) < key) { cur = cur->_right; } else if (kot(cur->_data) > key) { cur = cur->_left; } else { return cur; } } return nullptr; } private: int _Size(Node* root) { return root == nullptr ? 0 : _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; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } 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 (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* ppnode = parent->_parent; subR->_left = parent; parent->_parent = subR; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } } private: Node* _root = nullptr; };

数据结构：红黑树原理与实现

红黑树

1. 红黑树

1.1 红黑树的定义

1.2 红黑树的规则

1.3 红黑树的效率：

2. 红黑树的实现

2.1 红黑树的插入

2.1.1 情况 1:变色

2.1.2 情况 2：单旋 + 变色

2.1.3 情况 3：双旋 + 变色

2.2 红黑树的插入代码实现

更多推荐文章

相关免费在线工具

2.3 红黑树的查找

2.4 红黑树的检查

数据结构：红黑树原理与实现

红黑树

1. 红黑树

1.1 红黑树的定义

1.2 红黑树的规则

1.3 红黑树的效率：

2. 红黑树的实现

2.1 红黑树的插入

2.1.1 情况 1:变色

2.1.2 情况 2：单旋 + 变色

2.1.3 情况 3：双旋 + 变色

2.2 红黑树的插入代码实现

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

更多推荐文章

相关免费在线工具

2.3 红黑树的查找

2.4 红黑树的检查