设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › 数据结构与算法 › 【纯C实现】【非递归】AVL树删除, 插入等操作
返回列表 发新帖
查看: 3590|回复: 6

[技术交流] 【纯C实现】【非递归】AVL树删除, 插入等操作

[复制链接]
柠“萌”圆
发表于 2015-2-15 13:21:55 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
纯C实现了AVL树, 非递归算法
实现了简单的范型, 这个AVL树是当作字典(即保持(key, value)对)用的(类似C++标准库的std::map), 也就是用AVL树实现了映射
测试插入4000000个数据(别数有几个0了, 是四百万), 生成的(key, value)对是随机的(但是可以保证4000000个数据中每一对数据的key都是唯一的), 插入4000000个数据后树的高度(在我测试过的情况中)为25左右
然后删除2000000个数据, 查找2000000个数据
所花时间大概在9秒到10秒之间(我看的手表计时......没有用time.h中的函数计时, 不是很准, 大家可以自己测试)
下面贴完整代码吧, 注释应该是够了, 可能没有太注意排版, 100多行代码全部塞一个函数里......凑合着看......
实现整个AVL树用了446行代码, 删除算法很多书都没有(我看的这本书有, 不过整个AVL树书上只是讲了思路, 没有代码), 连小甲鱼的视频里都没有哦, 而且非递归, 应该挺难得的吧......
贴代码:
注意stdbool.h VS貌似没有(微软貌似从来没有对C/C++标准很重视......stdbool.h是C99的内容), bool类型要自己定义
  1. #ifndef AVL_TREE_H
  2. #define AVL_TREE_H

  4. #include <stddef.h>
  5. #include <stdbool.h>

  7. struct AVLTreeHandle;
  8. typedef struct AVLTreeHandle * AVLTree;

  10. AVLTree CreateAVLTree(int (*cmp_key)(const void *, const void *),  
  11.                       size_t key_width, size_t value_width);
  12. bool InsertAVLTree(AVLTree avl, const void *key, const void *value);
  13. bool DeleteAVLTree(AVLTree avl, const void *key, void *value);
  14. void * SearchAVLTree(AVLTree avl, const void *key);
  15. bool IsAVLTreeEmpty(AVLTree avl);
  16. void ClearAVLTree(AVLTree avl);
  17. void DestroyAVLTree(AVLTree avl);

  19. #endif
复制代码

stdint.h貌似在VC10(也就是VS2010)和之前版本都没有, int8_t需要自己定义
  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include <stdint.h>
  4. #include <assert.h>
  5. #include "avl_tree.h"

  7. #define NONE  -1
  8. #define LEFT  0
  9. #define RIGHT 1
  10. #define LL    2
  11. #define LR    3
  12. #define RL    4
  13. #define RR    5

  15. typedef struct AVLTreeNode {
  16.         int8_t bf;
  17.         void *key;
  18.         void *value;
  19.         struct AVLTreeNode *parent;
  20.         struct AVLTreeNode *left_child;
  21.         struct AVLTreeNode *right_child;
  22. } AVLTreeNode;

  24. struct AVLTreeHandle {
  25.         int (*cmp_key)(const void *, const void *);
  26.         size_t key_width,
  27.                value_width;
  28.         AVLTreeNode *root;
  29. };

  31. static void LLRotate(AVLTreeNode *x);
  32. static void LRRotate(AVLTreeNode *x);
  33. static void RLRotate(AVLTreeNode *x);
  34. static void RRRotate(AVLTreeNode *x);
  35. static void DestroyTree(AVLTreeNode *root);
  36. static AVLTreeNode * FindPrev(AVLTreeNode *root);

  38. AVLTree CreateAVLTree(int (*cmp_key)(const void *, const void *),
  39.                       size_t key_width, size_t value_width)
  40. {
  41.         struct AVLTreeHandle *new = malloc(sizeof (struct AVLTreeHandle));
  42.         assert(new);

  44.         new->cmp_key = cmp_key;
  45.         new->key_width = key_width;
  46.         new->value_width = value_width;
  47.         new->root = NULL;
  48.         return new;
  49. }

  51. bool InsertAVLTree(AVLTree avl, const void *key, const void *value)
  52. {
  53.         AVLTreeNode *p = avl->root;
  54.         AVLTreeNode *pp = NULL;
  55.         AVLTreeNode *x = NULL;
  56.         int non_balanced_type, cmp_result;
  57.         /*********************************************
  58.          * x是在插入的路径上, 在插入前最后一个bf值为 *
  59.          * 1或-1的节点                               *
  60.          *********************************************/

  62.         while (p != NULL && (cmp_result = avl->cmp_key(key, p->key)) != 0) {
  63.                 pp = p;

  65.                 if (pp->bf == 1 || pp->bf == -1) {
  66.                         x = pp;
  67.                         non_balanced_type = NONE;
  68.                 }

  70.                 if (cmp_result < 0) {
  71.                         p = p->left_child;
  72.                         if (x != NULL) {
  73.                                 /* 根据插入路径确定不平衡类型 */
  74.                                 switch (non_balanced_type) {
  75.                                         case NONE:  non_balanced_type = LEFT; break;
  76.                                         case LEFT:  non_balanced_type = LL;   break;
  77.                                         case RIGHT: non_balanced_type = RL;   break;
  78.                                 }
  79.                         }
  80.                 }
  81.                 else {
  82.                         p = p->right_child;
  83.                         if (x != NULL) {
  84.                                 /* 根据插入路径确定不平衡类型 */
  85.                                 switch (non_balanced_type) {
  86.                                         case NONE:  non_balanced_type = RIGHT; break;
  87.                                         case LEFT:  non_balanced_type = LR;    break;
  88.                                         case RIGHT: non_balanced_type = RR;    break;
  89.                                 }
  90.                         }
  91.                 }
  92.         }

  94.         /* 键在原AVL树中不存在 */
  95.         if (p == NULL) {
  96.                 AVLTreeNode *new = malloc(sizeof (AVLTreeNode));
  97.                 bool insert_left, insert_right, is_balanced;
  98.                 int b;
  99.                 assert(new);

  101.                 new->key = malloc(avl->key_width);
  102.                 assert(new->key);
  103.                 new->value = malloc(avl->value_width);
  104.                 assert(new->value);
  105.                 new->parent = pp;
  106.                 new->left_child = NULL;
  107.                 new->right_child = NULL;

  109.                 memcpy(new->key, key, avl->key_width);
  110.                 memcpy(new->value, value, avl->value_width);
  111.                 new->bf = 0;

  113.                 /* 原树为空 */
  114.                 if (pp == NULL) {
  115.                         avl->root = new;
  116.                         return true;
  117.                 }

  119.                 insert_left = non_balanced_type == LL || non_balanced_type == LR || non_balanced_type == LEFT;
  120.                 insert_right = non_balanced_type == RR || non_balanced_type == RL || non_balanced_type == RIGHT;
  121.                 is_balanced = (x != NULL) && ((x->bf == 1 && insert_right) || (x->bf == -1 && insert_left));

  123.                 if (cmp_result < 0) {
  124.                         pp->left_child = new;
  125.                         ++pp->bf;
  126.                 }
  127.                 else {
  128.                         pp->right_child = new;
  129.                         --pp->bf;
  130.                 }
  131.                        

  133.                 /*************************************************************************************
  134.                  * 当插入路径上的节点在插入前平衡因子都为0的话, 修改从根节点到pp的父节点的平衡因子,  *
  135.                  * 否则修改从x到pp父节点的平衡因子(pp的平衡因子已经修改过)                           *
  136.                  *************************************************************************************/
  137.                 p = (x == NULL) ? avl->root : x;

  139.                 while (p != pp) {
  140.                         if (avl->cmp_key(key, p->key) < 0) {
  141.                                 ++p->bf;
  142.                                 p = p->left_child;
  143.                         }
  144.                         else {
  145.                                 --p->bf;
  146.                                 p = p->right_child;
  147.                         }
  148.                 }

  150.                 /* 树在插入后仍然保持平衡 */
  151.                 if (x == NULL || is_balanced)
  152.                         return true;

  154.                 /* 插入后树不平衡 */
  155.                 /* 根据不平衡类型执行对应旋转 */
  156.                 switch (non_balanced_type) {
  157.                         case LL: LLRotate(x);
  158.                                  x->right_child->bf = 0;
  159.                                  break;
  160.                         case LR: b = x->left_child->right_child->bf;
  161.                                  LRRotate(x);
  162.                                  x->left_child->bf = (b == -1) ? 1 : 0;
  163.                                  x->right_child->bf = (b == 1) ? -1 : 0;
  164.                                  break;
  165.                         case RL: b = x->right_child->left_child->bf;
  166.                                  RLRotate(x);
  167.                                  x->left_child->bf = (b == -1) ? 1 : 0;
  168.                                  x->right_child->bf = (b == 1) ? -1 : 0;
  169.                                  break;
  170.                         case RR: RRRotate(x);
  171.                                  x->left_child->bf = 0;
  172.                                  break;
  173.                         default: assert(0);     break;
  174.                 }
  175.                 x->bf = 0;
  176.                 return true;
  177.         }
  178.         return false;
  179. }


  182. bool DeleteAVLTree(AVLTree avl, const void *key, void *value)
  183. {
  184.         AVLTreeNode *p = avl->root, /* p指向要删除的节点 */
  185.                     *q = NULL, /* q指向p的父节点 */
  186.                     *c; /* c在下面会说明 */
  187.         int cmp_result;
  188.         bool lower = false;

  190.         while (p != NULL && (cmp_result = avl->cmp_key(key, p->key)) != 0) {
  191.                 q = p;
  192.                 p = (cmp_result < 0) ? p->left_child : p->right_child;
  193.         }

  195.         /* 没有找到关键字为key的节点 */
  196.         if (p == NULL)
  197.                 return false;

  199.         memcpy(value, p->value, avl->value_width);

  201.         /* 欲删除节点有两个孩子 */
  202.         if (p->left_child != NULL && p->right_child != NULL) {
  203.                 AVLTreeNode *prev = FindPrev(p);
  204.                 void *p_key = p->key, *p_value = p->value;

  206.                 p->key = prev->key;
  207.                 p->value = prev->value;
  208.                 prev->key = p_key;
  209.                 prev->value = p_value;

  211.                 p = prev;
  212.                 q = prev->parent;
  213.         }

  215.         /* c指向p唯一非空的子树(如果p为叶子节点c为NULL) */
  216.         c = (p->left_child != NULL) ? p->left_child : p->right_child;

  218.         if (p == avl->root) {
  219.                 avl->root = c;
  220.                 q = NULL;
  221.         } else if (p == q->left_child) {
  222.                 q->left_child = c;
  223.                 --q->bf;
  224.         } else {
  225.                 q->right_child = c;
  226.                 ++q->bf;
  227.         }

  229.         if (c != NULL)
  230.                 c->parent = q;

  232.         free(p->key);
  233.         free(p->value);
  234.         free(p);

  236.         while (q != NULL) {
  237.                 if (lower) {
  238.                         if (p == q->left_child)
  239.                                 --q->bf;
  240.                         else
  241.                                 ++q->bf;
  242.                 }

  244.                 if (q->bf == 0)
  245.                         lower = true;
  246.                 else if (q->bf == 1 || q->bf == -1)
  247.                         break;
  248.                 else {
  249.                         /* 树出现不平衡 */
  250.                         /* 除了R0型不平衡和L0型不平衡外, 其他不平衡矫正后都会使子树的高度减小 */
  251.                         int b;

  253.                         if (q->bf == 2) {
  254.                                 /* R型不平衡 */
  255.                                 int lbf = q->left_child->bf;

  257.                                 if (lbf == 0) {
  258.                                         /* R0型不平衡 */
  259.                                         LLRotate(q);
  260.                                         q->bf = -1;
  261.                                         q->right_child->bf = 1;
  262.                                         break;
  263.                                 } else if (lbf == 1) {
  264.                                         /* R1型不平衡 */
  265.                                         LLRotate(q);
  266.                                         q->bf = 0;
  267.                                         q->right_child->bf = 0;
  268.                                 } else {
  269.                                         /* R-1型不平衡 */
  270.                                         b = q->left_child->right_child->bf;
  271.                                         LRRotate(q);
  272.                                         q->bf = 0;
  273.                                         q->left_child->bf = (b == -1) ? 1 : 0;
  274.                                         q->right_child->bf = (b == 1) ? -1 : 0;
  275.                                 }
  276.                         } else {
  277.                                 /* L型不平衡 */
  278.                                 int rbf = q->right_child->bf;

  280.                                 if (rbf == 0) {
  281.                                         /* L0型不平衡 */
  282.                                         RRRotate(q);
  283.                                         q->bf = 1;
  284.                                         q->left_child->bf = -1;
  285.                                         break;
  286.                                 } else if (rbf == 1) {
  287.                                         /* L1型不平衡 */
  288.                                         b = q->right_child->left_child->bf;
  289.                                         RLRotate(q);
  290.                                         q->bf = 0;
  291.                                         q->left_child->bf = (b == -1) ? 1 : 0;
  292.                                         q->right_child->bf = (b == 1) ? -1 : 0;
  293.                                 } else {
  294.                                          /* L-1型不平衡 */
  295.                                         RRRotate(q);
  296.                                         q->bf = 0;
  297.                                         q->left_child->bf = 0;
  298.                                 }
  299.                         }
  300.                         lower = true;
  301.                 }

  303.                 /* 上升一层 */
  304.                 p = q;
  305.                 q = q->parent;
  306.         }

  308.         return true;
  309. }

  311. void * SearchAVLTree(AVLTree avl, const void *key)
  312. {
  313.         AVLTreeNode *p = avl->root;
  314.         int cmp_result;

  316.         while (p != NULL && (cmp_result = avl->cmp_key(key, p->key)) != 0)
  317.                 p = (cmp_result < 0) ? p->left_child : p->right_child;

  319.         return (p == NULL) ? NULL : p->value;
  320. }

  322. bool IsAVLTreeEmpty(AVLTree avl)
  323. {
  324.         return avl->root == NULL;
  325. }

  327. void ClearAVLTree(AVLTree avl)
  328. {
  329.         DestroyTree(avl->root);
  330.         avl->root = NULL;
  331. }

  333. void DestroyAVLTree(AVLTree avl)
  334. {
  335.         DestroyTree(avl->root);
  336.         free(avl);
  337. }

  339. static void LLRotate(AVLTreeNode *x)
  340. {
  341.         /*      X(2)                            Y(0)
  342.          *     /   \                           /    \
  343.          *   Y(1)   Xr     ---->             Yl     X(0)
  344.          *   / \     h                       h+1    /  \
  345.          * Yl   Yr                                 Yr  Xr
  346.          * h+1   h                                 h   h
  347.          */
  348.         AVLTreeNode *y = x->left_child, *xr = x->right_child;
  349.         void *x_key = x->key, *x_value = x->value;
  350.         /*      X(2)                            X(-2)
  351.          *     /   \                           /    \
  352.          *   Y(1)   Xr     ---->             Yl     Y(1)
  353.          *   / \     h                       h+1    /  \
  354.          * Yl   Yr                                 Yl  Yr
  355.          * h+1   h                                 h+1  h
  356.          */
  357.         x->left_child = y->left_child;
  358.         if (y->left_child != NULL)
  359.                 y->left_child->parent = x;
  360.         x->right_child = y;
  361.         /*      X(-2)                  Y(0)
  362.          *     /   \                  /    \
  363.          *   Yl     Y(1)    ---->    Yl    X(0)
  364.          *   h+1    /  \             h+1   /  \
  365.          *         Yl  Yr                 Yr  Xr
  366.          *         h+1  h                 h   h
  367.          */
  368.         x->key = y->key;
  369.         x->value = y->value;

  371.         y->key = x_key;
  372.         y->value = x_value;

  374.         y->left_child = y->right_child;
  375.         y->right_child = xr;
  376.         if (xr != NULL)
  377.                 xr->parent = y;
  378. }

  380. static void LRRotate(AVLTreeNode *x)
  381. {
  382.         RRRotate(x->left_child);
  383.         LLRotate(x);
  384. }

  386. static void RLRotate(AVLTreeNode *x)
  387. {
  388.         LLRotate(x->right_child);
  389.         RRRotate(x);
  390. }

  392. static void RRRotate(AVLTreeNode *x)
  393. {
  394.         /*     X(-2)                    Y(0)
  395.          *    /   \                    /   \
  396.          *   Xl   Y(-1)    ---->     X(0)   Yr
  397.          *   h    /   \              /  \   h+1
  398.          *       Yl    Yr           Xl   Yl
  399.          *       h     h+1          h    h
  400.          */
  401.         AVLTreeNode *y = x->right_child;
  402.         AVLTreeNode *xl = x->left_child;
  403.         void *x_key = x->key, *x_value = x->value;
  404.         /*     X(-2)                    Y(0)     
  405.          *    /   \                    /    \
  406.          *   Xl    Y(-1)   ---->     X(0)   Yr
  407.          *   h     /   \             /  \    h+1
  408.          *        Yl   Yr           Xl   Yl
  409.          *        h    h+1          h    h
  410.          */
  411.         x->right_child = y->right_child;
  412.         if (y->right_child != NULL)
  413.                 y->right_child->parent = x;
  414.         x->left_child = y;

  416.         y->right_child = y->left_child;
  417.         y->left_child = xl;
  418.         if (xl != NULL)
  419.                 xl->parent = y;

  421.         x->key = y->key;
  422.         x->value = y->value;

  424.         y->key = x_key;
  425.         y->value = x_value;
  426. }

  428. static void DestroyTree(AVLTreeNode *root)
  429. {
  430.         if (root != NULL) {
  431.                 DestroyTree(root->left_child);
  432.                 DestroyTree(root->right_child);
  433.                 free(root->key);
  434.                 free(root->value);
  435.                 free(root);
  436.         }
  437. }

  439. static AVLTreeNode * FindPrev(AVLTreeNode *root)
  440. {
  441.         for (root = root->left_child; root->right_child != NULL;
  442.              root = root->right_child)
  443.                 ;
  444.         return root;       
  445. }
复制代码

也许我的代码不是很好, 也恳请大神指教~
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

柠“萌”圆
 楼主| 发表于 2015-2-15 13:23:35 | 显示全部楼层
我发帖之前对代码做了小小的修改, 所以大家看到的代码少了一行, 变成了445行
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

柠“萌”圆
 楼主| 发表于 2015-2-15 13:25:12 | 显示全部楼层
另外这个源文件也只能用C语言编译器编译(不能用C++编译器), 因为里面有变量被命名为new, 而new是C++的关键字......用C++编译器编译的代码要做些修改
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

柠“萌”圆
 楼主| 发表于 2015-2-15 13:30:43 | 显示全部楼层
我也希望小甲鱼能把AVL树的删除课程补上......
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

Angel丶L
发表于 2015-2-15 13:33:29 | 显示全部楼层
支持学习了。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

柠“萌”圆
 楼主| 发表于 2015-2-15 16:19:05 | 显示全部楼层
范型->泛型......
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

柠“萌”圆
 楼主| 发表于 2015-2-19 20:46:54 | 显示全部楼层
进来看的朋友给个回复吧, 否则我会以为根本没人看我的帖的:cry
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-4-16 01:35

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表