免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: Godbach

Linux内核中的红黑树 [复制链接]

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-01-01 23:00 |显示全部楼层
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                                struct rb_node ** rb_link)
{
        node->rb_parent_color = (unsigned long )parent;
        node->rb_left = node->rb_right = NULL;

        *rb_link = node;
}
它把parent设为node的父结点,并且让rb_link指向node。


一个疑问:
这个地方只能设置parent为node的父节点。那么node是作为parent的左子节点还是右子节点,应该是我们在程序里自己实现了吧?

论坛徽章:
0
发表于 2009-01-02 00:35 |显示全部楼层
sqlite除了hash还有B tree,管理大量数据RB Tree显然不如B Tree和hash有优势

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-01-02 12:50 |显示全部楼层

回复 #22 prolj 的帖子

请教prolj兄一个问题:
如果我想统计一段时间内和我本地主机通信的IP总数,你觉得用哪种方式实现更好?

论坛徽章:
3
金牛座
日期:2014-06-14 22:04:062015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:49:45
发表于 2009-01-02 15:39 |显示全部楼层
原帖由 Godbach 于 2009-1-1 23:00 发表


一个疑问:
这个地方只能设置parent为node的父节点。那么node是作为parent的左子节点还是右子节点,应该是我们在程序里自己实现了吧?


通过父结点来确认自身是左是右。

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-01-02 16:06 |显示全部楼层
原帖由 dreamice 于 2009-1-2 15:39 发表


通过父结点来确认自身是左是右。


dreamice兄什么意思,该函数并没有包含任何parent指向该节点的动作啊。

[ 本帖最后由 Godbach 于 2009-1-2 16:55 编辑 ]

论坛徽章:
3
金牛座
日期:2014-06-14 22:04:062015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:49:45
发表于 2009-01-02 17:11 |显示全部楼层
原帖由 Godbach 于 2009-1-2 16:06 发表


dreamice兄什么意思,该函数并没有包含任何parent只想该节点的动作啊。


如果是你自己写程序调用这个函数的话,那就是在查找阶段设置左还是右了

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-01-02 17:45 |显示全部楼层
原帖由 dreamice 于 2009-1-2 17:11 发表


如果是你自己写程序调用这个函数的话,那就是在查找阶段设置左还是右了


多谢dreamice兄的指点。明白了这个函数的实际用法:
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                                struct rb_node ** rb_link)
node为当前要插入的节点;
parent为node的父节点;
rb_link为node节点要插入的位置,即parent->left 或parent->right。这个可有前面在查找过程中确定。

论坛徽章:
0
发表于 2009-01-03 16:45 |显示全部楼层
这种数据结构的东西,还是看教材,代码参考产品代码 (STL 中也有 这个数据结构, ),最好不要使用未经严格测试的代码,

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-01-03 16:53 |显示全部楼层
原帖由 蚊见蚊爱 于 2009-1-3 16:45 发表
这种数据结构的东西,还是看教材,代码参考产品代码 (STL 中也有 这个数据结构, ),最好不要使用未经严格测试的代码,


这是内核中的代码,内存管理、进程管理都使用红黑树的接口。怎么能说未经严格测试的代码呢?

论坛徽章:
0
发表于 2009-01-03 22:09 |显示全部楼层
红黑树在STL容器里面基本上都用着了,数据库里面有B+树,hash多一点.
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP