当前位置：首页 > news >正文

c++红黑树

news 2026/5/11 21:47:42

一、为什么需要红黑树？

在编程中，我们经常需要一个动态维护有序数据的结构。比如：

std::map和std::set的底层实现
Linux内核的进程调度器
数据库的索引结构

如果使用普通的二叉搜索树（BST），极端情况下会退化成链表（如插入有序数据），导致查找效率从O(log n)降为O(n)。为了解决这个问题，红黑树（Red-Black Tree）应运而生。

二、红黑树的核心思想

红黑树是一种自平衡的二叉搜索树，它通过以下规则实现近似平衡：

红黑树的5大规则

每个节点非红即黑
根节点必须是黑色
红色节点的子节点必须是黑色（不能出现连续的红色）
从任意节点到其空子节点的路径上，黑色节点的数量必须相同
每个叶子节点（空节点）是黑色

为什么这些规则能保证效率？

最长路径 ≤ 2 × 最短路径
例如，如果最短路径有k个节点，最长路径最多有2k个节点。这确保了红黑树的高度始终在O(log n)范围内。

三、红黑树的插入操作详解

插入新节点时，红黑树需要通过变色 + 旋转维持平衡。以下是典型场景：

情况1：父节点是黑色

直接插入即可，无需调整。

情况2：父节点是红色

此时需要根据叔叔节点的颜色进行处理：

子情况1：叔叔是红色

操作：父节点、叔节点变黑，祖父节点变红，并继续向上处理。

祖父(黑) → 父(红) → 当前(红) 叔(红)

子情况2：叔叔是黑色或不存在

需要通过旋转调整：

LL型（当前节点在左子树的左子树）：右单旋 + 变色
RR型（当前节点在右子树的右子树）：左单旋 + 变色
LR型（当前节点在左子树的右子树）：左右双旋 + 变色
RL型（当前节点在右子树的左子树）：右左双旋 + 变色

四、红黑树的代码实现

enum Color { RED, BLACK }; template <typename K, typename V> struct RBTreeNode { RBTreeNode* left; RBTreeNode* right; RBTreeNode* parent; std::pair<K, V> kv; Color color; RBTreeNode(const K& key, const V& value) : left(nullptr), right(nullptr), parent(nullptr), kv(key, value), color(RED) {} }; template <typename K, typename V> class RBTree { public: void insert(const K& key, const V& value) { // 二叉搜索树插入逻辑 // ... // 插入后调整平衡 fixInsert(newNode); } private: void fixInsert(RBTreeNode<K, V>* node) { while (node->parent && node->parent->color == RED) { // 处理四种情况 // ... } root->color = BLACK; } RBTreeNode<K, V>* root; };