【C++】红黑树

红黑树的介绍

概念

红黑树是一种自平衡的二叉查找树，它通过为每个节点附加颜色属性（红色或黑色），并强制满足一组约束条件，使得树在插入、删除操作后能自动恢复平衡，从而保证最坏情况下的查找、插入、删除时间复杂度均为O(log n)。

接下来我会从各个方面为你介绍红黑树相关信息。

规则

红黑树每个节点要么是红色，要么是黑色，且必须同时满足以下规则：

正是这五条性质（尤其是④和⑤），保证了最长路径不会超过最短路径的两倍，从而防止树退化成链表。

那么它是如何确保最长路径不超过最短路径的两倍呢？

我们这里举个例子：假设有一颗红黑树的每条路径有x个黑色节点，在极端情况下，它的最短路径为（这条路径全为黑色节点）：x，它的最长路径为（路径的节点全为一红一黑组合）：2x。因此在这些规则的规定下，红黑树的最长路径不会超过最短路径的两倍。

红黑树的实现

在介绍完规则之后，我们来简单的实现一下红黑树的结构：

红黑树的结构

红黑树的结构与AVL树的结构相近，只是多了一个枚举类型来记录节点的颜色

#pragma once #include<iostream> using namespace std; enum Color { BLACK, RED }; template<class K, class V> struct RBTreeNode { pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Color _col; RBTreeNode(const pair<K, V>& kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) { } }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: private: Node* _root = nullptr; };

红黑树的插入

红黑树插入的大概过程

红黑树的插入大致分为两个流程：先按二叉搜索树的规则插入，而后对插入的节点进行调整。而我们的重点放在调整部分。

首先我们要明确：对于空树插入，新插入的节点一定是黑色节点（红黑树规则2：根节点一定是黑色）。如果是非空树插入，则新增节点一定是红色节点，如果是黑色节点就会使得这条路径上的黑色节点与其他路径不同，规则5被破坏。

在非空树的节点插入之后，我们还要观察它是否违背了其他规则：父节点是否为黑色。

若父节点为黑色，则未违反任何规则，插入结束。若父节点为红色，违反了规则4：红色节点的两个子节点必须都是黑色（不允许连续两个红色节点相连）。则我们要对其进行分析和讨论。

为了方便称呼，在这里统一一下称呼：新增结点标识为c(cur)，c的父亲标识为p(parent)，p的父亲标识为 g(grandfather)，p的兄弟标识为u（uncle）。

情况1：变色

第一种情况为c、p都为红色，g为黑色，而u存在且为红。则我们需要做的就是把p和u变成黑色，而g的颜色变为红色。

把p和u都变黑、g变红的做法，相当于在左右子树各增加一个黑色节点后，再通过将爷爷变红把g所在子树的黑色节点总数拉回原状，从而在消除c与p连续红色的同时维持黑高不变；处理完成后若g的父亲为黑色则立即终止，若父亲也是红色则需将g视为新的问题节点继续向上调整，而一旦g最终成为根节点就必须重新染回黑色。

情况2：单旋 + 变色

第二种情况为c、p都为红色，g为黑色，而u不存在或者u存在且为黑。

关于u与c的关系：u不存在，则c⼀定是新增结点，u存在且为黑，则 c⼀定不是新增，c之前是黑色的，是在c的子树中插⼊，符合情况1，变色将c从黑色变成红色，更新上来的。

当新插入的红色节点位于父节点的外侧且叔父为黑色时，冲突的根源在于红色的父子相连破坏了规则，而调整的方法是对爷爷节点执行一次朝向父亲方向的单旋转，让父亲取代爷爷的位置成为局部新根，接着将父亲重新染为黑色、爷爷染为红色；这样一来，原本违规的红色父子被拆散，父亲变黑后挡住了向下的红色蔓延，而爷爷变红又刚好抵消了因旋转带来的黑色节点数量变化，整棵子树的黑高维持原样，调整一步到位，无需继续向上追溯。

情况3：双旋 + 变色

第三种情况与第二章情况相似，它们的前提相同：c、p都为红色，g为黑色，而u不存在或者u存在且为黑。

当新插入的红色节点位于父节点的内侧（即父为左子时新节点是右子，或父为右子时新节点是左子）且叔父为黑色时，直接单旋无法一步到位，因为此时新节点处在“拐弯”位置；处理方法是先对父节点执行一次反向单旋，把新节点转到外侧，此时结构退化为情况二的“外侧直线”形态，再对爷爷节点执行一次朝向新节点方向的单旋，最后将新节点染黑、爷爷染红即可。这整个过程包含两次旋转和两次变色，因此称为双旋加变色，目的是在维持黑高不变的前提下，将原本嵌在中间的红节点提为子树的黑色新根，从而彻底消除连续红色冲突。

完整代码

bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return true; } Node* cur = _root; Node* parent = nullptr; 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->_right) { 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); grandfather->_col = RED; parent->_col = BLACK; } else { RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } } } else { 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); grandfather->_col = RED; parent->_col = BLACK; } else { RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } } } } _root->_col = BLACK; return true; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* pParent = parent->_parent; subL->_right = parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (pParent->_left == parent) { pParent->_left = subL; } else { pParent->_right = subL; } subL->_parent = pParent; } } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* pParent = parent->_parent; subR->_left = parent; parent->_parent = subR; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (pParent->_left == parent) { pParent->_left = subR; } else { pParent->_right = subR; } subR->_parent = pParent; } }

红黑树的查找

按二叉搜索树逻辑实现即可，搜索效率为 O(logN)

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;

红黑树的验证

红黑树的验证，本质就是对照五条核心性质逐项检查，确认这棵树既是合法的二叉搜索树，又严格符合颜色与黑高约束。具体验证逻辑如下：

1. 二叉搜索树性质
   先通过中序遍历确认节点值严格有序，确保树本身是合法的 BST。

2. 根节点为黑
   直接检查根节点颜色，若为红则不合法。

3. 无连续红色节点
   遍历每个红色节点，检查其父节点和子节点是否均为黑色（NIL 视为黑）。

4. 黑高一致性
   从根节点出发，递归计算每条到 NIL 叶子路径上的黑色节点数，保证所有路径结果相等。

实际操作中，写一个递归函数，返回以当前节点为根的子树是否合法及其黑高，自底向上校验，能高效完成验证。

bool IsBalance() { if (_root == nullptr) { return true; } if (_root->_col == RED) return false; Node* cur = _root; int refNum = 0; while (cur) { if (cur->_col == BLACK) { refNum++; } cur = cur->_left; } return Check(_root, 0, refNum); } bool Check(Node* root, int blackNum, int refNum) { if (root == nullptr) { if (blackNum != refNum) { cout << "有路径的黑色节点数错误" << endl; return false; } return true; } if (root->_col == RED && root->_parent->_col == RED) { cout << "存在两个相连的红色节点" << endl; } if (root->_col == BLACK) { blackNum++; } return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum); }

与AVL树的比较

红黑树模拟实现STL中的set和map

在实现完红黑树的基本结构之后，我们要尝试用红黑树来封装set和map

改造红黑树

在标准库的实现中，map和set底层通常共用同一套红黑树代码。为了适配这种复用，红黑树节点中存储的数据类型不再写死为K或pair<const K, V>，而是定义为一个泛型参数T。

这样一来就产生了一个问题：当红黑树内部需要比较两个节点的大小（比如执行插入、查找时），它面对的只是泛型T，并不知道应该比较什么字段。对于set，T就是K本身，直接比较K即可；但对于map，T是pair<K, V>，而比较规则要求只看键K，忽略值V。pair默认的比较运算符会先比较K，相等时还会比较V，这既不符合语义，也会引入不必要的开销。

解决这个矛盾的办法是将“如何从T中取出键”这一行为抽象成一个仿函数，由上层调用方提供。具体做法如下：

• 在RBTree模板参数中增加一个KeyOfT类型，它必须是一个可调用对象，负责从T类型的实例中提取出用于比较的键K。

• 在map的实现层，定义一个仿函数MapKeyOfT，其operator()接收pair<const K, V>，返回pair.first。

• 在set的实现层，定义一个仿函数SetKeyOfT，其operator()接收K，直接返回K自身。

• 实例化红黑树时，map将MapKeyOfT传入，set将SetKeyOfT传入。

之后，红黑树中任何需要比较两个节点的地方，都先调用KeyOfT取出各自的键，再对键进行大小比较。这样就将数据存储结构与比较规则解耦，用一套红黑树代码干净地支撑了两种不同的容器。

红黑树的迭代器

因为map和set支持迭代器，同样的，我们需要在原本的结构上再加上迭代器。

红黑树的迭代器在整体设计框架上与链表的迭代器思路一致，都是封装一个指向树节点的指针，并通过重载*、->、++、--等运算符，使其具备类似原生指针的访问行为。这里的核心难点在于operator++和operator--的实现，因为它们需要严格遵循二叉搜索树的中序遍历顺序——左子树、根节点、右子树。

具体来说，当迭代器指向某个节点it时，++it的逻辑分为两种情况：

++时若当前节点有右子树，则下一节点为右子树的最左节点；若无右子树，则沿父指针向上回溯，直到找到某个作为父节点左孩子的祖先，该祖先即为下一节点，若一直未找到则迭代器置为nullptr表示end()。

operator--的整体逻辑与++完全对称，只是遍历顺序变为右子树、根节点、左子树。

还有一点需要注意为满足map可改值、set不可改键的要求，底层红黑树模板参数对set用const K，对map用pair<const K, V>。

改造后的红黑树代码

#pragma once #include<iostream> using namespace std; enum Color { BLACK, RED }; template<class T> struct RBTreeNode { T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Color _col; RBTreeNode(const T& data) :_data(data) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) { } }; template<class T, class Ref, class Ptr> struct RBTreeIterator { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, Ref, Ptr> Self; Node* _node; Node* _root; RBTreeIterator(Node* node, Node* root) :_node(node) ,_root(root) { } Self& operator++() { if (_node->_right) { _node = _node->_right; while (_node->_left) { _node = _node->_left; } } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } Self& operator--() { if (_node == nullptr) { Node* cur = _root; while (cur && cur->_right) { cur = cur->_right; } _node = cur; } else if (_node->_left) { Node* cur = _node->_left; while (cur->_right) { cur = cur->_right; } _node = cur; } else { Node* parent = _node->_parent; Node* cur = _node; while (parent && cur == parent->_left) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } }; template<class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: typedef RBTreeIterator<T, T&, T*> Iterator; typedef RBTreeIterator<T, const T&, const T*> ConstIterator; Iterator Begin() { Node* cur = _root; while (cur && cur->_left) { cur = cur->_left; } return Iterator( cur, _root ); } Iterator End() { return Iterator(nullptr, _root); } ConstIterator Begin() const { Node* cur = _root; while (cur && cur->_left) { cur = cur->_left; } return Iterator(cur, _root); } ConstIterator End() const { return Iterator(nullptr, _root); } pair<Iterator, bool> Insert(const T& data) { if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return { Iterator(_root, _root), true }; } KeyOfT kot; Node* cur = _root; Node* parent = nullptr; 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 { Iterator(cur, _root), false }; } } cur = new Node(data); cur->_col = RED; if (kot(parent->_data) < kot(data)) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; Node* newnode = cur; while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; if (parent == grandfather->_right) { 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); grandfather->_col = RED; parent->_col = BLACK; } else { RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } } } else { 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); grandfather->_col = RED; parent->_col = BLACK; } else { RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } } } } _root->_col = BLACK; return { Iterator(newnode, _root), true }; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; Node* pParent = parent->_parent; subL->_right = parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (pParent->_left == parent) { pParent->_left = subL; } else { pParent->_right = subL; } subL->_parent = pParent; } } void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; Node* pParent = parent->_parent; subR->_left = parent; parent->_parent = subR; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (pParent->_left == parent) { pParent->_left = subR; } else { pParent->_right = subR; } subR->_parent = pParent; } } 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; } bool IsBalance() { if (_root == nullptr) { return true; } if (_root->_col == RED) return false; Node* cur = _root; int refNum = 0; while (cur) { if (cur->_col == BLACK) { refNum++; } cur = cur->_left; } return Check(_root, 0, refNum); } void InOrder() { return _InOrder(_root); } int Height() { return _Height(_root); } int Size() { return _Size(_root); } private: bool Check(Node* root, int blackNum, int refNum) { if (root == nullptr) { if (blackNum != refNum) { cout << "有路径的黑色节点数错误" << endl; return false; } return true; } if (root->_col == RED && root->_parent->_col == RED) { cout << "存在两个相连的红色节点" << endl; } if (root->_col == BLACK) { blackNum++; } return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum); } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_data.first << ":" << root->_data.second << endl; _InOrder(root->_right); } 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 _Size(Node* root) { if (root == nullptr) { return 0; } return _Size(root->_left) + _Size(root->_right) + 1; } Node* _root = nullptr; };

set的模拟实现

#pragma once #include"RBTree4.13.h" namespace Rane { template<class K> class set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator; typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator; iterator begin() { return _t.Begin(); } iterator end() { return _t.End(); } const_iterator begin() const { return _t.Begin(); } const_iterator end() const { return _t.End(); } pair<iterator, bool> insert(const K& key) { return _t.Insert(key); } private: RBTree<K, const K, SetKeyOfT> _t; }; }

map的模拟实现

#pragma once #include"RBTree4.13.h" namespace Rane { template<class K, class V> class map { struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator; typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator; iterator begin() { return _t.Begin(); } iterator end() { return _t.End(); } const_iterator begin() const { return _t.Begin(); } const_iterator end() const { return _t.End(); } pair<iterator, bool> insert(const pair<K, V>& kv) { return _t.Insert(kv); } V& operator[](const K& key) { pair<iterator, bool> ret = insert({ key, V() }); return ret.first->second; } private: RBTree<K, pair<const K, V>, MapKeyOfT> _t; }; }