devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++实现红黑树_c遍历红黑树

作者：不正经 | 2024-03-16 02:05:54

赞

踩

c遍历红黑树

红黑树的基本概念：

红黑树是一个平衡二叉树（左子节点比当前节点小，右子节点比当前节点大）。

一棵红黑树需要满足以下条件：

1.根节点的颜色是黑色的。

2.一个节点要么是黑色，要么是红色。

3.红色节点的子节点必须是黑色节点。（红色节点被黑色节点隔开）

4.叶子节点的颜色是黑色的。

5.从根节点出发到叶子节点，每一条路径的黑色节点数量是相同的。（黑高）。

红黑树的类声明：

  1. #include"iostream"
  2. #include"math.h"
  3. using namespace std;
  4.  
  5.  
  6. #define RED 0
  7. #define BLACK 1
  8.  
  9. class RBtree{
  10. private:
  11. // 红黑树的属性
  12.  
  13.  
  14.     
  15.  
  16.     
  17.  
  18. public:
  19.  
  20.  
  21.     RBtree();
  22.     // 根节点
  23.     RBtree *root;
  24.     // 数据
  25.     int data;
  26.         // 颜色
  27.     bool color;
  28.     // 父亲节点
  29.     RBtree *parent;
  30.     // 左子节点
  31.     RBtree *left;
  32.     // 右子节点
  33.     RBtree *right;
  34.  
  35.  
  36.  
  37.  
  38.     // 节点插入函数,传入一个数据和一个根节点
  39.     RBtree *rbinsert(int data,RBtree *root);
  40.     // 节点删除传入一个要删除的数据和一个节点
  41.     RBtree *rbdelete(int data,RBtree *root);
  42.     // 节点的查找
  43.     RBtree *rbsearch(int data,RBtree *root);
  44.     
  45.     // 最大值
  46.     RBtree *rbmax(RBtree *root);
  47.     // 最小值
  48.     RBtree *rbmin(RBtree *root);
  49.  
  50.    // 右旋转
  51.     RBtree *rrotate(RBtree *root,RBtree *x);
  52.      // 左旋转
  53.     RBtree *lrotate(RBtree *root,RBtree *x);
  54.  
  55.     // 插入修复
  56.     RBtree *rbinsertfixup(RBtree *x);
  57.  
  58.     // 树的遍历
  59.     void rbprint(RBtree *x);
  60.  
  61.  
  62.  
  63.     
  64.     ~RBtree();
  65.  
  66. };

红黑树的插入：

  1. #include"RBtree.h"
  2. // 插入修复
  3. RBtree *insert_fixup(RBtree *root,RBtree *x)
  4. {
  5.  
  6. //  如果x的父节点的color是red,并且x节点不是root节点
  7.     while (x->parent && x->parent->color==RED)
  8.     {
  9.         // 如果x的父是在祖父节点的左边
  10.         if(x->parent == x->parent->parent->left)
  11.         {
  12.             // 确定叔叔节点
  13.             RBtree *y = x->parent->parent->right;
  14.             // 情况1：y节点的颜色是red,并且y不是空节点
  15.             if(y && y->color==RED)
  16.             {
  17.                 x->parent->color=BLACK;
  18.                 y->color=BLACK;
  19.                 x= y->parent;
  20.                 x->color=RED;
  21.             }
  22.             // 情况2：y节点是黑色的，并且x的位置是三角型
  23.             else 
  24.             if(x==x->parent->right)
  25.             {
  26.                 x=x->parent;
  27.                 root=root->lrotate(root,x);
  28.             }
  29.             // 情况3：y的节点是黑色，并且x的位置是直线
  30.             else
  31.             {
  32.                 x->parent->color=BLACK;
  33.                 x->parent->parent->color=RED;
  34.                 root=root->rrotate(root,x->parent->parent);
  35.             }
  36.         }
  37.         else
  38.         // x的父节点在祖父节点的右边
  39.         {
  40.             // 确定叔叔节点
  41.             RBtree *y = x->parent->parent->left;
  42.             // 情况1：y节点的颜色是red,并且y不是空节点
  43.             if(y && y->color==RED)
  44.             {
  45.                 x->parent->color=BLACK;
  46.                 y->color=BLACK;
  47.                 x= y->parent;
  48.                 x->color=RED;
  49.             }
  50.             // 情况2：y节点是黑色的，并且x的位置是三角型
  51.             else 
  52.             if(x==x->parent->left)
  53.             {
  54.                 x=x->parent;
  55.                 root=root->rrotate(root,x);
  56.             }
  57.             // 情况3：y的节点是黑色，并且x的位置是直线
  58.             else
  59.             {
  60.                 x->parent->color=BLACK;
  61.                 x->parent->parent->color=RED;
  62.                 root=root->lrotate(root,x->parent->parent);
  63.             }
  64.         }
  65.     }
  66.     // 根节点的颜色始终是黑色
  67.     root->color=BLACK;
  68.     return root;
  69.     
  70. }
  71. RBtree * RBtree::rbinsert(int data,RBtree *root)
  72. {
  73.     //  实现将data插入rbtree
  74.  
  75.     // 创建一个节点得到数据
  76.     RBtree *newnode = new RBtree;
  77.  
  78.     newnode->data = data;
  79.  
  80.     // 如果root为空，第一个节点
  81.     if(root== nullptr)
  82.     {
  83.         // 直接就是根节点
  84.         root=newnode;
  85.     }
  86.     // 如果root不为空
  87.     // 开始插入
  88.     else
  89.     {
  90.         //辅助指针
  91.         RBtree *x = root;
  92.         RBtree *y;
  93.         // 如果x不为空
  94.         while(x)
  95.         {
  96.             // y的位置始终在x的后面
  97.             y=x;
  98.             // 如果newnode的data比x的data小
  99.             if(newnode->data<x->data)
  100.             {
  101.                 // 从左边走
  102.                 x=x->left;
  103.             }
  104.             else
  105.             {
  106.                 // 从右边走
  107.                 x=x->right;
  108.             }
  109.         }
  110.         // 开始连接
  111.         // 确定newnode的父节点
  112.         newnode->parent=y;
  113.         if(newnode->data<y->data)
  114.         {
  115.             // 连接左边
  116.             y->left=newnode;
  117.         }
  118.         else
  119.         {
  120.             y->right=newnode;
  121.         }
  122.  
  123.         
  124.  
  125.     }
  126.     // 对newnode节点进行修复
  127.     root=insert_fixup(root,newnode);
  128.  
  129.  
  130.     return root;
  131. }

红黑树的删除：

  1. #include"RBtree.h"
  2.  
  3. RBtree *delete_fixup(RBtree *root,RBtree *x)
  4. {
  5.     while(x!=root && x->color==BLACK)
  6.     {
  7.         // 判断x的位置
  8.         if(x==x->parent->left)
  9.         {
  10.             // 确定w节点
  11.             RBtree *w=x->parent->right;
  12.             
  13.  
  14.             // 情况1：w是红色节点
  15.             if(w->color==RED)
  16.             {
  17.                 // 将w的颜色染成黑色
  18.                 w->color=BLACK;
  19.                 // x的父节点的颜色染成红色
  20.                 x->parent->color=RED;
  21.                 // 对x的父节点左旋
  22.                 root=root->lrotate(root,x->parent);
  23.                 // 使得w成为新的兄弟节点
  24.                 w=x->parent->right;
  25.  
  26.             }
  27.             // 情况2：w的左右子节点都是黑色，或者w左右都是空节点,因为空节点的颜色本来就是黑色的
  28.             if((w->left==nullptr && w->right==nullptr)
  29.             // 或者w的left是一个黑节点或者w的right节点是一个空节点
  30.              || (w->left && w->left->color==BLACK && w->right==nullptr)
  31.             //  或者w的right是一个黑色节点或者w的left节点是一个空节点
  32.              || ((w->right && w->right->color==BLACK && w->left==nullptr))
  33.              || (
  34.                     // 确保w的左边和右边不是空节点
  35.                     (w->left && w->right) 
  36.                     && 
  37.                     // 确保w的左边和右边都是黑色节点
  38.                     (w->left->color==BLACK && w->right->color==BLACK)
  39.                 )
  40.               )
  41.             {
  42.                 // w的颜色直接染成红色
  43.                 w->color=RED;
  44.                 // x直接上移一个
  45.                 x=x->parent;
  46.             }
  47.             // 情况3：w右孩子是黑色，或者w的右孩子是空的
  48.             else
  49.             if(w->right==nullptr || w->right->color==BLACK)
  50.             {
  51.                 w->left->color=BLACK;
  52.                 w->color=RED;
  53.                 root=root->rrotate(root,w);
  54.                 w=x->parent->right;
  55.  
  56.             }
  57.             // 情况4：结束
  58.             else
  59.             {
  60.                 w->color=x->parent->color;
  61.                 x->parent->color=BLACK;
  62.                 // 判断w的right是否是节点
  63.                 if(w->right)
  64.                 {
  65.                     w->right->color=BLACK;
  66.                 }
  67.                 root=root->lrotate(root,x->parent);
  68.                 x=root;
  69.             }
  70.         }
  71.         else
  72.         {
  73.             // 确定w节点
  74.             RBtree *w=x->parent->left;
  75.             
  76.  
  77.             // 情况1：w是红色节点
  78.             if(w->color==RED)
  79.             {
  80.                 // 将w的颜色染成黑色
  81.                 w->color=BLACK;
  82.                 // x的父节点的颜色染成红色
  83.                 x->parent->color=RED;
  84.                 // 对x的父节点右旋
  85.                 root=root->rrotate(root,x->parent);
  86.                 w=x->parent->left;
  87.  
  88.             }
  89.             // 情况2：w的左右子节点都是黑色，或者w左右都是空节点,因为空节点的颜色本来就是黑色的
  90.             if((w->left==nullptr && w->right==nullptr)
  91.             // 或者w的left是一个黑节点或者w的right节点是一个空节点
  92.              || (w->left && w->left->color==BLACK && w->right==nullptr)
  93.             //  或者w的right是一个黑色节点或者w的left节点是一个黑色节点
  94.              || ((w->right && w->right->color==BLACK && w->left==nullptr))
  95.              || (
  96.                     // 确保w的左边和右边不是空节点
  97.                     (w->left && w->right) 
  98.                     && 
  99.                     // 确保w的左边和右边都是黑色节点
  100.                     (w->left->color==BLACK && w->right->color==BLACK)
  101.                 )
  102.               )
  103.               {
  104.                 // w的颜色直接染成红色
  105.                 w->color=RED;
  106.                 // x直接上移一个
  107.                 x=x->parent;
  108.             }
  109.             // 情况3：w右孩子是黑色，或者w的右孩子是空的
  110.             else
  111.             if(w->left==nullptr || w->left->color==BLACK)
  112.             {
  113.                 w->right->color=BLACK;
  114.                 w->color=RED;
  115.                 root=root->lrotate(root,w);
  116.                 w=x->parent->left;
  117.  
  118.             }
  119.             // 情况4：结束
  120.             else
  121.             {
  122.                 w->color=x->parent->color;
  123.                 x->parent->color=BLACK;
  124.                 // 判断w的left是否是节点
  125.                 if(w->left)
  126.                 {
  127.                     w->left->color=BLACK;
  128.                 }
  129.                 root=root->rrotate(root,x->parent);
  130.                 x=root;
  131.             }
  132.         }
  133.     }
  134.     x->color=BLACK;
  135.     return root;
  136. }
  137.  
  138.  
  139. RBtree *RBtree::rbdelete(int data,RBtree *root)
  140. {
  141.     // 搜索节点要删除的节点
  142.     RBtree *delenode = root->rbsearch(data,root);
  143.  
  144.     // 直到delenode被释放
  145.     while(delenode!=nullptr)
  146.     {
  147.         // 如果删除的是根节点
  148.         if(delenode == root)
  149.         {
  150.             // 如果根节点有两个子节点
  151.             if(delenode->right && delenode->left)
  152.             {
  153.                 // 首先找到delenode的right的最小值
  154.                 RBtree *rmin = delenode->rbmin(delenode->right);
  155.                 // 把rmin的data给到delenode的data
  156.                 delenode->data=rmin->data;
  157.                 // 直接去删除rmin
  158.                 delenode = rmin;
  159.  
  160.                 // // 就直接把delenode的data改成，deletnode的right的最小值
  161.                 // delenode->data=delenode->right->rbmin(delenode->right)->data;
  162.                 // // 去删除delenode
  163.                 // delenode=delenode->right->rbmin(delenode->right);
  164.             }
  165.             else
  166.             // 如果根节点只有一个右节点
  167.             if(delenode->right)
  168.             {
  169.                 // 对delenode 修复
  170.                 root=delete_fixup(root,delenode);
  171.  
  172.                 // 新的根
  173.                 root=delenode->right;
  174.                 root->parent = nullptr;
  175.  
  176.                 //删除根
  177.                 delete delenode; 
  178.                 delenode =nullptr;
  179.             }
  180.             else
  181.             // 根节点只有一个左节点
  182.             if(delenode->left)
  183.             {
  184.                 // 对delenode 修复
  185.                 root=delete_fixup(root,delenode);
  186.  
  187.                 root=delenode->left;
  188.                 root->parent=nullptr;
  189.                 delete delenode;
  190.                 delenode = nullptr;
  191.             }
  192.             else
  193.             // 删除根节点
  194.             {
  195.  
  196.                 root =nullptr;
  197.                 delete delenode;
  198.                 delenode = nullptr;
  199.             }
  200.         }
  201.     // 删除的是除了根节点以外的节点
  202.         else
  203.         {
  204.             // 判断要删除节点的方向
  205.             if(delenode->parent->left==delenode)
  206.             {
  207.                 // 要删除的节点在delenod的父节点的左边
  208.  
  209.                 // 
  210.                 if(delenode->right && delenode->left)
  211.                 {
  212.                     // 情况1：delenode有两个子节点
  213.                     RBtree *rmin = root->rbmin(delenode->right);
  214.                     // 替换内容
  215.                     delenode->data=rmin->data;
  216.                     // 直接删除rmin
  217.                     delenode = rmin;
  218.                     // 将第四种情况转换成第一种情况
  219.                 }
  220.                 else
  221.                 if(delenode->left)
  222.                 {
  223.                     // 对delenode 修复
  224.                     root=delete_fixup(root,delenode);
  225.                     // 情况2：deletnode有一个left节点
  226.  
  227.                     // delenode父节点的左边连接denode的左边
  228.                     delenode->parent->left=delenode->left;
  229.                     // delenode的的左孩子的父节点连接delenode的父节点
  230.                     delenode->left->parent=delenode->parent;
  231.                     // 删除节点
  232.                     delete delenode;
  233.                     delenode = nullptr;
  234.                 }
  235.                 else
  236.                 if(delenode->right)
  237.                 {
  238.                     // 对delenode 修复
  239.                     root=delete_fixup(root,delenode);
  240.                     // 情况3：deletnode有一个right节点
  241.  
  242.                     // delenode父节点的左边连接denode的左边
  243.                     delenode->parent->left=delenode->right;
  244.                     // delenode的的左孩子的父节点连接delenode的父节点
  245.                     delenode->right->parent=delenode->parent;
  246.                     // 删除节点
  247.                     delete delenode;
  248.                     delenode = nullptr;
  249.                 }
  250.                 else
  251.                 {
  252.                     // 对delenode 修复
  253.                     root=delete_fixup(root,delenode);
  254.                     // 情况4：delenode没有子节点
  255.                     delenode->parent->left =nullptr;
  256.                     delete delenode;
  257.                     delenode=nullptr;
  258.                 }
  259.  
  260.  
  261.             }
  262.             else
  263.             {
  264.                 // 要删除的节点在delenod的父节点的右边
  265.                 
  266.  
  267.                 // 
  268.                 if(delenode->right && delenode->left)
  269.                 {
  270.                     // 情况1：delenode有两个子节点
  271.                     RBtree *rmin = root->rbmin(delenode->right);
  272.                     // 替换内容
  273.                     delenode->data=rmin->data;
  274.                     // 直接删除rmin
  275.                     delenode = rmin;
  276.                     // 将第四种情况转换成第一种情况
  277.                 }
  278.                 else
  279.                 if(delenode->left)
  280.                 {
  281.                     // 对delenode 修复
  282.                     root=delete_fixup(root,delenode);
  283.                     // 情况2：deletnode有一个left节点
  284.  
  285.                     // delenode父节点的左边连接denode的左边
  286.                     delenode->parent->right=delenode->left;
  287.                     // delenode的的左孩子的父节点连接delenode的父节点
  288.                     delenode->left->parent=delenode->parent;
  289.                     // 删除节点
  290.                     delete delenode;
  291.                     delenode = nullptr;
  292.                 }
  293.                 else
  294.                 if(delenode->right)
  295.                 {
  296.                     // 对delenode 修复
  297.                     root=delete_fixup(root,delenode);
  298.                     // 情况3：deletnode有一个right节点
  299.  
  300.                     // delenode父节点的左边连接denode的左边
  301.                     delenode->parent->right=delenode->right;
  302.                     // delenode的的左孩子的父节点连接delenode的父节点
  303.                     delenode->right->parent=delenode->parent;
  304.                     // 删除节点
  305.                     delete delenode;
  306.                     delenode = nullptr;
  307.                 }
  308.                 else
  309.                 {
  310.                     // 对delenode 修复
  311.                     root=delete_fixup(root,delenode);
  312.                     // 情况4：delenode没有子节点
  313.                     delenode->parent->right =nullptr;
  314.                     delete delenode;
  315.                     delenode=nullptr;
  316.                 }
  317.             }
  318.         }
  319.     }
  320.     
  321.  
  322.  
  323.  
  324.     return root;
  325. }

寻找节点的最大值

  1. // 查找最大值
  2. #include"RBtree.h"
  3. RBtree *RBtree::rbmax(RBtree *root)
  4. {
  5.     RBtree *x =root;
  6.     RBtree *y;
  7.     while (x)
  8.     {
  9.         y=x;
  10.         x=x->right;
  11.     }
  12.     return y;
  13.     
  14. }

寻找最小值：

  1. // 查找最小值
  2. #include"RBtree.h"
  3. RBtree *RBtree::rbmin(RBtree *root)
  4. {
  5.     RBtree *x =root;
  6.     RBtree *y;
  7.     while (x)
  8.     {
  9.         y=x;
  10.         x=x->left;
  11.     }
  12.     return y;
  13.     
  14. }

红黑树的遍历输出：

  1. #include"RBtree.h"
  2.  
  3.  // 树的遍历
  4. void RBtree::rbprint(RBtree *x)
  5. {
  6.     if(x)
  7.     {
  8.         rbprint(x->left);
  9.         cout<<x->data<<endl;
  10.         rbprint(x->right);
  11.     }
  12. }

红黑树的查找：

  1. #include"RBtree.h"
  2.  
  3. // rb树的查找
  4. RBtree* RBtree::rbsearch(int data,RBtree *root)
  5. {
  6.     RBtree *snode =root;
  7.     while (snode!=nullptr)
  8.     {
  9.         // 如果snode的data比data要小
  10.        if(snode->data<data)
  11.        {
  12.         // 右边走
  13.             snode=snode->right;
  14.        }
  15.     //    如果snode的data比data要大
  16.        else if(snode->data>data)
  17.        {
  18.         // 左边边走
  19.             snode = snode->left;
  20.        }
  21.        else
  22.        {
  23.          // 找到了
  24.             // 返回这个节点的地址
  25.             return snode;
  26.  
  27.        }
  28.  
  29.     }
  30.     return nullptr;
  31.     
  32.     
  33. }

红黑树的左旋：

  1. #include"RBtree.h"
  2. // 左旋转
  3. RBtree *RBtree::lrotate(RBtree *root,RBtree *x)
  4. {
  5.     // 根节点的旋转
  6.     RBtree *y;
  7.     // y在x的右边
  8.     y=x->right;
  9.     // 开始旋转
  10.     if(x == root)
  11.     {
  12.         // 如果x的right不是空节点
  13.         if(x->right)
  14.         {
  15.             // x的右边
  16.             x->right=y->left;
  17.             // 判断y的left是否有节点
  18.             if(y->left)
  19.             {
  20.                 y->left->parent=x;
  21.             }
  22.             // y的左边
  23.             y->left=x;
  24.             x->parent=y;
  25.             // 连接root
  26.             root=y;
  27.             y->parent=nullptr;
  28.         }
  29.  
  30.  
  31.     }
  32.     else
  33.     {
  34.         // 判断x是左孩子还是右孩子
  35.         if(x->parent->left==x)
  36.         {
  37.             // x在父节点的左边
  38.             
  39.             // 改变x父节点到y
  40.             x->parent->left=y;
  41.  
  42.         }
  43.         else
  44.         {
  45.             // x在父节点的右边
  46.             // 改变x父节点到y
  47.             x->parent->right=y;
  48.         }
  49.         y->parent=x->parent;
  50.  
  51.         // x的右边
  52.         x->right=y->left;
  53.         // 判断y是否有left节点
  54.         if(y->left)
  55.         {
  56.             y->left->parent=x;
  57.         }
  58.         
  59.         // y的左边
  60.         y->left=x;
  61.         x->parent=y;
  62.  
  63.  
  64.     }
  65.     return root;
  66. }

红黑树的右旋：

  1. #include"RBtree.h"
  2. // 右旋转
  3. RBtree *RBtree::rrotate(RBtree *root,RBtree *x)
  4. {
  5.     // 根节点的旋转
  6.     RBtree *y;
  7.     // y在x的左边
  8.     y=x->left;
  9.     // 开始旋转
  10.     if(x == root)
  11.     {
  12.         // 如果x的left不是空节点
  13.         if(x->left)
  14.         {
  15.             // x的左边
  16.             x->left=y->right;
  17.             // 判断y的left是否有节点
  18.             if(y->right)
  19.             {
  20.                 y->right->parent=x;
  21.             }
  22.             // y的右边
  23.             y->right=x;
  24.             x->parent=y;
  25.             // 连接root
  26.             root=y;
  27.             y->parent=nullptr;
  28.         }
  29.  
  30.  
  31.     }
  32.     else
  33.     {
  34.         // 判断x是左孩子还是右孩子
  35.         if(x->parent->right==x)
  36.         {
  37.             // x在父节点的右边
  38.             
  39.             // 改变x父节点到y
  40.             x->parent->right=y;
  41.  
  42.         }
  43.         else
  44.         {
  45.             // x在父节点的右边
  46.             // 改变x父节点到y
  47.             x->parent->left=y;
  48.         }
  49.         y->parent=x->parent;
  50.  
  51.         // x的左边
  52.         x->left=y->right;
  53.         // 判断y是否有left节点
  54.         if(y->right)
  55.         {
  56.             y->right->parent=x;
  57.         }
  58.         
  59.         // y的右边
  60.         y->right=x;
  61.         x->parent=y;
  62.  
  63.  
  64.     }
  65.     return root;
  66. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/246254
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号