紅黑樹(shù)是比較常用的二叉查找樹(shù)，也是比較難實(shí)現(xiàn)的查找樹(shù)。他的實(shí)質(zhì)是把2-3-4樹(shù)（即4階的B樹(shù)）化為二叉樹(shù)的表示形式，具有較好的性能。一般算法書(shū)（包括CLRS的算法導(dǎo)論）講述red-black tree都講得很頭暈，特別是各種不同情況的討論。最好看看紅黑樹(shù)的作者之一sedgewick的pdf（
參見(jiàn)此處）。 另外，cnblogs的abatei兄也把原理講得很清楚(
點(diǎn)擊這里)。
由于red-black tree的復(fù)雜性，sedgewick在08年重新審視了紅黑樹(shù)的實(shí)現(xiàn), 提出了
left-leaning red-black tree . 大大簡(jiǎn)化了red-black tree的實(shí)現(xiàn)難度，代碼非常簡(jiǎn)潔清晰。不過(guò)外國(guó)某人實(shí)現(xiàn)了LLRB，插入和刪除的效率大概比標(biāo)準(zhǔn)紅黑樹(shù)慢一倍左右，搜索效率相當(dāng)。
自上而下的遞歸版本的代碼量少很多，而且很清晰，但是效率不及自下以上的迭代實(shí)現(xiàn)。
為了進(jìn)一步節(jié)省空間，可以把color信息合并到parent指針中。這是由于指針以4字節(jié)對(duì)齊，最低兩位必然為0，顏色值只有紅，黑兩種狀態(tài)，于是可以利用最低的1bit保存顏色信息，只需要定義一些 位運(yùn)算的宏，便可以節(jié)省了4byte/結(jié)點(diǎn)的空間 。
#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) 自己根據(jù)linux kernel中的rbtree.c（非遞歸），做了一層薄薄的C++模板封裝，并對(duì)比了不同實(shí)現(xiàn)的效率。（本實(shí)現(xiàn)中沒(méi)有把color合并到指針中）
(我的rbtree源代碼下載) 測(cè)試環(huán)境：
Intel celeron 2.4GHz / 1GB 內(nèi)存 / winXP
編譯環(huán)境： VC++ 6.0 和 Dev c++ 4.9.9
結(jié)果：
測(cè)試數(shù)據(jù)分別是50000和5000個(gè)隨機(jī)樣本, 時(shí)間為所有樣本操作總和，單位為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 |
|
對(duì)于5000個(gè)以?xún)?nèi)的樣本，搜索5000個(gè)元素總共才用了幾毫秒，已經(jīng)可以滿(mǎn)足一般key查找應(yīng)用了。
由于rbtree的實(shí)現(xiàn)復(fù)雜性，AVL樹(shù)和Treaps的實(shí)際效率并不比red-black tree差，但是實(shí)現(xiàn)要簡(jiǎn)單多了。(
參見(jiàn)此處)
在本測(cè)試?yán)又校琸ey是一個(gè)范圍內(nèi)的整數(shù)，用hash table會(huì)快得到，這樣不太公平，因此就沒(méi)測(cè)了。而且hash的數(shù)據(jù)是無(wú)序的，不支持范圍查找。
PS: VC6的PJ版STL實(shí)現(xiàn)可以扔進(jìn)垃圾桶了。STL的實(shí)現(xiàn)還是用SGI版本的比較好。
以下是benchmark的代碼
1
struct 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}