红黑树(RBTree)

750阅读　0评论2013-08-23　A_Nemo_A
分类：C/C++

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


点击(此处)折叠或打开

  1. //红黑树的定义

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

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

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


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


上一篇：高精度算法
下一篇：嵌入式Linux之我行——S3C2440上LCD驱动(FrameBuffer)实例开发讲解（二）