红黑树的实现源码(C语言版)

Godbach

这两天正在学习converse版主的红黑树实现。
有个问题，对于内核中提供的rbtree的接口，定义的结构体：

1. struct rb_node
   
2. {
   
3.         unsigned long  rb_parent_color;
   
4. #define        RB_RED                0
   
5. #define        RB_BLACK        1
   
6.         struct rb_node *rb_right;
   
7.         struct rb_node *rb_left;
   
8. } __attribute__((aligned(sizeof(long))));

复制代码

这样在写程序调用这个接口的时候，是不是需要新定义接口体，包含struct rb_node，并且自定义key呢？

converse

没用过内核中的红黑树接口,不好回答这个问题....但是感觉跟那个流传的很广泛的内核中使用的list应该原理类似.

Godbach

最近可能要使用内核rbtree接口实现一些功能。看来得先学习一下这些接口的使用方法。

BTW，如果我想直接将一个tree所有节点释放，有什么好的方法呢？

converse

这简单啊,后序遍历树就OK啦...

Godbach

多谢。偶的数据结构学的不咋地，用的时候感觉吃力啊。有问题再请教converse兄啊。

converse

客气了,我这个代码也是copy别人的然后照着书改的

todaygood

把linux内核中的rbtree.c拿过来把与内核特有的代码删掉就可以用了

为何要自己写？

难不成楼主是想研究算法？

cugb_cat

原帖由 Godbach 于 2008-12-30 22:47 发表
这两天正在学习converse版主的红黑树实现。
有个问题，对于内核中提供的rbtree的接口，定义的结构体：
struct rb_node
{
        unsigned long  rb_parent_color;
#define        RB_RED                0
#define        RB_BLACK        1
        stru ...

用法和内核中的list结构是一样的，Linux内核代码的lib目录下封装的数据结构，基本上用法都一样的。

Godbach

相当于内核的接口只是提供一个红黑树构成的框架。
自行选好key，然后根据这个key，利用红黑树提供的相关接口，可以构建起来一个树。

xhl

BSD里的那个宏RB_TREE多好用啊， 而且效率还高