Chinaunix首页 | 论坛 | 博客
  • 博客访问: 797458
  • 博文数量: 142
  • 博客积分: 3505
  • 博客等级: 中校
  • 技术积分: 1501
  • 用 户 组: 普通用户
  • 注册时间: 2011-07-30 19:30
文章分类

全部博文(142)

文章存档

2012年(33)

2011年(109)

分类: C/C++

2011-08-06 16:24:26

rbtree.c

  1. #include   
  2. #include   
  3. #include   
  4. #include "rbtree.h"  
  5. static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)  
  6. {  
  7.         struct rb_node *right = node->rb_right;  
  8.         struct rb_node *parent = rb_parent(node);  
  9.         if ((node->rb_right = right->rb_left))  
  10.                 rb_set_parent(right->rb_left, node);  
  11.         right->rb_left = node;  
  12.         rb_set_parent(right, parent);  
  13.         if (parent) {  
  14.                 if (node == parent->rb_left)  
  15.                         parent->rb_left = right;  
  16.                 else  
  17.                         parent->rb_right = right;  
  18.         } else  
  19.                 root->rb_node = right;  
  20.         rb_set_parent(node, right);  
  21. }  
  22. static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)  
  23. {  
  24.         struct rb_node *left = node->rb_left;  
  25.         struct rb_node *parent = rb_parent(node);  
  26.         if ((node->rb_left = left->rb_right))  
  27.                 rb_set_parent(left->rb_right, node);  
  28.         left->rb_right = node;  
  29.         rb_set_parent(left, parent);  
  30.         if (parent) {  
  31.                 if (node == parent->rb_right)  
  32.                         parent->rb_right = left;  
  33.                 else  
  34.                         parent->rb_left = left;  
  35.         } else  
  36.                 root->rb_node = left;  
  37.         rb_set_parent(node, left);  
  38. }  
  39. void rb_insert_color(struct rb_node *node, struct rb_root *root)  
  40. {  
  41.     struct rb_node *parent, *gparent;  
  42.     while ((parent = rb_parent(node)) && rb_is_red(parent)) {  
  43.         gparent = rb_parent(parent);  
  44.         if (parent == gparent->rb_left)  { // node is left child of parent  
  45.             {  
  46.                 struct rb_node *uncle = gparent->rb_right;  
  47.                 if (uncle && rb_is_red(uncle)) { // case 1  
  48.                     rb_set_black(uncle);  
  49.                     rb_set_black(parent);  
  50.                     rb_set_red(gparent);  
  51.                     node = gparent;  
  52.                     continue;  
  53.                 }  
  54.             }  
  55.             if (parent->rb_right == node) { // case 2  
  56.                 struct rb_node *tmp;  
  57.                 __rb_rotate_left(parent, root);  
  58.                 tmp = parent;  
  59.                 parent = node;  
  60.                 node = tmp;  
  61.             }  
  62.             // case 3  
  63.             rb_set_black(parent);  
  64.             rb_set_red(gparent);  
  65.             __rb_rotate_right(gparent, root);  
  66.         } else { // node is right child of parent  
  67.             {  
  68.                 struct rb_node *uncle = gparent->rb_left;  
  69.                 if (uncle && rb_is_red(uncle)) { // case 1  
  70.                     rb_set_black(uncle);  
  71.                     rb_set_black(parent);  
  72.                     rb_set_red(gparent);  
  73.                     node = gparent;  
  74.                     continue;  
  75.                 }  
  76.             }  
  77.             if (parent->rb_left == node) { // case 2  
  78.                 struct rb_node *tmp;  
  79.                 __rb_rotate_right(parent, root);  
  80.                 tmp = parent;  
  81.                 parent = node;  
  82.                 node = tmp;  
  83.             }  
  84.             // case 3  
  85.             rb_set_black(parent);  
  86.             rb_set_red(gparent);  
  87.             __rb_rotate_left(gparent, root);  
  88.         }  
  89.     }  
  90.     rb_set_black(root->rb_node);  
  91. }  
  92. static int rb_compare(struct rb_key key1, struct rb_key key2)  
  93. {  
  94.     return (key1.key - key2.key);  
  95. }  
  96. struct rb_node* rb_newnode(struct rb_key *rb_key)  
  97. {  
  98.     struct rb_node *node = (struct rb_node *)malloc(sizeof(struct rb_node));  
  99.     if (node) {  
  100.         node->rb_parent = NULL;  
  101.         node->rb_left = NULL;  
  102.         node->rb_right = NULL;  
  103.         node->rb_color = RB_RED;  
  104.         memcpy(&node->rb_key, rb_key, sizeof(struct rb_key));  
  105.     }  
  106.     return node;  
  107. }  
  108. void rb_insert(struct rb_node *node, struct rb_root *root)  
  109. {  
  110.     struct rb_node *p = root->rb_node;  
  111.     struct rb_node *q = NULL;  
  112.     while (p != NULL) {  
  113.         q = p;  
  114.         if (rb_compare(node->rb_key, p->rb_key) < 0)  
  115.             p = p->rb_left;  
  116.         else  
  117.             p = p->rb_right;  
  118.     }  
  119.     node->rb_parent = q;  
  120.     if (q == NULL) {  
  121.         root->rb_node = node;  
  122.     } else {  
  123.         if (rb_compare(node->rb_key, q->rb_key) < 0)  
  124.             q->rb_left = node;  
  125.         else  
  126.             q->rb_right = node;  
  127.     }  
  128.     rb_insert_color(node, root);  
  129. }  
  130. static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root)  
  131. {  
  132.     struct rb_node *other;  
  133.     while ((!node || rb_is_black(node)) && node != root->rb_node)  
  134.     {  
  135.         if (parent->rb_left == node)  
  136.         {  
  137.             other = parent->rb_right;  
  138.             // case 1  
  139.             if (rb_is_red(other))  
  140.             {  
  141.                 rb_set_black(other);  
  142.                 rb_set_red(parent);  
  143.                 __rb_rotate_left(parent, root);  
  144.                 other = parent->rb_right;  
  145.             }  
  146.             // case 2  
  147.             if ((!other->rb_left || rb_is_black(other->rb_left)) &&  
  148.                 (!other->rb_right || rb_is_black(other->rb_right)))  
  149.             {  
  150.                 rb_set_red(other);  
  151.                 node = parent;  
  152.                 parent = rb_parent(node);  
  153.             }  
  154.             else  
  155.             {  
  156.                 // case 3  
  157.                 if (!other->rb_right || rb_is_black(other->rb_right))  
  158.                 {  
  159.                     struct rb_node *o_left;  
  160.                     if ((o_left = other->rb_left))  
  161.                         rb_set_black(o_left);  
  162.                     rb_set_red(other);  
  163.                     __rb_rotate_right(other, root);  
  164.                     other = parent->rb_right;  
  165.                 }  
  166.                 // case 4  
  167.                 rb_set_color(other, rb_color(parent));  
  168.                 rb_set_black(parent);  
  169.                 if (other->rb_right)  
  170.                     rb_set_black(other->rb_right);  
  171.                 __rb_rotate_left(parent, root);  
  172.                 node = root->rb_node;  
  173.                 break;  
  174.             }  
  175.         }  
  176.         else  
  177.         {  
  178.             other = parent->rb_left;  
  179.             // case 1  
  180.             if (rb_is_red(other))  
  181.             {  
  182.                 rb_set_black(other);  
  183.                 rb_set_red(parent);  
  184.                 __rb_rotate_right(parent, root);  
  185.                 other = parent->rb_left;  
  186.             }  
  187.             // case 2  
  188.             if ((!other->rb_left || rb_is_black(other->rb_left)) &&  
  189.                 (!other->rb_right || rb_is_black(other->rb_right)))  
  190.             {  
  191.                 rb_set_red(other);  
  192.                 node = parent;  
  193.                 parent = rb_parent(node);  
  194.             }  
  195.             else  
  196.             {  
  197.                 // case 3  
  198.                 if (!other->rb_left || rb_is_black(other->rb_left))  
  199.                 {  
  200.                     register struct rb_node *o_right;  
  201.                     if ((o_right = other->rb_right))  
  202.                         rb_set_black(o_right);  
  203.                     rb_set_red(other);  
  204.                     __rb_rotate_left(other, root);  
  205.                     other = parent->rb_left;  
  206.                 }  
  207.                 // case 4  
  208.                 rb_set_color(other, rb_color(parent));  
  209.                 rb_set_black(parent);  
  210.                 if (other->rb_left)  
  211.                     rb_set_black(other->rb_left);  
  212.                 __rb_rotate_right(parent, root);  
  213.                 node = root->rb_node;  
  214.                 break;  
  215.             }  
  216.         }  
  217.     }  
  218.     if (node)  
  219.         rb_set_black(node);  
  220. }  
  221. void rb_erase(struct rb_node *node, struct rb_root *root)  
  222. {  
  223.     struct rb_node *child, *parent;  
  224.     int color;  
  225.     if (!node->rb_left)  
  226.         child = node->rb_right;  
  227.     else if (!node->rb_right)  
  228.         child = node->rb_left;  
  229.     else  
  230.     {  
  231.         struct rb_node *old = node, *left;  
  232.         node = node->rb_right;  
  233.         while ((left = node->rb_left) != NULL)  
  234.             node = left;  
  235.         child = node->rb_right;  
  236.         parent = rb_parent(node);  
  237.         color = rb_color(node);  
  238.         if (child)  
  239.             rb_set_parent(child, parent);  
  240.         if (parent == old) {  
  241.             parent->rb_right = child;  
  242.             parent = node;  
  243.         } else  
  244.             parent->rb_left = child;  
  245.         node->rb_color = old->rb_color;  
  246.         node->rb_parent = old->rb_parent;  
  247.         node->rb_right = old->rb_right;  
  248.         node->rb_left = old->rb_left;  
  249.         if (rb_parent(old))  
  250.         {  
  251.             if (rb_parent(old)->rb_left == old)  
  252.                 rb_parent(old)->rb_left = node;  
  253.             else  
  254.                 rb_parent(old)->rb_right = node;  
  255.         } else  
  256.             root->rb_node = node;  
  257.         rb_set_parent(old->rb_left, node);  
  258.         if (old->rb_right)  
  259.             rb_set_parent(old->rb_right, node);  
  260.         goto color;  
  261.     }  
  262.     parent = rb_parent(node);  
  263.     color = rb_color(node);  
  264.     if (child)  
  265.         rb_set_parent(child, parent);  
  266.     if (parent)  
  267.     {  
  268.         if (parent->rb_left == node)  
  269.             parent->rb_left = child;  
  270.         else  
  271.             parent->rb_right = child;  
  272.     }  
  273.     else  
  274.         root->rb_node = child;  
  275.  color:  
  276.     if (color == RB_BLACK)  
  277.         __rb_erase_color(child, parent, root);  
  278. }  
  279. struct rb_node *rb_first(struct rb_root *root)  
  280. {  
  281.     struct rb_node  *n;  
  282.     n = root->rb_node;  
  283.     if (!n)  
  284.         return NULL;  
  285.     while (n->rb_left)  
  286.         n = n->rb_left;  
  287.     return n;  
  288. }  
  289. struct rb_node *rb_last(struct rb_root *root)  
  290. {  
  291.     struct rb_node  *n;  
  292.     n = root->rb_node;  
  293.     if (!n)  
  294.         return NULL;  
  295.     while (n->rb_right)  
  296.         n = n->rb_right;  
  297.     return n;  
  298. }  
  299. struct rb_node *rb_next(struct rb_node *node)  
  300. {  
  301.     struct rb_node *parent;  
  302.     if (rb_parent(node) == node)  
  303.         return NULL;  
  304.     /* If we have a right-hand child, go down and then left as far 
  305.        as we can. */  
  306.     if (node->rb_right) {  
  307.         node = node->rb_right;   
  308.         while (node->rb_left)  
  309.             node=node->rb_left;  
  310.         return node;  
  311.     }  
  312.     /* No right-hand children.  Everything down and left is 
  313.        smaller than us, so any 'next' node must be in the general 
  314.        direction of our parent. Go up the tree; any time the 
  315.        ancestor is a right-hand child of its parent, keep going 
  316.        up. First time it's a left-hand child of its parent, said 
  317.        parent is our 'next' node. */  
  318.     while ((parent = rb_parent(node)) && node == parent->rb_right)  
  319.         node = parent;  
  320.     return parent;  
  321. }  
  322. struct rb_node *rb_prev(struct rb_node *node)  
  323. {  
  324.     struct rb_node *parent;  
  325.     if (rb_parent(node) == node)  
  326.         return NULL;  
  327.     /* If we have a left-hand child, go down and then right as far 
  328.        as we can. */  
  329.     if (node->rb_left) {  
  330.         node = node->rb_left;   
  331.         while (node->rb_right)  
  332.             node=node->rb_right;  
  333.         return node;  
  334.     }  
  335.     /* No left-hand children. Go up till we find an ancestor which 
  336.        is a right-hand child of its parent */  
  337.     while ((parent = rb_parent(node)) && node == parent->rb_left)  
  338.         node = parent;  
  339.     return parent;  
  340. }  
  341. void rb_replace_node(struct rb_node *victim, struct rb_node *new_node, struct rb_root *root)  
  342. {  
  343.     struct rb_node *parent = rb_parent(victim);  
  344.     /* Set the surrounding nodes to point to the replacement */  
  345.     if (parent) {  
  346.         if (victim == parent->rb_left)  
  347.             parent->rb_left = new_node;  
  348.         else  
  349.             parent->rb_right = new_node;  
  350.     } else {  
  351.         root->rb_node = new_node;  
  352.     }  
  353.     if (victim->rb_left)  
  354.         rb_set_parent(victim->rb_left, new_node);  
  355.     if (victim->rb_right)  
  356.         rb_set_parent(victim->rb_right, new_node);  
  357.     /* Copy the pointers/colour from the victim to the replacement */  
  358.     *new_node = *victim;  
  359. }  
  360. struct rb_node *rb_search(struct rb_root *root, struct rb_key key)  
  361. {  
  362.     struct rb_node *p = root->rb_node;  
  363.     while(p != NULL && rb_compare(p->rb_key, key) != 0) {  
  364.         p = (rb_compare(p->rb_key, key) > 0) ? p->rb_left : p->rb_right;  
  365.     }  
  366.     return p;  
  367. }  
  368. void rb_traverse(struct rb_node *p)  
  369. {  
  370.     if (p) {  
  371.         if (p->rb_left)  
  372.             rb_traverse(p->rb_left);  
  373.         printf(" %d ", p->rb_key.key);  
  374.         if (p->rb_right)  
  375.             rb_traverse(p->rb_right);  
  376.     }  
  377. }  

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