【C++】红黑树

红黑树的介绍概念红黑树是一种自平衡的二叉查找树它通过为每个节点附加颜色属性红色或黑色并强制满足一组约束条件使得树在插入、删除操作后能自动恢复平衡从而保证最坏情况下的查找、插入、删除时间复杂度均为O(log n)。接下来我会从各个方面为你介绍红黑树相关信息。规则红黑树每个节点要么是红色要么是黑色且必须同时满足以下规则规则说明① 节点颜色每个节点非红即黑。② 根节点根节点必须是黑色。③ 叶子节点NIL所有叶子节点空节点通常用NIL表示都被视为黑色。④ 红色节点的子节点红色节点的两个子节点必须都是黑色不允许连续两个红色节点相连。⑤ 任意节点到叶子的黑色节点的数目从任一节点出发到达其所有后代叶子节点的路径上经过的黑色节点数目必须相同。正是这五条性质尤其是④和⑤保证了最长路径不会超过最短路径的两倍从而防止树退化成链表。那么它是如何确保最长路径不超过最短路径的两倍呢我们这里举个例子假设有一颗红黑树的每条路径有x个黑色节点在极端情况下它的最短路径为这条路径全为黑色节点x它的最长路径为路径的节点全为一红一黑组合2x。因此在这些规则的规定下红黑树的最长路径不会超过最短路径的两倍。红黑树的实现在介绍完规则之后我们来简单的实现一下红黑树的结构红黑树的结构红黑树的结构与AVL树的结构相近只是多了一个枚举类型来记录节点的颜色#pragma once #includeiostream using namespace std; enum Color { BLACK, RED }; templateclass K, class V struct RBTreeNode { pairK, V _kv; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNodeK, V* _parent; Color _col; RBTreeNode(const pairK, V kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) { } }; templateclass K, class V class RBTree { typedef RBTreeNodeK, V Node; public: private: Node* _root nullptr; };红黑树的插入红黑树插入的大概过程红黑树的插入大致分为两个流程先按二叉搜索树的规则插入而后对插入的节点进行调整。而我们的重点放在调整部分。首先我们要明确对于空树插入新插入的节点一定是黑色节点红黑树规则2根节点一定是黑色。如果是非空树插入则新增节点一定是红色节点如果是黑色节点就会使得这条路径上的黑色节点与其他路径不同规则5被破坏。在非空树的节点插入之后我们还要观察它是否违背了其他规则父节点是否为黑色。若父节点为黑色则未违反任何规则插入结束。若父节点为红色违反了规则4红色节点的两个子节点必须都是黑色不允许连续两个红色节点相连。则我们要对其进行分析和讨论。为了方便称呼在这里统一一下称呼新增结点标识为c(cur)c的父亲标识为p(parent)p的父亲标识为 g(grandfather)p的兄弟标识为uuncle。情况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 pairK, 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;红黑树的验证红黑树的验证本质就是对照五条核心性质逐项检查确认这棵树既是合法的二叉搜索树又严格符合颜色与黑高约束。具体验证逻辑如下二叉搜索树性质先通过中序遍历确认节点值严格有序确保树本身是合法的 BST。根节点为黑直接检查根节点颜色若为红则不合法。无连续红色节点遍历每个红色节点检查其父节点和子节点是否均为黑色NIL 视为黑。黑高一致性从根节点出发递归计算每条到 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树的比较对比维度红黑树AVL 树平衡条件宽松最长路径 ≤ 2倍最短路径严格左右子树高度差 ≤ 1高度略高但仍是 O(log n)更低理论上查找更快插入/删除效率旋转次数少更优旋转次数可能更多但查找略快适用场景写多读少如 JavaTreeMap、C STLmap读多写少如词典查找、数据库索引红黑树模拟实现STL中的set和map在实现完红黑树的基本结构之后我们要尝试用红黑树来封装set和map改造红黑树在标准库的实现中map和set底层通常共用同一套红黑树代码。为了适配这种复用红黑树节点中存储的数据类型不再写死为K或pairconst K, V而是定义为一个泛型参数T。这样一来就产生了一个问题当红黑树内部需要比较两个节点的大小比如执行插入、查找时它面对的只是泛型T并不知道应该比较什么字段。对于setT就是K本身直接比较K即可但对于mapT是pairK, V而比较规则要求只看键K忽略值V。pair默认的比较运算符会先比较K相等时还会比较V这既不符合语义也会引入不必要的开销。解决这个矛盾的办法是将“如何从T中取出键”这一行为抽象成一个仿函数由上层调用方提供。具体做法如下在RBTree模板参数中增加一个KeyOfT类型它必须是一个可调用对象负责从T类型的实例中提取出用于比较的键K。在map的实现层定义一个仿函数MapKeyOfT其operator()接收pairconst 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用pairconst K, V。改造后的红黑树代码#pragma once #includeiostream using namespace std; enum Color { BLACK, RED }; templateclass T struct RBTreeNode { T _data; RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; Color _col; RBTreeNode(const T data) :_data(data) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) { } }; templateclass T, class Ref, class Ptr struct RBTreeIterator { typedef RBTreeNodeT Node; typedef RBTreeIteratorT, 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; } }; templateclass K, class T, class KeyOfT class RBTree { typedef RBTreeNodeT Node; public: typedef RBTreeIteratorT, T, T* Iterator; typedef RBTreeIteratorT, 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); } pairIterator, 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 #includeRBTree4.13.h namespace Rane { templateclass K class set { struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: typedef typename RBTreeK, const K, SetKeyOfT::Iterator iterator; typedef typename RBTreeK, 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(); } pairiterator, bool insert(const K key) { return _t.Insert(key); } private: RBTreeK, const K, SetKeyOfT _t; }; }map的模拟实现#pragma once #includeRBTree4.13.h namespace Rane { templateclass K, class V class map { struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first; } }; public: typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator; typedef typename RBTreeK, pairconst 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(); } pairiterator, bool insert(const pairK, V kv) { return _t.Insert(kv); } V operator[](const K key) { pairiterator, bool ret insert({ key, V() }); return ret.first-second; } private: RBTreeK, pairconst K, V, MapKeyOfT _t; }; }