Chinaunix首页 | 论坛 | 博客

mrkeywang的ChinaUnix博客

首页　| 　博文目录　| 　关于我

mrkeywang

  • 博客访问： 12933
  • 博文数量： 16
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 170
  • 用 户 组： 普通用户
  • 注册时间： 2013-05-08 11:44
文章分类

全部博文（16）

文章存档

2014年（16）

我的朋友
最近访客
推荐博文
相关博文
avl2

分类： C/C++

2014-05-22 10:32:00


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdbool.h>
  3. #include <stdlib.h>
  4. /***factor可以和parent用一个元素存放***/
  5. struct avl_node {
  6.         int key;
  7.         int factor;
  8.         struct avl_node *parent;
  9.         struct avl_node *lchild;
  10.         struct avl_node *rchild;
  11. };
  12. struct avl_head {
  13.         struct avl_node *head;
  14. };
  15. #define LH 2
  16. #define RH 1
  17. #define EH 0
  18. #define MASK 3
  19. void init_head(struct avl_head *head)
  20. {
  21.         head->head = NULL;
  22. }
  23. void init_node(struct avl_node *node, int key)
  24. {
  25.         node->key = key;
  26.         node->parent = node->rchild = node->lchild = NULL;
  27. }

  29. struct avl_node *get_parent(struct avl_node *node)
  30. {
  31.         if (node)
  32.                 return node->parent;
  33.         else
  34.                 return NULL;
  35. }
  36. int get_factor(struct avl_node *node)
  37. {
  38.         int factor = 0;
  39.         if (node)
  40.                 factor = node->factor;
  41.         return factor;
  42. }
  43. void set_parent_factor(struct avl_node *now, struct avl_node *parent, int factor)
  44. {
  45.         if (now) {
  46.                 now->parent = parent;
  47.                 if (factor != -1)
  48.                         now->factor = factor;
  49.         }

  51. }
  52. struct avl_node *ll_rotate(struct avl_node *p)
  53. {
  54.         struct avl_node *tmp, *parent;
  55.         int factor;

  57.         parent = get_parent(p);

  59.         tmp = p->lchild;
  60.         p->lchild = tmp->rchild;
  61.         tmp->rchild = p;

  63.         factor = get_factor(tmp);
  64.         set_parent_factor(p->lchild, p, -1);

  66.         if (LH == factor) {
  67.                 set_parent_factor(p, tmp, EH);
  68.                 set_parent_factor(tmp, parent, EH);
  69.         } else {
  70.                 set_parent_factor(p, tmp, LH);
  71.                 set_parent_factor(tmp, parent, RH);
  72.         }

  74.         return tmp;
  75. }
  76. struct avl_node *rr_rotate(struct avl_node *p)
  77. {
  78.         struct avl_node *tmp, *parent;
  79.         int factor;

  81.         parent = get_parent(p);

  83.         tmp = p->rchild;
  84.         p->rchild = tmp->lchild;
  85.         tmp->lchild = p;

  87.         factor = get_factor(tmp);
  88.         set_parent_factor(p->rchild, p, -1);

  90.         if (RH == factor) {
  91.                 set_parent_factor(p, tmp, EH);
  92.                 set_parent_factor(tmp, parent, EH);
  93.         } else {
  94.                 set_parent_factor(p, tmp, RH);
  95.                 set_parent_factor(tmp, parent, LH);
  96.         }
  97.         return tmp;
  98. }

  100. struct avl_node *lr_rotate(struct avl_node *p)
  101. {
  102.         struct avl_node *tmp, *parent, *rc;
  103.         int factor;

  105.         parent = get_parent(p);

  107.         tmp = p->lchild;
  108.         rc = tmp->rchild;
  109.         tmp->rchild = rc->lchild;
  110.         p->lchild = rc->rchild;
  111.         rc->lchild = tmp;
  112.         rc->rchild = p;

  114.         factor = get_factor(rc);
  115.         set_parent_factor(rc, parent, EH);
  116.         set_parent_factor(tmp->rchild, tmp, -1);
  117.         set_parent_factor(p->lchild, p, -1);

  119.         if (EH == factor) {
  120.                 set_parent_factor(tmp, rc, EH);
  121.                 set_parent_factor(p, rc, EH);
  122.         } else if(LH == factor) {
  123.                 set_parent_factor(tmp, rc, EH);
  124.                 set_parent_factor(p, rc, RH);
  125.         } else {
  126.                 set_parent_factor(tmp, rc, LH);
  127.                 set_parent_factor(p, rc, EH);
  128.         }

  130.         return rc;
  131. }
  132. struct avl_node *rl_rotate(struct avl_node *p)
  133. {
  134.         struct avl_node *tmp, *parent, *rc;
  135.         int factor;

  137.         parent = get_parent(p);

  139.         tmp = p->rchild;
  140.         rc = tmp->lchild;
  141.         p->rchild = rc->lchild;
  142.         tmp->lchild = rc->rchild;
  143.         rc->lchild = p;
  144.         rc->rchild = tmp;

  146.         factor = get_factor(rc);
  147.         set_parent_factor(rc, parent, EH);
  148.         set_parent_factor(p->rchild, p, -1);
  149.         set_parent_factor(tmp->lchild, tmp, -1);

  151.         if (EH == factor) {
  152.                 set_parent_factor(tmp, rc, EH);
  153.                 set_parent_factor(p, rc, EH);
  154.         } else if (LH == factor) {
  155.                 set_parent_factor(p, rc, EH);
  156.                 set_parent_factor(tmp, rc, RH);
  157.         } else {
  158.                 set_parent_factor(p, rc, LH);
  159.                 set_parent_factor(tmp, rc, EH);
  160.         }

  162.         return rc;
  163. }
  164. void avl_new_link(struct avl_node *new, struct avl_node *parent, struct avl_node **which)
  165. {
  166.         new->parent = parent;
  167.         new->lchild = new->rchild = NULL;
  168.         new->factor = EH;
  169.         *which = new;
  170. }
  171. void avl_change_link(struct avl_node *new, struct avl_node *old, \
  172.                 struct avl_node *parent, struct avl_head *root)
  173. {
  174.         if (parent) {
  175.                 if (old == parent->lchild)
  176.                         parent->lchild = new;
  177.                 else
  178.                         parent->rchild = new;
  179.         } else
  180.                 root->head = new;
  181. }

  183. void avl_insert(struct avl_head *root, struct avl_node *node)
  184. {
  185.         struct avl_node *parent, *gp;

  187.         parent = get_parent(node);

  189.         while (true) {
  190.                 int factor;
  191.                 struct avl_node *tmp;

  193.                 if (!parent)
  194.                         break;
  195.                 gp = get_parent(parent);
  196.                 factor = get_factor(parent);

  198.                 if (node == parent->lchild) {
  199.                         if (EH == factor) {
  200.                                 set_parent_factor(parent, gp, LH);
  201.                                 node = parent;
  202.                                 parent = gp;
  203.                                 continue;
  204.                         } else if (LH == factor) {
  205.                                 int f;
  206.                                 f = get_factor(node);
  207.                                 if (LH == f)
  208.                                         node = ll_rotate(parent);
  209.                                 else
  210.                                         node = lr_rotate(parent);

  212.                                 avl_change_link(node, parent, gp, root);
  213.                                 break;
  214.                         } else {
  215.                                 set_parent_factor(parent, gp, EH);
  216.                                 break;
  217.                         }
  218.   } else {
  219.                         if (EH == factor) {
  220.                                 set_parent_factor(parent, gp, RH);
  221.                                 node = parent;
  222.                                 parent = gp;
  223.                                 continue;
  224.                         } else if (LH == factor) {
  225.                                 set_parent_factor(parent, gp, EH);
  226.                                 break;
  227.                         } else {
  228.                                 int f;
  229.                                 f = get_factor(node);
  230.                                 if (LH == f)
  231.                                         node = rl_rotate(parent);
  232.                                 else
  233.                                         node = rr_rotate(parent);

  235.                                 avl_change_link(node, parent, gp, root);
  236.                                 break;
  237.                         }
  238.                 }
  239.         }
  240. }
  241. void do_del(struct avl_head *root, struct avl_node *node)
  242. {
  243.         struct avl_node *parent, *gp;
  244.         int factor;

  246.         parent = get_parent(node);
  247.         while(true) {
  248.                 if (!parent)
  249.                         break;
  250.                 gp = get_parent(parent);
  251.                 factor = get_factor(parent);

  253.                 if (node == parent->lchild) {
  254.                         if (EH == factor) {
  255.                                 set_parent_factor(parent, gp, RH);
  256.                                 break;
  257.                         } else if (LH == factor) {
  258.                                 set_parent_factor(parent, gp, EH);
  259.                                 node = parent;
  260.                                 parent = gp;
  261.                                 continue;
  262.                         } else {
  263.                                 int f;
  264.                                 f = get_factor(parent->rchild);
  265.                                 if (RH == f) {
  266.                                         node = rr_rotate(parent);
  267.                                         avl_change_link(node, parent, gp, root);
  268.                                         parent = gp;
  269.                                         continue;
  270.                                 } else if (EH == f) {
  271.                                         node = rr_rotate(parent);
  272.                                         avl_change_link(node, parent, gp, root);
  273.                                         break;
  274.                                 } else {
  275.                                         node = rl_rotate(parent);
  276.                                         avl_change_link(node, parent, gp, root);
  277.                                         parent = gp;
  278.                                         continue;
  279.                                 }
  280.                         }
  281.   } else {
  282.                         if (EH == factor) {
  283.                                 set_parent_factor(parent, gp, LH);
  284.                                 break;
  285.                         } else if (RH == factor) {
  286.                                 set_parent_factor(parent, gp, EH);
  287.                                 node = parent;
  288.                                 parent = gp;
  289.                                 continue;
  290.                         } else {
  291.                                 int f;
  292.                                 f = get_factor(parent->lchild);
  293.                                 if (LH == f) {
  294.                                         node = ll_rotate(parent);
  295.                                         avl_change_link(node, parent, gp, root);
  296.                                         parent = gp;
  297.                                         continue;
  298.                                 } else if (EH == f) {
  299.                                         node == ll_rotate(parent);
  300.                                         avl_change_link(node, parent, gp, root);
  301.                                         break;
  302.                                 } else {
  303.                                         node = lr_rotate(parent);
  304.                                         avl_change_link(node, parent, gp, root);
  305.                                         parent = gp;
  306.                                         continue;
  307.                                 }
  308.                         }
  309.                 }
  310.         }
  311. }
  312. void avl_del(struct avl_head *root, struct avl_node *node)
  313. {
  314.         struct avl_node *victim, *parent, *child;
  315.         struct avl_node tmp;

  317.         victim = node;
  318.         if (node->lchild && node->rchild) {
  319.                 victim = node->lchild;
  320.                 while (victim->rchild)
  321.                         victim = victim->rchild;
  322.         }

  324.         if (victim->lchild)
  325.                 child = victim->lchild;
  326.         else
  327.                 child = victim->rchild;

  329.         do_del(root, victim);

  331.         parent = get_parent(victim);
  332.         set_parent_factor(child, parent, -1);
  333.         avl_change_link(child, victim, parent, root);

  335.         if (victim != node) {
  336.                 *victim = *node;
  337.                 parent = get_parent(victim);
  338.                 set_parent_factor(victim->lchild, victim, -1);
  339.                 set_parent_factor(victim->rchild, victim, -1);
  340.                 avl_change_link(victim, node, parent, root);
  341.         }
  342. }
  343. void insert(struct avl_head *root, int key)
  344. {
  345.         struct avl_node *parent, **which, *node;


  348.         which = &root->head;
  349.         parent = *which;
  350.         while(*which) {
  351.                 parent = *which;
  352.                 if (key < (*which)->key)
  353.                         which = &(*which)->lchild;
  354.                 else if (key > (*which)->key)
  355.                         which = &(*which)->rchild;
  356.                 else
  357.                         break;
  358.         }
  359.         if (*which)
  360.                 fprintf(stderr, "insert: key been bound\n");
  361.         else {
  362.                 node = malloc(sizeof(struct avl_node));
  363.                 init_node(node, key);
  364.                 avl_new_link(node, parent, which);
  365.                 avl_insert(root, node);
  366.         }
  367. }
  368. void del(struct avl_head *root, int key)
  369. {
  370.         struct avl_node *parent, **which, *node;

  372.         node = root->head;

  374.         while (node) {
  375.                 if (key < node->key)
  376.                         node = node->lchild;
  377.                 else if (key > node->key)
  378.                         node = node->rchild;
  379.                 else
  380.                         break;
  381.         }

  383.         if (node == NULL) {
  384.                 fprintf(stderr, "this key is not bound\n");
  385.         } else {
  386.                 avl_del(root, node);
  387.                 free(node);
  388.         }
  389. }

阅读(204) | 评论(0) | 转发(0) |
0

上一篇：treap

下一篇：置换选择

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6