文档章节

二叉树之红黑树的实现-插入和删除(三)

y
 yky20190625
发布于 07/27 13:58
字数 3435
阅读 3
收藏 0

  #include <stdio.h>
  #include <stdlib.h>
  //////////////////////////////////////////////////////////////////////
  
  #define RED        0    // 红色节点
  #define BLACK    1    // 黑色节点
  
  typedef int Type;
  
  // 红黑树的节点
  typedef struct RBTreeNode{
     unsigned char color;        // 颜色(RED 或 BLACK)
     Type   key;                    // 关键字(键值)
     struct RBTreeNode *left;    // 左孩子
     struct RBTreeNode *right;    // 右孩子
     struct RBTreeNode *parent;    // 父结点
  }Node, *RBTree;
 // 红黑树的根
  typedef struct rb_root{
     Node *node;
  }RBRoot;
 
 RBRoot* create_rbtree();
 Node* rb_parent(Node* n);
 Node* create_node(Type key, Node *parent, Node *left, Node* right);
 void left_rotate(RBRoot *root, Node *x);
 void right_rotate(RBRoot *root, Node *y);
 static void insert_fixup(RBRoot *root, Node *node);
 int  insert(RBRoot *root, Node *node);
  static void inorder(Node *root);
  static Node* rbtree_search(RBRoot* root, Type key);
  void rb_delete_fixup(RBRoot *root, Node *parent,Node *node);
  void rb_delete(RBRoot *root, Node *del);
    
  //#define rb_is_black(r)  ((r)->color==BLACK)
  //#define rb_set_black(r)  do { (r)->color = BLACK; } while (0)
  //#define rb_set_red(r)  do { (r)->color = RED; } while (0)
  #define rb_set_parent(r,p)  do { (r)->parent = (p); } while (0)
  #define rb_set_color(r,c)  do { (r)->color = (c); } while (0)
  inline  bool rb_is_red(Node *n) { if(n)  return n->color==RED ; else return  false; }
  inline  bool rb_is_black(Node*n) {  return n->color==BLACK; }
  inline  void rb_set_black(Node*n) {   n->color=BLACK; }
  inline  void rb_set_red(Node*n) {   n->color=RED; } 
  bool rb_is_red(Node *node);
// #endif
//=========================================================================================================================
int main()
{
    RBRoot* root =create_rbtree();
    Node* n= create_node(3, NULL, NULL, NULL);
    
    int  a[100]={13,45,23,7,8,9,11,14,16,18, 29, 33, 31, 6, 3, 2, 42};
    for( int i=0;i<10;i++)
    {
        n= create_node(a[i], NULL, NULL, NULL);
        insert(root,n);
    }
    inorder(root->node);
    printf("\n");
    Node* del=rbtree_search(root,23);
    if(del)
        rb_delete(root,del);
    inorder(root->node);
    
    return 0;
}

static void inorder(Node *root)
  {
      if(root != NULL)
      {
          inorder(root->left);
          printf("%d ", root->key);
          inorder(root->right);
      }
  }
/*
  * 创建红黑树,返回"红黑树的根"!
    */
  RBRoot* create_rbtree()
  {
      RBRoot *root = (RBRoot *)malloc(sizeof(RBRoot));
      root->node = NULL;
      return root;
  }
  
  Node* create_node(Type key, Node *parent, Node *left, Node* right)
 {
     Node* p;
 
    if ((p = (Node *)malloc(sizeof(Node))) == NULL)
         return NULL;
     p->key = key;
     p->left = left;
     p->right = right;
     p->parent = parent;
     p->color = BLACK; // 默认为黑色
 
     return p;
 }
 /* 
227  * 对红黑树的节点(x)进行左旋转
228  *
229  * 左旋示意图(对节点x进行左旋): 右子变父,父变左子 
230  *      px                              px
231  *     /                               /
232  *    x                               y                
233  *   /  \      --(左旋)-->           / \                #
234  *  lx   y                          x  ry     
235  *     /   \                       /  \
236  *    ly   ry                     lx  ly  
237  *
238  *
239  */
 void left_rotate(RBRoot *root, Node *x)
 {
     // 设置x的右孩子为y
     Node *y = x->right;
 
     // 将 “y的左孩子” 设为 “x的右孩子”;
     // 如果y的左孩子非空,将 “x” 设为 “y的左孩子的父亲”
     x->right = y->left;
     if (y->left != NULL)
         y->left->parent = x;
 
     // 将 “x的父亲” 设为 “y的父亲”
     y->parent = x->parent;
 
     if (x->parent == NULL)
     {
         root->node = y;            // 如果 “x的父亲” 是空节点,则将y设为根节点
     }
     else
     {
         if (x->parent->left == x)
             x->parent->left = y;    // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
         else
             x->parent->right = y;    // 如果 x是它父节点的右孩子,则将y设为“x的父节点的右孩子”
     }
     
     // 将 “x” 设为 “y的左孩子”
     y->left = x;
     // 将 “x的父节点” 设为 “y”
     x->parent = y;
 }
 
/* 
274  * 对红黑树的节点(y)进行右旋转
275  *
276  * 右旋示意图(对节点y进行左旋):
277  *            py                               py
278  *           /                                /
279  *          y                                x                  
280  *         /  \      --(右旋)-->            /  \                     #
281  *        x   ry                           lx   y  
282  *       / \                                   / \                   #
283  *      lx  rx                                rx  ry
284  * 
285  */
  void right_rotate(RBRoot *root, Node *y)
 {
     // 设置x是当前节点的左孩子。
     Node *x = y->left;
 
     // 将 “x的右孩子” 设为 “y的左孩子”;
     // 如果"x的右孩子"不为空的话,将 “y” 设为 “x的右孩子的父亲”
     y->left = x->right;
     if (x->right != NULL)
         x->right->parent = y;
     // 将 “y的父亲” 设为 “x的父亲”
     x->parent = y->parent;
     if (y->parent == NULL) 
     {
         root->node = x;            // 如果 “y的父亲” 是空节点,则将x设为根节点
     }
     else
     {
         if (y == y->parent->right)
             y->parent->right = x;    // 如果 y是它父节点的右孩子,则将x设为“y的父节点的右孩子”
         else
             y->parent->left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
     }
 
     // 将 “y” 设为 “x的右孩子”
     x->right = y;
       // 将 “y的父节点” 设为 “x”
     y->parent = x;
 }
 
 /*
321  * 红黑树插入修正函数
322  *
326  * 参数说明:
327  *     root 红黑树的根
328  *     node 插入的结点        
329  */
 static void insert_fixup(RBRoot *root, Node *node)
 {
    Node *parent, *gparent;
    //由于插入结点都是红色  如果插入结点的父结点是黑色,不影响红黑树平衡,无需调整 ,
    //因此只需考虑父结点为红色的情况 
    // 若“父节点存在,并且父节点的颜色是红色”
    while ((parent = node->parent) && rb_is_red(parent))
    {
             gparent = parent->parent;   //因为父结点是红色,祖父必然是黑色 
             
             //情况1:叔叔结点存在且是红色  
             Node *uncle = gparent->left==parent? gparent->right:gparent->left;//父是左子,则叔是右子,反之 
             if (uncle && rb_is_red(uncle))
             {
                        rb_set_black(uncle);   //父辈都翻黑 
                        rb_set_black(parent);  //父辈都翻黑 
                        rb_set_red(gparent);   //祖辈翻红 
                        node = gparent;        //由于祖辈翻红, 会与祖辈的上辈违反红黑树的要求,因此 把祖辈设为当前结点,继续调整 
                        continue;
             }
             //情况2: 以下是叔叔不存在或者为黑色的情况 其实 叔叔只能不存在,不可能为黑色 
             
             //情况2.1  若“父节点”是“祖父节点的左孩子”
             if (parent == gparent->left)
             {
                    
                    //情况2.1.1  插入结点是父节点的右孩子
                    if (parent->right == node)
                     {
                         left_rotate(root,parent);   //先把父左旋  变成 左-左使之与2.1.2称为一样的形态  调整还没有完成, 到2.1.2进一步调整 
                        Node *tmp= parent;         //左旋后,父子地位互换, 要把父设为当前结点node,而node变为父,才能在2.1.2中得到进一步处理 
                        parent = node; 
                        node = tmp;
                        
                     }
                     //情况2.1.2  插入结点是父节点的左孩子   左-左 
                     {
                         rb_set_black(parent);  //父亲变黑 
                         rb_set_red(gparent);   //祖父变红 
                         right_rotate(root, gparent); //把祖父右旋转  
                    }
              }
             //情况2.2 若“父节点”是“祖父节点的右孩子”
             else 
             {
                     //情况2.2.1  插入结点是父节点的左孩子
                    if (parent->left == node)
                     {
                         right_rotate(root,parent);   //先把父右旋  变 右-左    为右-右 使之与2.2.2一样的形态,到2.2.2中进一步调整 
                        Node *tmp= parent;         //右旋后,父子地位互换, 要把父设为当前结点node,而node变为父
                        parent = node; 
                        node = tmp;  
                     }
                     //情况2.2.2  插入结点是父节点的右孩子
                     {
                         
                        rb_set_black(parent);  //父亲变黑 
                         rb_set_red(gparent);   //祖父变红 
                         left_rotate(root, gparent); //把祖父左旋转 
                   }
             }
             
    }
             
    // 将根节点设为黑色
    rb_set_black(root->node);
 }

 /*
407  * 添加节点:将节点(node)插入到红黑树中
408  *
409  * 参数说明:
410  *     root 红黑树的根
411  *     node 插入的结点        
412  */
 int  insert(RBRoot *root, Node *node)
 {
     Node *y = NULL;
     Node *x = root->node;  
 
     // 1. 将红黑树当作一颗二叉查找树,将节点添加到二叉查找树中。
     while (x != NULL)         //y迭代当前结点,x迭代当前结点的左右子结点 
     {
         y = x;
         if (node->key < x->key)
             x = x->left;
         else if (node->key > x->key) 
             x = x->right;
         else                        //找到相等的key了 
             return -1;    //key值已经存在 插入失败  
     }
     node->parent = y;
     if (y != NULL)
     {
         if (node->key < y->key)
             y->left = node;                // 情况2:若“node所包含的值” < “y所包含的值”,则将node设为“y的左孩子”
         else 
             y->right = node;            // 情况3:(“node所包含的值” >= “y所包含的值”)将node设为“y的右孩子”
         
     }
     else
     {
         root->node = node;                // 情况1:若y是空节点,则将node设为根
     }
     // 2. 设置插入节点的颜色为红色
     node->color = RED;
     // 3. 将它重新修正为一颗红黑树
     insert_fixup(root, node);
     return  1;
 }
 
 void rb_delete(RBRoot *root, Node *del)
 {
     Node *child=NULL, *parent;
     int color;
     
     // 先处理被删除节点的"左右孩子都不为空"的情况,找到它的替代点, 再把替代点变为真正要删除的结点 
     if ( (del->left!=NULL) && (del->right!=NULL) ) 
     {
             //搜寻替代结点 
            Node *replace = del;    
            replace = replace->right;   
            while (replace->left != NULL)
                    replace = replace->left;
            
            // (1)用替代结点替换删除结点   
            if(del->parent)
            {
                if(del->parent->left==del) del->parent->left=replace;  
                else                       del->parent->right=replace;
            }
            else  root->node = replace;
            //记录替代节点的父亲和孩子  
            parent =replace->parent;
            child = replace->right;   //替代结点只有右子 
            color = replace->color;
                            
            //替代结点脱离原来的关系     
            if(parent==del)      // 如果替代结点的父亲恰好就是删除结点
            {
                parent= replace;   // 此时关系是    del->右-> replace->右->child  所以 child无需和替代结点R脱离 ,替代点就是child的父亲
            }
            else{
                 if(child ) child->parent = parent;
                 parent->left  =child;
                 // (2)用替换结点变为删除结点//    // 放到这里是因为避免出现删除结点是替代结点的父亲的情况,从而导致替代结点的右子结点指向自己
                 replace->right = del->right;     
                 del->right->parent    = replace; 
            }
            // 经过(1)(2)(3)三步才完成替换了删除结点 
            //替代删除结点为替代结点一共有6个操作,分别是设置左子结点(2个),右子结点(2个),父亲结点(2个)
            // (3) 用替换结点变为删除结点     
            replace->parent = del->parent;
            replace->color = del->color;
            replace->left = del->left;
            del->left->parent = replace;
            
           //最后判断 如果有孩子, 则孩子必为红色   设为黑色, 替代被删的黑点 
            if(child)
                child->color=BLACK;
            if(color==BLACK && !child)   //黑结点且无孩子,则需要修正  
                rb_delete_fixup(root, parent,child) ;   
        
     }
     //剩下都是被删点为单子树的情况
     //情况 A)  被删除结点是红色  则被删除结点的左或着右孩子必为空  直接删除,不需调整 
     //情况 B) 被删除结点为黑  被删除的黑结点如有孩子, 则孩子必是红色  删除后  孩子变黑既可,后续无需调整 
     //情况 C) 被删除的黑结点无孩子 ,要修正 
     else    
     {
              if(del->right)
                    child =del->right ;
             else child = del->left;
              
             parent=del->parent;
              color = del->color;
              
              //删除点从树中脱离 
             if(child)  {
                 child->parent =parent;
                 child->color  =BLACK;   //被删除的黑结点如有孩子, 则孩子必是红色, 删去黑结点, 让孩子变黑达到平衡 
             }   
             
             if(parent)  {
                  if(parent->left==del)  parent->left = child;
                  else  parent->right = child;
             }  
             else  root->node =child;
             
             if(color==BLACK && child==NULL)  //黑结点且无孩子,则需要修正 
                 rb_delete_fixup(root, parent,child) ;     
     }
     
     free(del);
     rb_set_black(root->node);
 }
 
 
 /*
501  * 红黑树删除修正函数
502  *
503  * 在从红黑树中删除插入节点之后(红黑树失去平衡),再调用该函数;
504  * 目的是将它重新塑造成一颗红黑树。
505  *
506  * 参数说明:
507  *     root 红黑树的根
508  *     node 待修正的节点
509  */
 inline void rb_delete_fixup(RBRoot *root, Node *parent,Node *node) 
 {
     Node* brother;  //被删除黑结点必有兄弟,否则以parent为根的子树不能平衡 
     while(  ( !node || rb_is_black(node) ) && node!=root->node )
     {
          /**
             * 分为四种情况,分别是
             * 1.兄弟结点是红色
             * 2.兄弟结点是黑色,其子结点也是黑色
             * 3.兄弟结点是黑色,其左子结点为红色,右子结点任意颜色 
             * 4.兄弟结点是黑色,其左子结点任意颜色,右子结点为红色
             */

          
          //分两大情况, 1 删除结点是父亲左孩子, 2 删除结点是父亲右孩子 
        if (parent->left == node)
        {
            brother= parent->right;  //兄弟是右 
            if (rb_is_red(brother) )  //1 若兄弟是红色, 为保证平衡,则兄弟必有两个黑子树 
            {
                brother->color=BLACK;  
                parent->color =RED;
                left_rotate(root, parent);    //旋转后,仍不平衡,此时,删除结点的兄弟变了,是原兄弟的左黑子树 ,因此兄弟要重设 
                brother = parent->right;    //重设兄弟, 现在的兄弟是黑色,转到下面黑兄弟的情况执行 
            }
            //以下都是黑兄弟的情况  根据平衡条件 黑兄弟只能有红孩子.  分有左红孩子, 有右红孩子,没孩子三种情况 
            if( brother->left && rb_is_red(brother->left) )  //3 兄弟有左红孩子 
            {
                         brother->left->color = parent->color; // brother的左红孩子变为父亲的颜色 
                         rb_set_black(parent);   //父亲变黑 
                         right_rotate(root, brother);  //兄弟右旋转, 左红孩子上位 
                         left_rotate(root,parent); //父亲左旋,补充左边的黑子数目 
                         break;
                         
            }
            else if(brother->right && rb_is_red(brother->right) ) //4 兄弟有右红孩子 
            {
                         brother->color = parent->color; // brother变为父亲的颜色 
                         rb_set_black(brother->right);    //兄弟右红孩子变黑 
                         rb_set_black(parent);   //父亲变黑
                         left_rotate(root,parent); //父亲左旋,补充左边的黑子数目
                         break;
            }
            else  // 2  黑兄弟只有黑孩子,或者没孩子 
            {
                        //又分两种情况  父为红, 父为黑 
                if( rb_is_red(parent) ) // 父为红
                {
                            rb_set_black(parent);   //父亲变黑  补充删去的黑结点 
                            rb_set_red(brother);    //为保证平衡, 兄弟变为红
                            break;
                }
                else // 父为黑 
                {
                            rb_set_red(brother);    //为保证平衡, 兄弟只能变为红
                            node =parent;          //父亲作为子树比其他树要少一个黑点了,因此要把 父亲当作新的待平衡点, 继续循环 上溯继续平衡 
                }
            } 
        }
        //2大情况 删除结点是父亲右孩子 
        else
        {
             brother= parent->left;   //兄弟是左 
            if (rb_is_red(brother) )  //1 若兄弟是红色, 为保证平衡,则兄弟必有两个黑孩子 
            {
                rb_set_black(brother);
                rb_set_red(parent);
                right_rotate(root, parent);    //旋转后,仍不平衡,此时,删除结点的兄弟变了,是黑兄弟 ,因此兄弟要重设 
                brother = parent->left;    //重设兄弟, 转到下面兄弟为黑兄弟的情况执行 
            }
            //以下都是黑兄弟的情况  根据平衡条件 黑兄弟只能有红孩子.  分有左红孩子, 有右红孩子,没孩子三种情况 
                
            if( brother->left && rb_is_red(brother->left) )  //兄弟有左红孩子 
            {
                         brother->color = parent->color; // brother变为父亲的颜色 
                         rb_set_black(brother->left);    //兄弟左红孩子变黑 
                         rb_set_black(parent);   //父亲变黑
                         right_rotate(root,parent); //父亲右旋,补充右边的黑子数目
                         break;
                         
                         
            }
            else if( brother->right && rb_is_red(brother->right)) //兄弟有右红孩子 
            {
                        brother->right->color = parent->color; // brother的右红孩子变为父亲的颜色 
                        rb_set_black(parent);   //父亲变黑 
                        left_rotate(root, brother);  //兄弟左旋转, 右红孩子上位 
                        right_rotate(root,parent); //父亲右旋,补充右边的黑子数目 
                        break;      
            }
            else  //黑兄弟没孩子的情况
            {
                //又分两种情况  父为红, 父为黑 
                if( rb_is_red(parent) ) // 父为红
                {
                            rb_set_black(parent);   //父亲变黑  补充删去的黑结点 
                            rb_set_red(brother);    //为保证平衡, 兄弟变为红
                            break;
                }
                else // 父为黑 
                {
                            rb_set_red(brother);    //为保证平衡, 兄弟只能变为红
                            node =parent;          //父亲作为子树比其他树要少一个黑点了,因此要把 父亲当作新的待平衡点,上溯继续平衡
                }
            } 
        }
        
         
     }  //循环结束 
     
          
     //if (node)
        // rb_set_black(node);
 }
 Node* rbtree_search(RBRoot* root, Type key)
{
    Node* x=root->node;
     while ((x!=NULL) && (x->key!=key))
     {
         if (key < x->key)
             x = x->left;
         else
             x = x->right;
     }
 
     return x;
 }    

© 著作权归作者所有

y
粉丝 0
博文 10
码字总数 13594
作品 0
荆州
私信 提问
树型结构之红黑树

一.红黑树的介绍 红黑树是一种自平衡二叉树,红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作...

大覇
2016/03/28
174
0
数据结构与算法之10(AVL自平衡二叉树与RB红黑树)

本节继续总结二叉树的变种,上节里的哈夫曼树是一种独特的二叉树,用于编解码会比较有效。这里的两种树都是BST二叉搜索树的加强版。 》BST二叉搜索树的弱点 我们之前也提到了,当插入序列是有...

kkae8643150
2017/12/01
0
0
关于红黑树(R-B tree)原理,看这篇如何

学过数据数据结构都知道二叉树的概念,而又有多种比较常见的二叉树类型,比如完全二叉树、满二叉树、二叉搜索树、均衡二叉树、完美二叉树等;今天我们要说的红黑树就是就是一颗非严格均衡的二...

工匠初心
07/17
0
0
堆,AVL树,红黑树以及优先级队列

声明:本文完全没有定量分析,需要定量分析的,请随便查阅一本数据结构的书籍或网页。 二叉堆:拥有删除最大(小)权值节点以及插入任意节点操作,是一颗完全二叉树,其完全性由插入和删除动...

晨曦之光
2012/04/10
564
0
植树节,程序员要爬哪些“树”?

作者 | 程序猿小吴、进击的Hello_World 转载自五分钟学算法(ID: CXYxiaowu) 公历 3 月 12 日是一年一度的植树节。旨在宣传保护森林,并动员群众参加植树造林活动。说到树,程序猿们肯定不陌...

AI科技大本营
03/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分享一个 pycharm 专业版的永久使用方法

刚开始接触Python,首先要解决的就是Python开发环境的搭建。 目前比较好用的Python开发工具是PyCharm,他有社区办和专业版两个版本,但是社区版支持有限,我们既然想好好学python,那肯定得用...

上海小胖
38分钟前
6
0
Spring Cloud Alibaba 实战(二) - 关于Spring Boot你不可不知道的实情

0 相关源码 1 什么是Spring Boot 一个快速开发的脚手架 作用 快速创建独立的、生产级的基于Spring的应用程序 特性 无需部署WAR文件 提供starter简化配置 尽可能自动配置Spring以及第三方库 ...

JavaEdge
今天
7
0
TensorFlow 机器学习秘籍中文第二版(初稿)

TensorFlow 入门 介绍 TensorFlow 如何工作 声明变量和张量 使用占位符和变量 使用矩阵 声明操作符 实现激活函数 使用数据源 其他资源 TensorFlow 的方式 介绍 计算图中的操作 对嵌套操作分层...

ApacheCN_飞龙
今天
8
0
五、Java设计模式之迪米特原则

定义:一个对象应该对其他对象保持最小的了解,又叫最小知道原则 尽量降低类与类之间的耦合 优点:降低类之间的耦合 强调只和朋友交流,不和陌生人说话 朋友:出现在成员变量、方法的输入、输...

东风破2019
昨天
25
0
jvm虚拟机结构

1:jvm可操作数据类型分为原始类型和引用类型,因此存在原始值和引用值被应用在赋值,参数,返回和运算操作中,jvm希望在运行时 明确变量的类型,即编译器编译成class文件需要对变量进行类型...

xpp_ba
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部