首页 > 代码库 > robot framework 测试实体 红黑树

robot framework 测试实体 红黑树

2024-07-15 22:52:34   224人阅读

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

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

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

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
    #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 <stdio.h>
    #include <stdlib.h>
    #include<assert.h>
    #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<SIZE;i++)
        {
            array[i] = rand()%100000;
            unsigned long long key = array[i];
            int ret = rbtree_insert(tree,key,&array[i]);//-1 mean alloc node failed,
                                                         //-2 mean existed node with same key
           // print_tree(tree);
            void * data = http://www.mamicode.com/rbtree_lookup(tree,key);
            if(ret == 0)
                assert(data =http://www.mamicode.com/= &array[i]);
        }
         
        for(i = 0; i <SIZE;i+=2)
        {
            rbtree_remove(tree,array[i]);
            //print_tree(tree);
        }
        return 0;
    }


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


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


联系
我们