Chinaunix首页 | 论坛 | 博客
  • 博客访问: 475504
  • 博文数量: 59
  • 博客积分: 345
  • 博客等级: 二等列兵
  • 技术积分: 1380
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-18 22:44
个人简介

to be myself

文章分类

全部博文(59)

文章存档

2017年(5)

2013年(47)

2012年(3)

2011年(4)

分类: C/C++

2013-03-02 16:53:39

经典的红黑树代码,插入的新节点为红色。然后再从父节点到根做颜色调整。先给出代码,我再做几张形象的图


点击(此处)折叠或打开

  1. //红黑树的定义

  2. struct rb_node
  3. {
  4.     struct rb_node *rb_parent;
  5.     int rb_color;
  6. #define RB_RED 0
  7. #define RB_BLACK 1
  8.     struct rb_node *rb_right;
  9.     struct rb_node *rb_left;
  10. };

  11. //红黑树的旋转
  12. static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
  13. {
  14.     /*设置right*/
  15.     struct rb_node *right = node->rb_right;
  16.     /*把right的左子树赋给node的右子树*/
  17.     if ((node->rb_right = right->rb_left))
  18.     {
  19.         right->rb_left->rb_parent = node;
  20.     }
  21.     right>rb_left = node;
  22.     /*把node的父亲节点赋给right的父节点,并且判断是否为0*/
  23.     if ((right->rb_parent = node->rb_parent))
  24.     {
  25.         if (node == node->rb_parent->rb_left)
  26.         {
  27.             node->rb_parent->rb_left = right;
  28.         }
  29.         else
  30.         {
  31.             node->rb_parent->rb_right = right;
  32.         }
  33.     }
  34.     else
  35.     {
  36.         root->rb_node = right;
  37.     }
  38.     node->rb_parent = right
  39. }

  40. //红黑树的颜色调整
  41. //红黑树的颜色插入函数主要完成红黑树的颜色调整,从而保持红黑树的原始特性,这些特性是保持红黑树为平衡树的基础
  42. void rb_insert_color(struct rb_node *node, struct rb_root *root)
  43. {
  44.     struct rb_node *parent, *gparent;
  45.     /*检查父节点的颜色是否为红色*/
  46.     while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
  47.     {
  48.         gparent = parent->rb_parent;
  49.         /*判断父节点是否是祖父节点的左节点*/
  50.         if (parent == gparent->rb_left)
  51.         {
  52.             {
  53.                 register struct rb_node *uncle = gparent->rb_right;
  54.                 /*判断uncle节点是否为红色,并相应调整颜色*/
  55.                 if (uncle && uncle->rb_color == RB_RED)
  56.                 {
  57.                     uncle->rb_color = RB_BLACK;
  58.                     parent->rb_color = RB_BLACK;
  59.                     gparent->rb_color = RB_RED;
  60.                     node = gparent;
  61.                     continue;
  62.                 }
  63.             }
  64.             if (parent->rb_right == node)
  65.             {
  66.                 register struct rb_node *tmp;
  67.                 /*左旋*/
  68.                 __rb_rotate_left(parent, root);
  69.                 tmp = parent;
  70.                 parent = node;
  71.                 node = tmp;
  72.             }
  73.             parent->rb_color = RB_BLACK;
  74.             gparent->rb_color = RB_RED;
  75.             /*右旋*/
  76.             __rb_rotate_right(gparent, root);
  77.         }
  78.         else /*else部分与前面对称*/
  79.         {
  80.             {
  81.                 register struct rb_node *uncle = gparent->rb_left;
  82.                 if (uncle && uncle->rb_color == RB_RED)
  83.                 {
  84.                     uncle->rb_color = RB_BLACK;
  85.                     parent->rb_color = RB_BLACK;
  86.                     gparent->rb_color = RB_RED;
  87.                     node = gparent;
  88.                     continue;
  89.                 }
  90.             }
  91.             if (parent->rb_left == node)
  92.             {
  93.                 register struct rb_node *tmp;
  94.                 /*右旋*/
  95.                 __rb_rotate_right(parent, root);
  96.                 tmp = parent;
  97.                 parent = node;
  98.                 node = tmp;
  99.             }
  100.             parent->rb_color = RB_BLACK;
  101.             gparent->rb_color = RB_RED;
  102.             /*左旋*/
  103.             __rb_rotate_left(gparent, root);
  104.         }
  105.     }
  106.     root->rb_node->rb_color = RB_BLACK;
  107. }


2010-11-29 22:41 发表于百度空间,今搬至CU。


阅读(1334) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~