红黑树数据结构与实现

红黑树的概念、五大性质及节点定义，详细讲解了插入操作中的旋转与变色逻辑，提供了验证平衡性的方法以及完整的 C++ 代码实现与性能测试，展示了红黑树在大数据量下的插入与查找效率。

王者发布于 2026/3/30更新于 2026/4/131 浏览

红黑树数据结构与实现

1. 红黑树的概念

红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

红黑树示意图

2. 红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的（此处的叶子结点指的是空结点，是红黑树特有的 NIL 节点）

其中，第 5 条性质是为了帮助理解性质 4。例如：下面这棵树符合红黑树的定义吗？

示例树

直观上看似乎符合，但加上 NIL 节点后：

带 NIL 节点的树

可以看到，用蓝色线条画出的这条路径容易被忽略。从根节点向下看，其他路径上的黑色节点数都是 2 个（不算 NIL 节点），唯独蓝色线路上的黑色节点只有 1 个，所以上面这棵树是不符合红黑树定义的，它不是红黑树！

满足了如上 5 条性质，就可以保证最长路径不超过最短路径的两倍。这是基于数学推导的设计，只要能使用并控制红黑树的结构即可。

3. 红黑树节点的定义

下面我们先实现一颗 kv 结构的红黑树。

// 颜色定义
enum Colour {
    RED,
    BLACK
};

// 红黑树节点
template<class K, class V>
struct RBTreeNode {
    RBTreeNode<K, V>* _left;      
    RBTreeNode<K, V>* _right;     
    RBTreeNode<K, V>* _parent;    
    pair<K, V> _kv;               
    Colour _col;                  

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

相关免费在线工具

加密/解密文本

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

template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; private: Node* _root = nullptr; 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 (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else { return false; // 已存在 } } // 设定新增节点为红色 cur = new Node(kv); cur->_col = RED; if (kv.first > parent->_kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } // 如果父节点存在并且是红色，再处理 while (parent && parent->_col == RED) { Node* grandFather = parent->_parent; if (parent == grandFather->_left) { Node* uncle = grandFather->_right; // 叔叔存在且为红色 if (uncle && uncle->_col == RED) { uncle->_col = parent->_col = BLACK; grandFather->_col = RED; cur = grandFather; parent = cur->_parent; } else { if (cur == parent->_left) { // 左左黑：右单旋 RotateR(grandFather); parent->_col = BLACK; grandFather->_col = RED; } else { // 左右黑：左右双旋 RotateL(parent); RotateR(grandFather); grandFather->_col = RED; cur->_col = BLACK; } break; } } else { Node* uncle = grandFather->_left; // 叔叔存在且为红色 if (uncle && uncle->_col == RED) { uncle->_col = parent->_col = BLACK; grandFather->_col = RED; cur = grandFather; parent = cur->_parent; } else { if (cur == parent->_right) { // 右右黑：左单旋 RotateL(grandFather); parent->_col = BLACK; grandFather->_col = RED; } else { // 右左黑：右左双旋 RotateR(parent); RotateL(grandFather); grandFather->_col = RED; cur->_col = BLACK; } break; } } } _root->_col = BLACK; return true; } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; subR->_left = parent; Node* parentParent = parent->_parent; parent->_parent = subR; if (subRL != nullptr) subRL->_parent = parent; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else if (parentParent->_left == parent) { parentParent->_left = subR; subR->_parent = parentParent; } else { parentParent->_right = subR; subR->_parent = parentParent; } } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; subL->_right = parent; Node* parentParent = parent->_parent; parent->_parent = subL; if (subLR != nullptr) subLR->_parent = parent; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else if (parentParent->_left == parent) { parentParent->_left = subL; subL->_parent = parentParent; } else { parentParent->_right = subL; subL->_parent = parentParent; } } };

#pragma once #include <iostream> #include <vector> #include <chrono> #include <ctime> #include <cstdlib> #include <utility> using namespace std; enum Colour { RED, BLACK }; template<class K, class V> struct RBTreeNode { RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; pair<K, V> _kv; Colour _col; RBTreeNode(const pair<K, V>& kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED) {} }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; private: Node* _root = nullptr; 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 (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); cur->_col = RED; if (kv.first > parent->_kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } while (parent && parent->_col == RED) { Node* grandFather = parent->_parent; if (parent == grandFather->_left) { Node* uncle = grandFather->_right; if (uncle && uncle->_col == RED) { uncle->_col = parent->_col = BLACK; grandFather->_col = RED; cur = grandFather; parent = cur->_parent; } else { if (cur == parent->_left) { RotateR(grandFather); parent->_col = BLACK; grandFather->_col = RED; } else { RotateL(parent); RotateR(grandFather); grandFather->_col = RED; cur->_col = BLACK; } break; } } else { Node* uncle = grandFather->_left; if (uncle && uncle->_col == RED) { uncle->_col = parent->_col = BLACK; grandFather->_col = RED; cur = grandFather; parent = cur->_parent; } else { if (cur == parent->_right) { RotateL(grandFather); parent->_col = BLACK; grandFather->_col = RED; } else { RotateR(parent); RotateL(grandFather); grandFather->_col = RED; cur->_col = BLACK; } break; } } } _root->_col = BLACK; return true; } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; subR->_left = parent; Node* parentParent = parent->_parent; parent->_parent = subR; if (subRL != nullptr) subRL->_parent = parent; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else if (parentParent->_left == parent) { parentParent->_left = subR; subR->_parent = parentParent; } else { parentParent->_right = subR; subR->_parent = parentParent; } } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; subL->_right = parent; Node* parentParent = parent->_parent; parent->_parent = subL; if (subLR != nullptr) subLR->_parent = parent; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else if (parentParent->_left == parent) { parentParent->_left = subL; subL->_parent = parentParent; } else { parentParent->_right = subL; subL->_parent = parentParent; } } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } void InOrder() { _InOrder(_root); cout << endl; } bool Check(Node* root, int blacknum, const int refVal) { if (root == nullptr) { if (blacknum != refVal) { cout << "存在黑色节点数量不相等的路径" << endl; return false; } return true; } if (root->_col == RED && root->_parent->_col == RED) { cout << "有连续的红色节点" << endl; return false; } if (root->_col == BLACK) blacknum++; return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal); } bool IsBalance() { return _IsBalance(_root); } bool _IsBalance(Node* root) { if (root == nullptr) return true; if (root->_col == RED) return false; int refVal = 0; Node* cur = root; while (cur) { if (cur->_col == BLACK) refVal++; cur = cur->_left; } int blacknum = 0; return Check(root, blacknum, refVal); } bool 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 true; } } return false; } 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; } int Height() { return _Height(_root); } int _Size(Node* root) { if (root == nullptr) return 0; return _Size(root->_left) + _Size(root->_right) + 1; } int Size() { return _Size(_root); } };

红黑树数据结构与实现

红黑树数据结构与实现

1. 红黑树的概念

2. 红黑树的性质

3. 红黑树节点的定义

更多推荐文章

相关免费在线工具

4. 红黑树的插入

1. 思考：新插入节点的颜色

2. 分情况讨论

3. 代码实现

5. 红黑树的验证

6. 红黑树的删除

7. 红黑树完整代码 + 测试

1. 完整代码

2. 测试效率

红黑树数据结构与实现

红黑树数据结构与实现

1. 红黑树的概念

2. 红黑树的性质

3. 红黑树节点的定义

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

更多推荐文章

相关免费在线工具

4. 红黑树的插入

1. 思考：新插入节点的颜色

2. 分情况讨论

3. 代码实现

5. 红黑树的验证

6. 红黑树的删除

7. 红黑树完整代码 + 测试

1. 完整代码

2. 测试效率