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

C++红黑树的深入解析：从理论到实践

news 2026/5/1 20:27:59

一、红黑树的基本概念与规则

红黑树是一种满足特定性质的二叉搜索树。与普通的二叉搜索树不同，红黑树的每个结点都附加了一个颜色属性，且通过一些规则保证了树的平衡性。红黑树的四条基本规则如下：

每个节点的颜色要么是红色，要么是黑色。
根节点是黑色的。
如果一个节点是红色的，那么它的两个子节点必须是黑色的。这就意味着红色节点不能有连续的红色节点。
从任意一个节点到其所有叶子节点的路径上，必须包含相同数量的黑色节点。这条规则保证了树的平衡性，防止树的某些路径过长。

红黑树的这些规则通过“颜色约束”来间接实现自平衡，因此每次进行插入、删除操作时，都需要确保这些规则被满足。

以上均为红黑树示例。

二、红黑树的高度与效率

红黑树的高度是它的关键特性之一。红黑树的自平衡机制确保了它的高度不会太大，这对于树的查找、插入和删除操作的效率至关重要。理论上，红黑树的高度 h 与黑色高度 bh（从根到叶子节点的路径上黑色节点的数量）之间存在如下关系：

最短路径（只有黑色节点）长度为 bh。
最长路径（交替的红色和黑色节点）长度为 2 * bh。

因此，红黑树的最大高度为 2 * bh，而最小高度为 bh。因此，红黑树的高度 h 满足 h≤2×bhh \leq 2 \times bhh≤2×bh，并且由于红黑树的黑色高度是相同的，所以可以得出红黑树的高度是 O(log N)，其中 N 是树中结点的数量。

由于红黑树的高度被控制在对数级别，它能够保证查找、插入、删除操作在最坏情况下的时间复杂度均为 O(log N)。

三、红黑树的结构

红黑树的基本节点结构包括以下几个部分：

代码语言：javascript

AI代码解释

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) {} };

每个节点不仅包含键值对 (_kv)，还包含指向左子树、右子树和父节点的指针。此外，节点的颜色 (_col) 用于维护红黑树的平衡。

四、红黑树的插入操作

红黑树的插入操作需要遵循以下步骤：

按照二叉搜索树的规则插入新节点。这是插入操作的第一步，我们首先将新节点插入到树的适当位置。
将新节点的颜色设置为红色。新插入的节点默认是红色的，这有助于避免违反红黑树的黑色节点数平衡。
调整颜色和结构。插入新节点后，可能会破坏红黑树的平衡。具体的修复操作包括：
- 情况1：变色操作。如果父节点和叔叔节点都是红色，则将父节点和叔叔节点都变为黑色，祖父节点变为红色，并继续往上处理。
- 情况2：旋转和变色。如果父节点是红色，且叔叔节点是黑色或不存在，则需要进行旋转操作（单旋或双旋），并相应地调整颜色。

我们来看一段插入代码的实现：

代码语言：javascript

AI代码解释

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->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } 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 (parent == grandfather->_left) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { parent->_col = uncle->_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); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = uncle->_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); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; }

这段代码展示了红黑树的插入操作，包括节点插入、颜色变更和旋转操作。关键的操作是通过循环和条件判断来确保红黑树的规则不被破坏。

五、红黑树的查找操作

红黑树的查找操作和普通的二叉搜索树是类似的，我们依然按照二叉搜索树的规则进行查找。由于红黑树的平衡性，查找操作的时间复杂度为 O(log N)。

代码语言：javascript

AI代码解释

Node* 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 cur; } } return nullptr; }

上述代码展示了查找操作的实现，我们根据节点的键值逐步向左或向右子树移动，直到找到目标节点或树为空。