内核红黑树使用范例 蔚落 2022-08-06 08:29 172阅读 0赞 # [内核红黑树使用范例][Link 1] # 内核中的红黑树只是提供了一个管理机制,并没有提供具体的使用接口。需要使用者根据自己的使用环境去定义和实现自己的关键字(char,uchar, int, uint等类型)操作。这样可以更加灵活。 像内核中的链表,hash表的代码都是这种思想。 ![复制代码][copycode.gif] 1 struct mytype 2 { 3 int num; 4 5 struct rb_node my_node; 6 }; 7 8 struct mytype *my_find(struct rb_root *root, int num) 9 { 10 struct rb_node *node = root->rb_node; 11 12 while (node) { 13 struct mytype *data = rb_entry(node, struct mytype, my_node); 14 15 if (num < data->num) 16 node = node->rb_left; 17 else if (num > data->num) 18 node = node->rb_right; 19 else 20 return data; 21 } 22 23 return NULL; 24 } 25 26 27 int my_insert(struct rb_root *root, struct mytype *data) 28 { 29 struct rb_node *parent = NULL; 30 struct rb_node **tmp = &(root->rb_node); 31 32 /* Figure out where to put new node */ 33 while (*tmp) { 34 struct mytype *this = rb_entry(*tmp, struct mytype, my_node); 35 36 parent = *tmp; 37 if (data->num < this->num) 38 tmp = &((*tmp)->rb_left); 39 else if (data->num > this->num) 40 tmp = &((*tmp)->rb_right); 41 else 42 return -1; 43 } 44 45 /* Add new node and rebalance tree. */ 46 rb_link_node(&data->my_node, parent, tmp); 47 rb_insert_color(&data->my_node, root); 48 49 return 0; 50 } 51 52 53 void my_delete(struct rb_root *root, int num) 54 { 55 struct mytype *data = my_find(root, num); 56 if(data != NULL) 57 { 58 rb_erase(&data->my_node, root); 59 free(data); 60 } 61 } 62 63 void my_destory(struct rb_root *tree) 64 { 65 struct rb_node *node; 66 67 for(node = rb_first(tree); node; node = rb_next(node)) 68 { 69 my_delete(tree, rb_entry(node, struct mytype, my_node)->num); 70 } 71 } 72 73 void my_printf(struct rb_root *tree) 74 { 75 struct rb_node *node; 76 77 for(node = rb_first(tree); node; node = rb_next(node)) 78 { 79 printf("%d ", rb_entry(node, struct mytype, my_node)->num); 80 } 81 82 printf("\n"); 83 } 84 85 86 #define RBTREE_MAX_NUM 10 87 88 int main(int argc, char *argv[]) 89 { 90 struct mytype *tmp = NULL; 91 struct rb_root mytree = RB_ROOT; 92 93 srand((unsigned int)time(NULL)); 94 95 unsigned int i = 0; 96 for(i = 0; i < RBTREE_MAX_NUM; ++i) 97 { 98 tmp = malloc(sizeof(struct mytype)); 99 if(tmp == NULL) 100 { 101 perror("Allocate dynamic memory"); 102 exit(-1); 103 } 104 105 tmp->num = rand()%100; 106 107 printf("%d ", tmp->num); 108 109 int ret = my_insert(&mytree, tmp); 110 if (ret < 0) 111 { 112 fprintf(stderr, "The %d already exists\n", tmp->num); 113 free(tmp); 114 } 115 } 116 117 printf("\n"); 118 119 my_printf(&mytree); 120 121 char buf[10]; 122 123 while(1) 124 { 125 printf("\n****************************************"); 126 printf("\n* +number to insert :"); 127 printf("\n* -number to delete :"); 128 printf("\n* q to quit :"); 129 printf("\n****************************************\n"); 130 131 fgets(buf, sizeof(buf), stdin); 132 133 if(buf[0] == 'q') 134 { 135 break; 136 } 137 else if(buf[0] == '+') 138 { 139 tmp = malloc(sizeof(struct mytype)); 140 if(tmp == NULL) 141 { 142 perror("Allocate dynamic memory"); 143 continue; 144 } 145 146 tmp->num = atoi(&buf[1]); 147 148 int ret = my_insert(&mytree, tmp); 149 if (ret < 0) 150 { 151 fprintf(stderr, "The %d already exists\n", tmp->num); 152 free(tmp); 153 } 154 } 155 else if(buf[0] == '-') 156 { 157 my_delete(&mytree, atoi(&buf[1])); 158 } 159 else 160 { 161 continue; 162 } 163 164 my_printf(&mytree); 165 166 } 167 168 my_destory(&mytree); 169 170 return 0; 171 } ![复制代码][copycode.gif] [Link 1]: http://www.cnblogs.com/li-hao/archive/2013/04/16/3024856.html [copycode.gif]: /images/20220806/fc0163f03bb9438fb8e50254aa2702ea.png
相关 树:红黑树 1,红黑树引入 红黑树是对AVL树的补充。AVL树要求整个树的高度差不能超过1,超过后需要进行左旋或者右旋操作再次对树进行平衡,虽然这样能够解决二叉树退化为链表的缺 ╰半橙微兮°/ 2023年02月28日 01:25/ 0 赞/ 175 阅读
相关 红黑树 红黑树的定义 每个节点要么是红色,要么是黑色。 根节点必须是黑色, 每个叶子节点是黑色(叶子节点包含NULL)。 红色节点不能连续(红色节点的孩子和父亲 Dear 丶/ 2022年12月13日 04:18/ 0 赞/ 38 阅读
相关 内核红黑树使用范例 [内核红黑树使用范例][Link 1] 内核中的红黑树只是提供了一个管理机制,并没有提供具体的使用接口。需要使用者根据自己的使用环境去定义和实现自己的关键字(char 蔚落/ 2022年08月06日 08:29/ 0 赞/ 173 阅读
相关 内核红黑树源码注解 [内核红黑树源码注解][Link 1] ![复制代码][copycode.gif] 1 typedef struct st_rb_node { 忘是亡心i/ 2022年08月06日 08:29/ 0 赞/ 208 阅读
相关 红黑树 红黑树(Red Black Tree) 是一种自平衡二叉查找树,红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能,它虽然 谁践踏了优雅/ 2022年06月15日 12:57/ 0 赞/ 520 阅读
相关 红黑树 > 3.3 Balanced Search Trees > [http://algs4.cs.princeton.edu/33balanced/][http_algs4.c ╰+攻爆jí腚メ/ 2022年06月09日 12:48/ 0 赞/ 371 阅读
相关 红黑树 红黑树 概念 红黑树,又被称为对称二叉B树。 [红黑树模型][Link 1] 其本质是一种二叉查找树,单它在二叉查找树的基础上额外添加了一个标记(颜色),同时具 拼搏现实的明天。/ 2022年04月10日 02:39/ 0 赞/ 462 阅读
相关 红黑树 先Mark,后续补充: [https://juejin.im/entry/58371f13a22b9d006882902d][https_juejin.im_entry_58 柔情只为你懂/ 2022年01月30日 14:57/ 0 赞/ 364 阅读
相关 红黑树 二叉查找树(BST) 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 下 川长思鸟来/ 2021年10月24日 01:48/ 0 赞/ 420 阅读
相关 红黑树 1. 从 2-3 树说起 一棵标准的 BST (二叉查找树 / 二叉搜索树)是长这个样子的: BST 其中,这棵二叉查找树中的每个结点也叫 2-结点 ,2-结点 就表示树... 系统管理员/ 2020年11月29日 04:30/ 0 赞/ 866 阅读
还没有评论,来说两句吧...