0
0

[数据结构 - C++] 红黑树RBTree

在这里插入图片描述

文章目录

1、前言

我们在学习了二叉搜索树后，在它的基础上又学习了AVL树，知道了AVL树是靠平衡因子来调节左右高度差，从而让树变得平衡的。本篇我们再来学习一个依靠另一种平衡规则来控制的二叉搜索树——红黑树。

2、红黑树的概念

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

3、红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（红色不能连续，黑色可以连续）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
概念中，说到没有一条路径会比其他路径长出俩倍，性质3与性质4相互牵制就可以保证这一点。

4、红黑树节点的定义

我们定义节点依然是三叉链，与AVL树不同的是红黑树没有平衡因子，而是保存一个代表节点颜色的属性。

  1. enumColor{
  2.     RED,
  3.     BLACK
  4. };
  6. template <class K, class V>structRBTreeNode{
  7.     RBTreeNode<K, V>* _left;
  8.     RBTreeNode<K, V>* _right;
  9.     RBTreeNode<K, V>* _parent;
  10.     pair<K, V> _kv;
  11.     Color _col;RBTreeNode(const pair<K, V>& _kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}};

这里我们定义的红黑树节点，颜色默认给的红色，但是这里是给红色还是黑色合适呢？
当插入的时候，我们新插入的节点颜色是黑色时，就会破坏性质3，新插入节点的这条路径的黑色节点数一定会比其他路径的黑色节点多一个，影响整棵树。
如果是红色，那插入的时候她的父节点可能是黑色，没有影响，可能是红色，那么就会出现连续的红色节点，但是它只会影响这一条路径。
这两种颜色插入，黑色是一定会影响，红色是可能会影响的，且黑色影响整棵树，红色影响它这一条路径，两害取其轻，我们选择红色，调整的话也比较容易调整。下面我们就来尝试看插入怎么写：

5、红黑树的插入Insert

红黑树的插入是在二叉搜索树插入基础上来修改的，因此大的方向分两步走：
1、找到插入的位置；
2、插入节点后，根据性质来调节平衡。

  1. bool Insert(const pair<K, V>& kv){if(nullptr == _root){
  2.         _root = new Node(data);
  3.         _root->_col = BLACK;// 性质2：根节点是黑色return true;}
  5.     Node* parent = nullptr;
  6.     Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){
  7.             parent = cur;
  8.             cur = cur->_right;}elseif(cur->_kv.first > kv.first){
  9.             parent = cur;
  10.             cur = cur->_left;}else{return false;}}// 新增插入节点是红色只会影响父节点，如果是黑色影响所有路径// 所以 new 的节点为红色
  11.     cur = new Node(kv);
  12.     cur->_col = RED;if(parent->_kv.first < kv.first){
  13.         parent->_right = cur;
  14.         cur->_parent = parent;}else{
  15.         parent->_left = cur;
  16.         cur->_parent = parent;}// 维护处理 ...}

当来到这块时，已经插入了，要做的就是按照性质来检查和维护这棵树了。
1、当父亲是黑色，那么就不用维护，就结束了；
2、当父亲是红色，那么就违反了性质3（不能存在连续的红色节点），这时就需要调整了，调整也是要分情况讨论（约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点）。
情况一：cur是红色，p为红色，g为黑色，u存在且为红色
这里看到的这棵树可能是完整的，也可能是子树：
在这里插入图片描述

如果是完整的树，那么改完之后，需要将g的颜色改为黑色。
如果g是子树，那么g就有父节点，这时g的颜色改为红色，父节点颜色可能也是红色，这时急需要继续向上调整了。
将p，u改为黑，g改为红，然后把g当作cur，继续向上调整。
情况二：cur是红色，p为红色，g为黑色，u不存在/u存在且为黑色
在这里插入图片描述

这里u有两种颜色，我们分开讨论：

  • 如果u不存在，那么cur一定是新增。因为u不存在g也是有一条右边路径的，这条路径就两个黑色节点（空结点也是黑色），那么c就不存在，a、b都不存在，如果存在就是黑色节点，那么就打破了性质3。
  • 如果存在且为黑，那么这个抽象图就不全。因为父节是红色，叔叔为黑色，每条路径的黑色节点个数要相同，因此推测出cur之前应该是黑色，那么a、b就应该是红色，新增节点在a/b的孩子位置。 整体就为下图：在这里插入图片描述

它会先经过情况一的调整方式，调整完变为情况二这样，然后再继续调整：
在这里插入图片描述

此时，就 以g为基点先右旋，然后将父节点颜色变为黑色，祖父节点颜色变为红色。（旋转不清楚的同学可以看看AVL树的）
情况三：cur是红色，p为红色，g为黑色，u不存在/u存在且为黑色
在这里插入图片描述

  • u不存在，cur是新增。因为每条路径的黑色节点个数相同，u不存在，u这条路径上两个黑色节点（空结点也是黑色），推测出a、b、c都是不存在的，那么cur就是新增，如果存在只能是黑色节点，那么就打破了性质3。
  • 如果存在且为黑，这个抽象图依然是不完整的。因为父节点是红色，叔叔为黑色，每条路径的黑色节点相同，因此推测出a为黑色，cur之前也应该为黑色，那么b、c就应该是红色，新增节点在b/c的孩子位置。

图跟情况二中，u存在且为黑差不多：
在这里插入图片描述

会先经过情况一调整，变为情况三这样，然后进行调整：
在这里插入图片描述

此时，先以p为基点左旋，再以g为基点右旋，然后将cur节点变为黑色，祖父节点变为红色。
如果新增的父节点在右，叔叔节点在左，那么也是分以上三种情况，调整方式也是对应三种方式差不多，这里就不过多赘述，直接上代码：

  1. bool Insert(const pair<K, V>& kv){if(nullptr == _root){
  2.         _root = new Node(data);
  3.         _root->_col = BLACK;// 性质2：根节点是黑色return true;}
  5.     Node* parent = nullptr;
  6.     Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){
  7.             parent = cur;
  8.             cur = cur->_right;}elseif(cur->_kv.first > kv.first){
  9.             parent = cur;
  10.             cur = cur->_left;}else{return false;}}// 新增插入节点是红色只会影响父节点，如果是黑色影响所有路径// 所以 new 的节点为红色
  11.     cur = new Node(kv);
  12.     cur->_col = RED;if(parent->_kv.first < kv.first){
  13.         parent->_right = cur;
  14.         cur->_parent = parent;}else{
  15.         parent->_left = cur;
  16.         cur->_parent = parent;}// 不断向上调整的，所以得用whilewhile(parent && parent->_col == RED){// 父节点是祖父节点的左//      g//    p   u//  c 
  17.         Node* grandfather = parent->_parent;// 1、父节点在祖父的左，即叔叔在右if(parent == grandfather->_left){
  18.             Node* uncle = grandfather->_right;// 1.1 叔叔存在并且为红if(uncle && uncle->_col == RED){// 变色
  19.                 parent->_col = uncle->_col = BLACK;
  20.                 grandfather->_col = RED;// 向上调整
  21.                 cur = grandfather;
  22.                 parent = cur->_parent;}// 1.2 叔叔不存在 / 叔叔存在且为黑，处理方法一样else{if(cur == parent->_left)// 左边高的情况{// 右单旋//     g//   p   u// cRotateR(grandfather);
  23.                     parent->_col = BLACK;
  24.                     grandfather->_col = RED;}else// 左边高右边高的情况{// 双旋//     g//  p     u//    cRotateL(parent);RotateR(grandfather);
  25.                     cur->_col = BLACK;
  26.                     grandfather->_col = RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}// 2、父节点在祖父的右，即叔叔在祖父的左else// parent == grandfather->_right{//     g//   u   p//         c
  27.             Node* uncle = grandfather->_left;// 2.1 叔叔存在且叔叔为红色if(uncle && uncle->_col == RED){// 变色
  28.                 parent->_col = uncle->_col = BLACK;
  29.                 grandfather->_col = RED;// 向上调整
  30.                 cur = grandfather;
  31.                 parent = cur->_parent;}// 2.2 叔叔不存在 / 叔叔存在且颜色为黑，处理方法一样else{if(cur == parent->_right)// 右边高的情况{//     g//   u   p//         cRotateL(grandfather);
  32.                     parent->_col = BLACK;
  33.                     grandfather->_col = RED;}else// 右边高，左边高{//     g//  u     p//      cRotateR(parent);RotateL(grandfather);
  34.                     cur->_col = BLACK;
  35.                     grandfather->_col = RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}}// 最后将根节点变为黑色
  36.     _root->_col = BLACK;return true;}// 左单旋voidRotateL(Node* parent){
  37.     Node* subR = parent->_right;
  38.     Node* subRL = subR->_left;
  39.     Node* parentParent = parent->_parent;
  41.     parent->_right = subRL;if(subRL)
  42.         subRL->_parent = parent;
  43.     subR->_left = parent;
  44.     parent->_parent = subR;if(_root == parent)// 父节点就是根节点{
  45.         _root = subR;
  46.         subR->_parent = nullptr;}else// 子树情况{if(parentParent->_left == parent){
  47.             parentParent->_left = subR;}else{
  48.             parentParent->_right = subR;}
  49.         subR->_parent = parentParent;}}// 右单旋voidRotateR(Node* parent){
  50.     Node* parentParent = parent->_parent;
  51.     Node* subL = parent->_left;
  52.     Node* subLR = subL->_right;
  54.     parent->_left = subLR;if(subLR)
  55.         subLR->_parent = parent;
  56.     subL->_right = parent;
  57.     parent->_parent = subL;if(_root == parent)// 父节点是根节点{
  58.         _root = subL;
  59.         subL->_parent = nullptr;}else// 子树情况{if(parentParent->_left == parent){
  60.             parentParent->_left = subL;}else{
  61.             parentParent->_right = subL;}
  62.         subL->_parent = parentParent;}}

6、红黑树的验证

红色树的验证本质就是验证两方面：
1、是否为二叉搜索树（中序遍历是否有序）；
2、是否满足5条性质。

  1. void_InOrder(Node* pRoot){if(pRoot == nullptr)return;_InOrder(pRoot->_left);
  2.     cout << pRoot->_data <<" ";_InOrder(pRoot->_right);}
  4. bool IsBalance(){if(_root == nullptr)return true;if(_root->_col == RED)return false;// 参考值int refValue =0;
  5.     Node* cur = _root;while(cur){if(cur->_col == BLACK) refValue++;
  7.         cur = cur->_left;}// 检查每条路径黑色节点个数// 思路：以上面参考值为主，对比每条路径的黑色节点个数// 当走到空就说明该路径走完了，那么这个过程中记录下黑色节点个数，到空时与refValue对比// 这里传进去blacknum只能是传值，这样就不会影响上一层的blacknum了int blacknum =0;// 检查连续红色节点与每条路径黑色节点个数returnCheck(_root, blacknum, refValue);}
  8. bool Check(Node* root,int blacknum,constint& refValue){if(root == nullptr){if(blacknum != refValue){
  9.             cout <<"存在黑色节点不相等的路径"<< endl;return false;}return true;}// 反向检查，查看当前与父结点为红色(当前节点为红色就说明不是根节点，即存在父节点)if(root->_col == RED && root->_parent->_col == RED){
  10.         cout <<"有连续的红色节点"<< endl;return false;}if(root->_col == BLACK) blacknum++;returnCheck(root->_left, blacknum, refValue)&&Check(root->_right, blacknum, refValue);}

7、红黑树与AVL树的比较

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

附录：

  1. enumColor{
  2.     RED,
  3.     BLACK
  4. };
  6. template <class K, class V>structRBTreeNode{
  7.     RBTreeNode<K, V>* _left;
  8.     RBTreeNode<K, V>* _right;
  9.     RBTreeNode<K, V>* _parent;
  10.     pair<K, V> _kv;
  11.     Color _col;RBTreeNode(const pair<K, V>& _kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}};
  13. template <class K, class V>
  14. class RBTree
  15. {typedef RBTreeNode<K,V> Node;
  16. public:
  17.     bool Insert(const pair<K, V>& kv){if(nullptr == _root){
  18.             _root = new Node(data);
  19.             _root->_col = BLACK;// 性质2：根节点是黑色return true;}
  20.     
  21.         Node* parent = nullptr;
  22.         Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){
  23.                 parent = cur;
  24.                 cur = cur->_right;}elseif(cur->_kv.first > kv.first){
  25.                 parent = cur;
  26.                 cur = cur->_left;}else{return false;}}// 新增插入节点是红色只会影响父节点，如果是黑色影响所有路径// 所以 new 的节点为红色
  27.         cur = new Node(kv);
  28.         cur->_col = RED;if(parent->_kv.first < kv.first){
  29.             parent->_right = cur;
  30.             cur->_parent = parent;}else{
  31.             parent->_left = cur;
  32.             cur->_parent = parent;}// 不断向上调整的，所以得用whilewhile(parent && parent->_col == RED){// 父节点是祖父节点的左//      g//    p   u//  c 
  33.             Node* grandfather = parent->_parent;// 1、父节点在祖父的左，即叔叔在右if(parent == grandfather->_left){
  34.                 Node* uncle = grandfather->_right;// 1.1 叔叔存在并且为红if(uncle && uncle->_col == RED){// 变色
  35.                     parent->_col = uncle->_col = BLACK;
  36.                     grandfather->_col = RED;// 向上调整
  37.                     cur = grandfather;
  38.                     parent = cur->_parent;}// 1.2 叔叔不存在 / 叔叔存在且为黑，处理方法一样else{if(cur == parent->_left)// 左边高的情况{// 右单旋//     g//   p   u// cRotateR(grandfather);
  39.                         parent->_col = BLACK;
  40.                         grandfather->_col = RED;}else// 左边高右边高的情况{// 双旋//     g//  p     u//    cRotateL(parent);RotateR(grandfather);
  41.                         cur->_col = BLACK;
  42.                         grandfather->_col = RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}// 2、父节点在祖父的右，即叔叔在祖父的左else// parent == grandfather->_right{//     g//   u   p//         c
  43.                 Node* uncle = grandfather->_left;// 2.1 叔叔存在且叔叔为红色if(uncle && uncle->_col == RED){// 变色
  44.                     parent->_col = uncle->_col = BLACK;
  45.                     grandfather->_col = RED;// 向上调整
  46.                     cur = grandfather;
  47.                     parent = cur->_parent;}// 2.2 叔叔不存在 / 叔叔存在且颜色为黑，处理方法一样else{if(cur == parent->_right)// 右边高的情况{//     g//   u   p//         cRotateL(grandfather);
  48.                         parent->_col = BLACK;
  49.                         grandfather->_col = RED;}else// 右边高，左边高{//     g//  u     p//      cRotateR(parent);RotateL(grandfather);
  50.                         cur->_col = BLACK;
  51.                         grandfather->_col = RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}}// 最后将根节点变为黑色
  52.         _root->_col = BLACK;return true;}
  53.     
  54.     bool Find(const K& key){
  55.         Node* cur = _root;while(cur){if(cur->_key < key){
  56.                 cur = cur->_right;}elseif(cur->_key > key){
  57.                 cur = cur->_left;}else{return true;}}return true;}
  59.     bool IsBalance(){if(_root == nullptr)return true;if(_root->_col == RED)return false;// 参考值int refValue =0;
  60.         Node* cur = _root;while(cur){if(cur->_col == BLACK) refValue++;
  62.             cur = cur->_left;}// 检查每条路径黑色节点个数// 思路：以上面参考值为主，对比每条路径的黑色节点个数// 当走到空就说明该路径走完了，那么这个过程中记录下黑色节点个数，到空时与refValue对比// 这里传进去blacknum只能是传值，这样就不会影响上一层的blacknum了int blacknum =0;// 检查连续红色节点与每条路径黑色节点个数returnCheck(_root, blacknum, refValue);}size_tHeight(){return_Height(_root);}voidInOrder(){_InOrder(_root);
  63.         cout << endl;}
  65. private:
  66.     bool Check(Node* root,int blacknum,constint& refValue){if(root == nullptr){if(blacknum != refValue){
  67.                 cout <<"存在黑色节点不相等的路径"<< endl;return false;}return true;}// 反向检查，查看当前与父结点为红色(当前节点为红色就说明不是根节点，即存在父节点)if(root->_col == RED && root->_parent->_col == RED){
  68.             cout <<"有连续的红色节点"<< endl;return false;}if(root->_col == BLACK) blacknum++;returnCheck(root->_left, blacknum, refValue)&&Check(root->_right, blacknum, refValue);}// 左单旋voidRotateL(Node* parent){
  69.         Node* subR = parent->_right;
  70.         Node* subRL = subR->_left;
  71.         Node* parentParent = parent->_parent;
  73.         parent->_right = subRL;if(subRL)
  74.             subRL->_parent = parent;
  75.         subR->_left = parent;
  76.         parent->_parent = subR;if(_root == parent)// 父节点就是根节点{
  77.             _root = subR;
  78.             subR->_parent = nullptr;}else// 子树情况{if(parentParent->_left == parent){
  79.                 parentParent->_left = subR;}else{
  80.                 parentParent->_right = subR;}
  81.             subR->_parent = parentParent;}}// 右单旋voidRotateR(Node* parent){
  82.         Node* parentParent = parent->_parent;
  83.         Node* subL = parent->_left;
  84.         Node* subLR = subL->_right;
  86.         parent->_left = subLR;if(subLR)
  87.             subLR->_parent = parent;
  88.         subL->_right = parent;
  89.         parent->_parent = subL;if(_root == parent)// 父节点是根节点{
  90.             _root = subL;
  91.             subL->_parent = nullptr;}else// 子树情况{if(parentParent->_left == parent){
  92.                 parentParent->_left = subL;}else{
  93.                 parentParent->_right = subL;}
  94.             subL->_parent = parentParent;}}void_InOrder(Node* pRoot){if(pRoot == nullptr)return;_InOrder(pRoot->_left);
  95.         cout << pRoot->_data <<" ";_InOrder(pRoot->_right);}size_t_Height(Node* pRoot){if(pRoot == nullptr)return0;int leftHeight =_Height(pRoot->_left);int rightHeight =_Height(pRoot->_right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}
  97. private:
  98.     Node* _root = nullptr;};
标签： 数据结构 c++
本文转载自: https://blog.csdn.net/Ljy_cx_21_4_3/article/details/135738338
版权归原作者 小白在努力jy 所有， 如有侵权，请联系我们删除。
登录后发布评论

“[数据结构 - C++] 红黑树RBTree”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？