Linux内核中的红黑树

Godbach

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的左子节点还是右子节点，应该是我们在程序里自己实现了吧？

prolj

sqlite除了hash还有B tree，管理大量数据RB Tree显然不如B Tree和hash有优势

Godbach

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

dreamice

原帖由 Godbach 于 2009-1-1 23:00 发表


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

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

Godbach

原帖由 dreamice 于 2009-1-2 15:39 发表


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

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

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

dreamice

原帖由 Godbach 于 2009-1-2 16:06 发表


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

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

Godbach

原帖由 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。这个可有前面在查找过程中确定。

蚊见蚊爱

这种数据结构的东西，还是看教材，代码参考产品代码 (STL 中也有 这个数据结构， )，最好不要使用未经严格测试的代码，

Godbach

原帖由 蚊见蚊爱 于 2009-1-3 16:45 发表
这种数据结构的东西，还是看教材，代码参考产品代码 (STL 中也有 这个数据结构， )，最好不要使用未经严格测试的代码，

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

creating2008

红黑树在STL容器里面基本上都用着了,数据库里面有B+树,hash多一点.