Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3220906
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8557
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2012-12-15 14:53:34

    这周写了红黑树,不得不说红黑树是复杂难写的数据结构。尽管我闭上眼睛,能够还原出如何插入,时间充足的情况下,不给我任何资料我能写出插入部分,但是删除还是做不来。删除部分的心得并不多。因为左旋右旋,左左右右,一会就搞晕了。所以插入部分用了一个晚上就写完了,但是删除部分用了2个晚上,又是看算法导论,又是看linux kernel 内核的实现。最终仿照了wiki给出代码,参考写出了删除部分。

    原理部分我就不写了,我觉得左右虽然是对称的,也算的上优美,两份本质一样的代码,对称地存在在C文件中,本质也是一种冗余。如果没有删除部分,我有雄心,不区分左右,采用child[2]的方式,把左旋右旋 插入部分代码统一在一个架构里面。可是删除写的自己很闹心,可能是我还是没有掌握红黑树的精髓所在。

    另一个需要提到的事情是结果的可视化,平衡二叉树,最好的调试手段就是把结果打印出来,打印的直观,就可以分析二叉树是否是对的。我在网上找了相关的代码,不是十分优雅的解决了这个问题。接下来可以学习学习这个方面,我在stackoverflow找到一篇文章不错,还没来得及学习。

    #ifndef __RBTREE_H__
    #define __RBTREE_H__
    enum rb_color
    {
        RB_BLACK,
        RB_RED,
    };
    typedef struct rbtree_node
    {
        struct rbtree_node* parent;
        struct rbtree_node* left;
        struct rbtree_node* right;
        enum rb_color color;
        unsigned long long key;
        void *data;
    }rbtree_node;
    typedef struct rbtree
    {
        struct rbtree_node* root;
    }rbtree;
    struct rbtree* rbtree_init();
    int rbtree_insert(struct rbtree *tree, unsigned long long key,void* data);
    void* rbtree_lookup(struct rbtree* tree,unsigned long long key);
    int rbtree_remove(struct rbtree* tree,unsigned long long key);
    #endif

下面是测试代码:

    #include"rbtree.h"
    #include 
    #include 
    #include
    #define SIZE 1600
    void padding ( char ch, int n )
    {
      int i;
      for ( i = 0; i < n; i++ )
        putchar ( ch );
    }
    void print_node ( struct rbtree_node *root, int level )
    {
      if ( root == NULL )
      {
        padding ( '\t', level );
        puts ( "NIL" );
      }
      else
      {
        print_node ( root->right, level + 1 );
        padding ( '\t', level );
        if(root->color == RB_BLACK)
        {
            printf ( "(%llu)\n", root->key );
        }
        else
           printf ( "%llu\n", root->key );
        print_node ( root->left, level + 1 );
      }
    }
    void print_tree(struct rbtree* tree)
    {
        print_node(tree->root,0);
        printf("-------------------------------------------\n");
    }
    int main()
    {
        struct rbtree* tree = rbtree_init();
        if(tree == NULL)
        {
            fprintf(stderr,"malloc tree failed\n");
            return -1;
        }
        int i = 0;
        int array[SIZE] = {0};
        for(i = 0;i

    print_tree把中间结果打印出来,这个test工具帮我不少帮,调试的过程,如果没有这个print_tree,全靠gdb的话,调试会特别的难受:


    RB红黑树实现部分就不贴了,有点长,500行代码贴上,估计也没人看。完整部分的代码在github,需要的筒子可以拿一份自己,如感兴趣,请访问我的github:
    https://github.com/manuscola/rbtree

参考文献:
1 LiteratePrograms (删除部分参考)
2 https://github.com/fbuihuu/libtree (总体结构参考)
3 维基百科
4 Linux kernel  (插入部分参考)
5 算法导论


阅读(4982) | 评论(4) | 转发(1) |
给主人留下些什么吧!~~

bottles2012-12-20 14:08:20

抽空也要把所有数据结构再复习一遍的说,感谢lz给我的提示。

bottles2012-12-20 14:06:11

红黑树很久以前在学校里写过。。现在都已经忘光了,lz太牛居然还能写出来。。

Bean_lee2012-12-19 17:23:33

GFree_Wind: 有时间下载代码学习一下。.....
基础虽然是很重要的,但是基础不好玩。这种基本功还是学校里面学比较合适。
600行代码,得花了我8个多小时,又是看书,又是上网查资料,一边理解一边写。

GFree_Wind2012-12-19 12:34:32

有时间下载代码学习一下。