欢迎来到尧图网

客户服务 关于我们

您的位置：首页 > 科技 > IT业 > C++_进阶：红黑树模拟实现

C++_进阶：红黑树模拟实现

2025/6/10 0:35:08 来源：https://blog.csdn.net/Lvision2/article/details/141431293  浏览:  次   关键词：C++_进阶：红黑树模拟实现

文章目录

    • 1. 🚀红黑树的概念
    • 2. 🚀红黑树的性质🔻
    • 3. 🚀红黑树节点的定义
    • 4. 🚀红黑树的插入操作🔻
    • 5. 🚀 红黑树的验证
    • 6. 🚀红黑树与AVL树的比较
    • 7. 🚀红黑树的迭代器
    • 8. 🚀红黑树模拟实现

1. 🚀红黑树的概念

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

2. 🚀红黑树的性质🔻

红黑树的性质也就是它的规则，在红黑树的结构构建中需要严格遵循以下性质：

  1. 🔻每个结点不是红色就是黑色。
  2. 🔻根节点是黑色的。
  3. 🔻如果一个节点是红色的，则它的两个孩子结点是黑色的(在一条路径中没有连续的红色节点)。
  4. 🔻对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(每条路径的黑色节点个数相同)。
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点。

❓为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍?

🔹要探讨这个问题，我们先要按照规则，找出理论的最短节点，与理论的最长节点

在这里插入图片描述
🔹AVL树只要出现高度差等于2的树就会开始调整保证平衡，相比较下，红黑树平衡调整的次数较少，红黑树允许更大高度差的树结构。
🔹AVL树是严格平衡，红黑树是近似平衡。

3. 🚀红黑树节点的定义

🔹在平衡二叉树(KV结构)的基础上，红黑树节点比一般平衡二叉树多了parent指针(指向父亲节点的指针)和colour(颜色枚举)。

//红黑树节点的颜色
enum Colour
{RED,BALCK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;//键值对RBTreeNode<K, V>* _left;//左孩子RBTreeNode<K, V>* _right;//右孩子RBTreeNode<K, V>* _parent;//父亲Colour colour = RED;//颜色-> 注意: 默认为红色节点//构造函数RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};

4. 🚀红黑树的插入操作🔻

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

  1. 按照二叉搜索树规则插入新节点
bool Insert(const pair<K, V>& kv)
{//第一步，如二叉搜索树一样插入节点if (_root == nullptr){_root = new Node(kv);_root->colour = BALCK;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);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//...//第二步...
}

2. 检测新节点插入后，红黑树的性质是否造到破坏
🔹因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是👥黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为💂红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

  • 情况1：cur红，p红，u存在且为红，平衡调整操作👇
    在这里插入图片描述
    🔹在调整后，需要考虑是否需要继续向上调整：
    在这里插入图片描述
    🔹为什么不能直接将p改为黑色节点❓
    在这里插入图片描述

  • 情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑,平衡调整操作👇
    在这里插入图片描述
    在这里插入图片描述

🔹说明:u的情况有两种

  1. 如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色，就不满足性质4:每条路径黑色节点个数相同。
  2. 如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。
    blog.csdnimg.cn/direct/39ccea2cd99b41c3bb962ecdf834807b.png)
  • 情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑，平衡调整操作👇
    在这里插入图片描述

在这里插入图片描述

bool Insert(const pair<K, V>& kv)
{//第一步，如二叉搜索树一样插入节点if (_root == nullptr){_root = new Node(kv);_root->colour = BALCK;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);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//第二步：while (parent&& parent->colour == RED){Node* grand = parent->_parent;if (grand->_left == parent){Node* uncle = grand->_right;//uncle 存在且为红//	g// f  u//cif (uncle && uncle->colour == RED){uncle->colour = BALCK;parent->colour = BALCK;grand->colour = RED;cur = grand;parent = cur->_parent;}//uncle 不存在或为黑else{if (parent->_left == cur){//	gB// fR  uB//cR 单旋转parent->colour = BALCK;grand->colour = RED;RotateR(grand);}else{//	g// f  u//  c 双旋cur->colour = BALCK;grand->colour = RED;RotateL(parent);RotateR(grand);}break;}}else{Node* uncle = grand->_left;//uncle 存在且为红//	g// u  f//      cif (uncle && uncle->colour == RED){uncle->colour = BALCK;parent->colour = BALCK;grand->colour = RED;cur = grand;parent = cur->_parent;}else{if (parent->_left == cur){//	g// u  f//      cparent->colour = BALCK;grand->colour = RED;RotateL(grand);}else{//	g// u  f//    ccur->colour = BALCK;grand->colour = RED;//RotateLR(grand);RotateL(parent);RotateR(grand);}break;}}}_root->colour = BALCK;return true;
}//左旋逻辑
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}
//右旋逻辑
void  RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}

5. 🚀 红黑树的验证

bool IsValidRBTree()
{Node* pRoot =_root;// 空树也是红黑树if (nullptr == pRoot)return true;// 检测根节点是否满足情况if (BALCK != pRoot->colour){cout << "违反红黑树性质二：根节点必须为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackCount = 0;Node* pCur = pRoot;while (pCur){if (BALCK == pCur->colour)blackCount++;pCur = pCur->_left;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(pRoot, k, blackCount);
}bool _IsValidRBTree(Node pRoot, size_t k, const size_t blackCount)
{//走到null之后，判断k和black是否相等if (nullptr == pRoot){if (k != blackCount){cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;return false;}return true;}// 统计黑色节点的个数if (BALCK == pRoot->colour)k++;// 检测当前节点与其双亲是否都为红色Node* pParent = pRoot->_parent;if (pParent && RED == pParent->colour && RED == pRoot->colour){cout << "违反性质三：没有连在一起的红色节点" << endl;return false;}return _IsValidRBTree(pRoot->_left, k, blackCount) &&_IsValidRBTree(pRoot->_right, k, blackCount);
}

6. 🚀红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

7. 🚀红黑树的迭代器

要实现红黑树的迭代器先要明确红黑树的begin()，end()。

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置。
关键是最大节点的下一个位置在哪块？在库中的方式是，在根节点之前有一个header节点作为头结点，最右侧节点的下一个位置设置为header。
在这里插入图片描述
在模拟实现中并没有实现header，而是将end()设置为nullptr，再做特殊处理。

🔹迭代器遍历
我们知道，红黑树的中序遍历是有序序列，对迭代器节点的下一个位置，就是当前节点中序遍历的下一个位置，中序找下一个节点有两种情况：

  1. 🔸 右子树不为空
    在这里插入图片描述
  2. 🔸右子树为空
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
//红黑树中序找到下一个节点规则
Self& operator++()
{//有两种情况//当右子树不为空//直接找到右子树的最左节点if (_node->_right){Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{//右子树为空//找到cur 与 parent是左孩子关系的节点Node* cur = _node;Node* parent = cur->_parent;while(parent&& parent->_right == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

红黑树中序找到上一个节点规则与 operator++类似
Self& operator--()
{// --end()，特殊处理，走到中序最后一个节点，整棵树的最右节点if (_node == nullptr) // end(){Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

8. 🚀红黑树模拟实现

#pragma once
#include<iostream>
#include <assert.h>
using namespace std;
//颜色枚举
enum Colour
{RED,BALCK
};//迭代器
template<class T,class Ref,class Ptr>
struct RBTreeiterator
{typedef RBTreeiterator<T,Ref,Ptr> Self;typedef RBTreeNode<T> Node;Node* _node;Node* _root;RBTreeiterator(Node* node , Node * root):_node(node),_root(root){};//++逻辑Self& operator++(){if (_node->_right){Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{Node* cur = _node;Node* parent = cur->_parent;while(parent&& parent->_right == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//--逻辑Self& operator--(){// --end()，特殊处理，走到中序最后一个节点，整棵树的最右节点if (_node == nullptr) // end(){Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!= (const Self& s){return _node != s._node;}};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour colour = RED;RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};template<class K, class V>
class RBTree
{typedef RBTreeiterator<T,T&,T*> Iterator;typedef RBTreeiterator<T,const T&, const T*> ConstIterator;typedef RBTreeNode<K, V> Node;
public:RBTree() = default;RBTree(const RBTree<K, V>& t){_root = Copy(t._root);}RBTree<K, V>& operator=(RBTree<K, V> t){swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}//插入逻辑bool Insert(const pair<K, V>& kv){// 1 二叉搜索树插入规则if (_root == nullptr){_root = new Node(kv);_root->colour = BALCK;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);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//2. 红黑树平衡规则while (parent&& parent->colour == RED){Node* grand = parent->_parent;if (grand->_left == parent){Node* uncle = grand->_right;//uncle 存在且为红//	g// f  u//cif (uncle && uncle->colour == RED){uncle->colour = BALCK;parent->colour = BALCK;grand->colour = RED;cur = grand;parent = cur->_parent;}//uncle 不存在或为黑else{if (parent->_left == cur){//	gB// fR  uB//cR 单旋转parent->colour = BALCK;grand->colour = RED;RotateR(grand);}else{//	g// f  u//  c 双旋cur->colour = BALCK;grand->colour = RED;RotateL(parent);RotateR(grand);}break;}}else{Node* uncle = grand->_left;//uncle 存在且为红//	g// u  f//      cif (uncle && uncle->colour == RED){uncle->colour = BALCK;parent->colour = BALCK;grand->colour = RED;cur = grand;parent = cur->_parent;}else{if (parent->_left == cur){//	g// u  f//      cparent->colour = BALCK;grand->colour = RED;RotateL(grand);}else{//	g// u  f//    ccur->colour = BALCK;grand->colour = RED;//RotateLR(grand);RotateL(parent);RotateR(grand);}break;}}}_root->colour = BALCK;return true;}//验证是否符合红黑树bool IsValidRBTree(){Node* pRoot =_root;// 空树也是红黑树if (nullptr == pRoot)return true;// 检测根节点是否满足情况if (BALCK != pRoot->colour){cout << "违反红黑树性质二：根节点必须为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackCount = 0;Node* pCur = pRoot;while (pCur){if (BALCK == pCur->colour)blackCount++;pCur = pCur->_left;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(pRoot, k, blackCount);}bool _IsValidRBTree(Node pRoot, size_t k, const size_t blackCount){//走到null之后，判断k和black是否相等if (nullptr == pRoot){if (k != blackCount){cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;return false;}return true;}// 统计黑色节点的个数if (BALCK == pRoot->colour)k++;// 检测当前节点与其双亲是否都为红色Node* pParent = pRoot->_parent;if (pParent && RED == pParent->colour && RED == pRoot->colour){cout << "违反性质三：没有连在一起的红色节点" << endl;return false;}return _IsValidRBTree(pRoot->_left, k, blackCount) &&_IsValidRBTree(pRoot->_right, k, blackCount);}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;}void InOrder(){inOrder(_root);cout << endl;}private:int _Height(Node* pRoot){if (pRoot == nullptr){return 0;}size_t leftH = _Height(pRoot->_left);size_t rightH = _Height(pRoot->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}void inOrder(Node* root){if (root == nullptr){return;}inOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << " ";inOrder(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}void  RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;
};

本文就到这里，感谢你看到这里❤️❤️！ 我知道一些人看文章喜欢静静看，不评论🤔，但是他会点赞😍，这样的人，帅气低调有内涵😎，美丽大方很优雅😊，明人不说暗话，要你手上的一个点赞😘！

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

相关资讯

热文排行

最新新闻

推荐新闻

热搜词