• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Daly的游戲人生

            紅黑樹的實現與討論

                 紅黑樹是比較常用的二叉查找樹,也是比較難實現的查找樹。他的實質是把2-3-4樹(即4階的B樹)化為二叉樹的表示形式,具有較好的性能。一般算法書(包括CLRS的算法導論)講述red-black tree都講得很頭暈,特別是各種不同情況的討論。最好看看紅黑樹的作者之一sedgewick的pdf(參見此處)。 另外,cnblogs的abatei兄也把原理講得很清楚(點擊這里)。

                 由于red-black tree的復雜性,sedgewick在08年重新審視了紅黑樹的實現,   提出了left-leaning red-black tree . 大大簡化了red-black tree的實現難度,代碼非常簡潔清晰。不過外國某人實現了LLRB,插入和刪除的效率大概比標準紅黑樹慢一倍左右,搜索效率相當。
                 自上而下的遞歸版本的代碼量少很多,而且很清晰,但是效率不及自下以上的迭代實現。
                 為了進一步節省空間,可以把color信息合并到parent指針中。這是由于指針以4字節對齊,最低兩位必然為0,顏色值只有紅,黑兩種狀態,于是可以利用最低的1bit保存顏色信息,只需要定義一些 位運算的宏,便可以節省了4byte/結點的空間 。
            #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
            #define rb_color(r)   ((r)->rb_parent_color & 1)
            #define rb_is_red(r)   (!rb_color(r))
            #define rb_is_black(r) rb_color(r)
            #define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
            #define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)

              
                自己根據linux kernel中的rbtree.c(非遞歸),做了一層薄薄的C++模板封裝,并對比了不同實現的效率。(本實現中沒有把color合并到指針中)
                 (我的rbtree源代碼下載)

                 測試環境:
                 Intel celeron 2.4GHz / 1GB 內存 / winXP
                 編譯環境: VC++ 6.0  和 Dev c++ 4.9.9

                 結果:
                 測試數據分別是50000和5000個隨機樣本,  時間為所有樣本操作總和,單位為ms
                
            my rbtree gcc STL map VC6 STL map 線性搜索
            insert 106.2  /  5.11 173.6 / 8.17 402.7  /  40.16 0
            search 73.9  /  1.69  89.7  /  3.28 226.9  /  17.8 3936.8  /  32.8
            delete 131.1  /  5.07 177.1  /  9.56 579.9  /  47.9

               對于5000個以內的樣本,搜索5000個元素總共才用了幾毫秒,已經可以滿足一般key查找應用了。
               由于rbtree的實現復雜性,AVL樹和Treaps的實際效率并不比red-black tree差,但是實現要簡單多了。(參見此處)
               在本測試例子中,key是一個范圍內的整數,用hash table會快得到,這樣不太公平,因此就沒測了。而且hash的數據是無序的,不支持范圍查找。

            PS:  VC6的PJ版STL實現可以扔進垃圾桶了。STL的實現還是用SGI版本的比較好。

            以下是benchmark的代碼

              1struct SampleType {
              2    char ch[8];
              3}
            ;
              4
              5struct SampleType testvalue;
              6
              7void benchmark_once(int nkeys)
              8{
              9    int i;
             10    int* key_set[3];   //key_set[0] for insert, 1 for search, 2 for erase
             11    RbTree<int, SampleType> my_rbt;
             12    std::map<int, SampleType> stl_map;
             13    std::map<int, SampleType>::iterator stl_iter; 
             14
             15    //generate test sequence
             16    for (i=0; i<3; i++{
             17        key_set[i] = new int[nkeys];
             18        if (key_set[i] == NULL) exit(0);
             19    }

             20    for (i=0; i<nkeys; i++{
             21        key_set[0][i] = key_set[1][i] = key_set[2][i] = i;
             22    }

             23
             24    srand(time(NULL));
             25    random_shuffle(key_set[0], nkeys);  //insert
             26    random_shuffle(key_set[1], nkeys);  //search
             27    random_shuffle(key_set[2], nkeys);  //erase
             28
             29    //begin test
             30
             31    LARGE_INTEGER litmp;
             32    LONGLONG  qbegin, qend;
             33    double df_freq, df_time;
             34    QueryPerformanceFrequency(&litmp);
             35    df_freq = (double)litmp.QuadPart;
             36
             37    //my rbtree ////////////////////////////
             38
             39    //insert benchmark
             40    QueryPerformanceCounter(&litmp);
             41    qbegin = litmp.QuadPart;
             42    for (i=0; i<nkeys; i++{
             43        my_rbt.insert(key_set[0][i], testvalue);
             44    }

             45
             46    QueryPerformanceCounter(&litmp);
             47    qend = litmp.QuadPart;
             48    df_time = (double)(qend - qbegin) / df_freq;
             49    printf("my rbtree insert: %lf ms\n", df_time*1000);
             50
             51    //search benchmark
             52    QueryPerformanceCounter(&litmp);
             53    qbegin = litmp.QuadPart;
             54
             55    for (i=0; i<nkeys; i++{
             56        my_rbt.search(key_set[1][i]);
             57    }

             58    QueryPerformanceCounter(&litmp);
             59    qend = litmp.QuadPart;
             60    df_time = (double)(qend - qbegin) / df_freq;
             61    printf("my rbtree search: %lf ms\n", df_time*1000);
             62
             63    //erase benchmark
             64    QueryPerformanceCounter(&litmp);
             65    qbegin = litmp.QuadPart;
             66
             67    for (i=0; i<nkeys; i++{
             68        my_rbt.erase(key_set[2][i]);
             69    }

             70    QueryPerformanceCounter(&litmp);
             71    qend = litmp.QuadPart;
             72    df_time = (double)(qend - qbegin) / df_freq;
             73    printf("my rbtree erase: %lf ms\n", df_time*1000);
             74
             75    //VC++6 version STL ////////////////////////////
             76    //insert test
             77    QueryPerformanceCounter(&litmp);
             78    qbegin = litmp.QuadPart;
             79    for (i=0; i<nkeys; i++{
             80        stl_map.insert(std::make_pair(key_set[0][i], testvalue));
             81    }

             82
             83    QueryPerformanceCounter(&litmp);
             84    qend = litmp.QuadPart;
             85    df_time = (double)(qend - qbegin) / df_freq;
             86    printf("stl_map insert: %lf ms\n", df_time*1000);
             87
             88    //search test
             89    QueryPerformanceCounter(&litmp);
             90    qbegin = litmp.QuadPart;
             91    for (i=0; i<nkeys; i++{
             92        stl_map.find(key_set[1][i]);
             93    }

             94
             95    QueryPerformanceCounter(&litmp);
             96    qend = litmp.QuadPart;
             97    df_time = (double)(qend - qbegin) / df_freq;
             98    printf("stl_map search: %lf ms\n", df_time*1000);
             99
            100    //erase test
            101    QueryPerformanceCounter(&litmp);
            102    qbegin = litmp.QuadPart;
            103
            104    for (i=0; i<nkeys; i++{
            105        stl_map.erase(key_set[2][i]);
            106    }

            107    QueryPerformanceCounter(&litmp);
            108    qend = litmp.QuadPart;
            109    df_time = (double)(qend - qbegin) / df_freq;
            110    printf("stl_map erase: %lf ms\n", df_time*1000);
            111
            112    //clear up sequence
            113    for (i=0; i<3; i++{
            114        delete[] key_set[i];
            115    }

            116}

            posted on 2009-11-20 20:21 Daly 閱讀(4046) 評論(4)  編輯 收藏 引用 所屬分類: 數據結構與算法

            評論

            # re: 紅黑樹的實現與討論[未登錄] 2009-11-23 10:12 Apan

            不錯!  回復  更多評論   

            # re: 紅黑樹的實現與討論 2010-05-18 23:40 GLENDANewman

            A thesis seek composition is a project for which a novice performs the most embracive ransack possible and blends it into a single assignment, usually filling 50 to 150 pages. So maybe <a href="http://www.supreme-thesis.com">dissertation writing service</a> will aid you.  回復  更多評論   

            # shi 2010-12-09 11:47 uk dress

            good post...  回復  更多評論   

            # Hairdresser George St Sydney 2011-05-21 14:40 Hairdresser George St Sydney

            Thanks for taking the time to talk about this, I feel fervently about this and I take pleasure in learning about this topic. Please, as you gain information, please update this blog with more information. I have found it very useful.  回復  更多評論   

            国内精品久久久久久久97牛牛 | 大香伊人久久精品一区二区| 午夜精品久久久久久久无码| 伊人色综合九久久天天蜜桃| 久久亚洲AV成人出白浆无码国产| 日本精品久久久久中文字幕8| 久久国产一片免费观看| 久久人人爽人人人人爽AV| 久久综合丝袜日本网| 欧美激情一区二区久久久| 久久99国产精品一区二区| 7777精品伊人久久久大香线蕉| 国产欧美一区二区久久| 久久只有这精品99| 久久综合久久久| 无码人妻久久一区二区三区免费| 国产精品丝袜久久久久久不卡| 久久综合给合久久狠狠狠97色| 污污内射久久一区二区欧美日韩| 久久99国产精品久久久| 久久婷婷国产剧情内射白浆| 久久久久久久综合日本| 国产∨亚洲V天堂无码久久久| 久久久久波多野结衣高潮| 久久精品国产72国产精福利| 色综合久久中文综合网| 国内精品久久人妻互换| 人妻少妇久久中文字幕| 色综合久久无码五十路人妻| 国产香蕉久久精品综合网| 亚洲欧美另类日本久久国产真实乱对白| 久久国产色AV免费看| 国产亚洲精久久久久久无码| 久久久无码精品亚洲日韩按摩| 久久精品国产亚洲AV蜜臀色欲 | 91精品日韩人妻无码久久不卡 | 国内精品久久久久| 久久99精品国产99久久6男男| 久久福利青草精品资源站| 国内精品久久久久久野外| 麻豆精品久久久一区二区|