数据结构之红黑树

    这周写了红黑树，不得不说红黑树是复杂难写的数据结构。尽管我闭上眼睛，能够还原出如何插入，时间充足的情况下，不给我任何资料我能写出插入部分，但是删除还是做不来。删除部分的心得并不多。因为左旋右旋，左左右右，一会就搞晕了。所以插入部分用了一个晚上就写完了，但是删除部分用了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:

    



参考文献：

1  （删除部分参考）

2  （总体结构参考）

3 维基百科

4 Linux kernel  （插入部分参考）

5 算法导论