-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathjv_rbtree_main.c
executable file
·199 lines (163 loc) · 10.7 KB
/
jv_rbtree_main.c
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include <jv_rbtree.h>
jv_uint_t tiny[] = {4, 9, 7, 13, 14, 2, 12, 8, 5, 0};
jv_uint_t lump[] = {54, 90, 82, 43, 31, 92, 96, 74, 8, 18, 92, 98, 67, 89, 41, 13, 46, 47, 93, 45, 88, 77, 59, 38, 2, 93,
38, 36, 13, 40, 14, 42, 45, 79, 15, 24, 58, 87, 91, 22, 23, 7, 61, 99, 72, 5, 22, 82, 79, 62, 25, 86,
1, 31, 52, 89, 27, 40, 84, 15, 90, 14, 44, 52, 70, 53, 94, 42, 56, 94, 52, 42, 79, 83, 14, 31, 76, 30,
6, 9, 83, 98, 96, 41, 7, 51, 54, 38, 63, 13, 76, 99, 44, 28, 79, 41, 53, 51, 62, 34, 0};
jv_uint_t huge[] = {
865, 924, 943, 880, 181, 396, 600, 507, 260, 477, 315, 487, 50, 359, 373, 737, 244, 889, 33, 503, 28, 938, 729, 139, 481, 637, 917, 904, 965,
190, 425, 173, 831, 490, 556, 878, 948, 467, 986, 817, 470, 192, 768, 661, 923, 264, 479, 546, 88, 903, 322, 923, 771, 788, 539, 184, 563, 97,
672, 327, 650, 826, 627, 714, 176, 809, 949, 939, 78, 787, 832, 498, 187, 0, 694, 461, 239, 535, 765, 972, 137, 468, 252, 432, 761, 52, 178,
661, 310, 369, 72, 860, 190, 280, 814, 547, 255, 656, 132, 132, 301, 890, 310, 549, 574, 396, 680, 861, 200, 966, 550, 730, 158, 181, 764, 776,
797, 232, 188, 829, 918, 647, 944, 938, 382, 651, 238, 717, 540, 838, 405, 657, 414, 886, 226, 639, 475, 724, 456, 613, 803, 256, 805, 929, 197,
648, 953, 701, 48, 858, 346, 758, 535, 216, 428, 600, 712, 937, 498, 462, 839, 415, 942, 703, 863, 793, 977, 163, 749, 2, 19, 951, 544, 540,
794, 331, 870, 999, 834, 274, 46, 250, 540, 253, 452, 445, 936, 300, 953, 125, 990, 58, 827, 527, 67, 887, 509, 850, 602, 64, 158, 245, 633,
475, 538, 41, 126, 291, 529, 569, 404, 686, 445, 690, 142, 894, 82, 234, 635, 262, 125, 789, 277, 557, 977, 759, 366, 657, 628, 975, 549, 939,
177, 671, 365, 116, 27, 911, 659, 321, 45, 573, 730, 82, 148, 404, 4, 672, 698, 812, 900, 447, 989, 473, 20, 857, 338, 231, 395, 490, 136,
319, 655, 83, 217, 132, 244, 372, 265, 377, 723, 793, 903, 242, 597, 493, 297, 648, 902, 557, 997, 559, 382, 128, 479, 346, 460, 983, 383, 800,
960, 19, 574, 830, 898, 517, 666, 132, 200, 473, 899, 2, 84, 475, 532, 210, 623, 283, 538, 717, 632, 138, 803, 587, 777, 408, 23, 141, 37,
776, 193, 161, 989, 266, 393, 342, 190, 420, 506, 114, 381, 231, 396, 334, 897, 674, 228, 176, 388, 745, 145, 875, 110, 754, 985, 232, 69, 238,
488, 17, 899, 654, 316, 528, 192, 731, 833, 160, 607, 314, 885, 717, 143, 965, 554, 792, 784, 568, 763, 495, 324, 852, 260, 760, 468, 236, 767,
848, 36, 459, 821, 387, 537, 86, 46, 793, 995, 605, 460, 710, 402, 260, 727, 579, 739, 167, 78, 467, 251, 657, 273, 364, 166, 2, 166, 168,
592, 443, 747, 352, 812, 164, 985, 309, 921, 597, 555, 665, 65, 936, 296, 397, 146, 208, 796, 421, 884, 418, 92, 483, 752, 168, 749, 231, 534,
607, 474, 947, 920, 468, 956, 417, 689, 871, 643, 700, 698, 394, 412, 837, 898, 358, 226, 121, 542, 446, 360, 784, 255, 706, 449, 322, 853, 516,
640, 253, 127, 815, 467, 827, 472, 77, 581, 815, 201, 381, 703, 686, 502, 322, 54, 870, 185, 147, 13, 969, 533, 122, 790, 272, 150, 688, 890,
286, 568, 951, 21, 279, 940, 785, 291, 608, 183, 359, 157, 363, 948, 813, 795, 271, 170, 734, 908, 217, 855, 122, 718, 671, 157, 260, 273, 641,
407, 654, 350, 23, 202, 12, 670, 881, 885, 999, 468, 259, 616, 44, 811, 133, 727, 664, 434, 853, 227, 698, 840, 10, 377, 12, 844, 359, 600,
742, 55, 395, 304, 323, 209, 446, 958, 443, 724, 476, 414, 291, 908, 829, 724, 948, 245, 352, 758, 390, 785, 179, 465, 538, 417, 439, 799, 331,
22, 146, 671, 827, 568, 503, 220, 416, 758, 490, 514, 731, 265, 3, 44, 247, 203, 373, 123, 123, 629, 282, 589, 388, 197, 25, 441, 205, 968,
656, 960, 39, 325, 912, 47, 736, 178, 354, 925, 783, 839, 836, 47, 53, 146, 842, 634, 136, 800, 332, 123, 21, 515, 55, 252, 709, 727, 94,
835, 502, 311, 521, 42, 322, 89, 145, 119, 979, 420, 578, 670, 202, 869, 133, 127, 464, 972, 960, 218, 892, 818, 199, 72, 345, 348, 7, 344,
852, 613, 149, 652, 275, 23, 817, 697, 336, 337, 600, 59, 874, 120, 816, 968, 637, 272, 710, 739, 205, 887, 613, 642, 556, 515, 297, 754, 627,
111, 785, 730, 173, 790, 429, 136, 468, 74, 819, 304, 468, 756, 557, 305, 318, 137, 362, 408, 795, 611, 15, 349, 848, 801, 757, 350, 278, 584,
292, 788, 202, 158, 243, 823, 329, 18, 910, 742, 530, 226, 336, 45, 486, 550, 494, 353, 4, 290, 449, 628, 740, 167, 765, 935, 943, 80, 505,
829, 101, 110, 301, 231, 50, 47, 468, 967, 646, 907, 704, 134, 953, 339, 805, 273, 132, 958, 284, 417, 420, 796, 61, 371, 906, 49, 236, 384,
515, 218, 597, 337, 228, 751, 252, 925, 268, 521, 574, 178, 219, 126, 135, 58, 35, 277, 343, 839, 945, 195, 632, 669, 243, 550, 673, 913, 920,
259, 421, 742, 770, 338, 307, 376, 939, 66, 261, 440, 929, 432, 57, 558, 31, 776, 179, 367, 314, 689, 682, 590, 612, 53, 657, 483, 20, 526,
763, 965, 489, 430, 418, 427, 173, 655, 964, 921, 59, 233, 440, 9, 413, 416, 549, 875, 230, 439, 516, 383, 233, 581, 8, 690, 316, 986, 867,
916, 676, 979, 770, 441, 508, 312, 455, 278, 323, 160, 318, 835, 70, 772, 850, 957, 575, 54, 660, 409, 858, 694, 796, 28, 494, 132, 75, 834,
42, 784, 479, 62, 810, 219, 827, 487, 931, 735, 876, 100, 209, 245, 838, 865, 917, 492, 526, 754, 838, 920, 674, 153, 813, 973, 240, 41, 687,
612, 827, 165, 226, 864, 452, 852, 37, 70, 352, 390, 888, 874, 606, 738, 675, 267, 28, 668, 60, 236, 983, 902, 534, 738, 592, 117, 554, 164,
56, 509, 535, 34, 370, 102, 323, 939, 209, 711, 47, 263, 988, 800, 589, 504, 414, 545, 731, 763, 117, 58, 915, 299, 418, 454, 625, 216, 585,
479, 568, 779, 942, 774, 692, 858, 977, 81, 121, 894, 393, 53, 0};
void test1(void) {
jv_rbtree_t *tree = jv_rbtree_create();
/*
41,38,31,12,19,8
82,76,68,50,25,10,8
12,1,9,2,11,7,19,4,15,18,5,14,13,10,16,6,3,8,17
13,2,10,3,1,12,8,20,5,16,19,6,15,14,11,17,7,4,9,18
1,2,4,5,7,8,11,14,15
11,2,14,1,7,15,5,8,4
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
*/
jv_int_t arr[] = {13, 2, 10, 3, 1, 12, 8, 20, 5, 16, 19, 6, 15, 14, 11, 17, 7, 4, 9, 18, 0};
jv_int_t *a = arr;
while (*a != 0) {
jv_rbtree_data_t data;
data.key = *a;
data.value = (void *) *a;
printf("insert value:%lu\n", data.key);
jv_rbtree_insert(tree, &data);
a++;
}
printf("--------------------------traverse 1-----------------------------\n");
jv_rbtree_inorder(tree->root, tree->sentinel);
printf("--------------------------remove 38-----------------------------\n");
printf("min:%lu\n", jv_rbtree_min(tree->root, tree->sentinel)->data->key);
printf("max:%lu\n", jv_rbtree_max(tree->root, tree->sentinel)->data->key);
/* 8,12,19,31,38,41 */
jv_rbtree_remove(tree, jv_rbtree_get(tree, 38));
jv_rbtree_inorder(tree->root, tree->sentinel);
printf("--------------------------remove 31-----------------------------\n");
printf("min:%lu\n", jv_rbtree_min(tree->root, tree->sentinel)->data->key);
printf("max:%lu\n", jv_rbtree_max(tree->root, tree->sentinel)->data->key);
/* 8,12,19,31,38,41 */
jv_rbtree_remove(tree, jv_rbtree_get(tree, 31));
jv_rbtree_inorder(tree->root, tree->sentinel);
printf("--------------------------remove 41-----------------------------\n");
printf("min:%lu\n", jv_rbtree_min(tree->root, tree->sentinel)->data->key);
printf("max:%lu\n", jv_rbtree_max(tree->root, tree->sentinel)->data->key);
/* 8,12,19,31,38,41 */
jv_rbtree_remove(tree, jv_rbtree_get(tree, 41));
jv_rbtree_inorder(tree->root, tree->sentinel);
printf("--------------------------remove 8-----------------------------\n");
/* 8,12,19,31,38,41 */
printf("min:%lu\n", jv_rbtree_min(tree->root, tree->sentinel)->data->key);
printf("max:%lu\n", jv_rbtree_max(tree->root, tree->sentinel)->data->key);
jv_rbtree_remove(tree, jv_rbtree_get(tree, 8));
jv_rbtree_inorder(tree->root, tree->sentinel);
printf("--------------------------remove 12-----------------------------\n");
printf("min:%lu\n", jv_rbtree_min(tree->root, tree->sentinel)->data->key);
printf("max:%lu\n", jv_rbtree_max(tree->root, tree->sentinel)->data->key);
/* 8,12,19,31,38,41 */
jv_rbtree_remove(tree, jv_rbtree_get(tree, 12));
jv_rbtree_inorder(tree->root, tree->sentinel);
printf("--------------------------remove 19-----------------------------\n");
printf("min:%lu\n", jv_rbtree_min(tree->root, tree->sentinel)->data->key);
printf("max:%lu\n", jv_rbtree_max(tree->root, tree->sentinel)->data->key);
/* 8,12,19,31,38,41 */
jv_rbtree_remove(tree, jv_rbtree_get(tree, 19));
jv_rbtree_inorder(tree->root, tree->sentinel);
jv_rbtree_destroy(tree);
}
void test2(void) {
jv_rbtree_t *tree = jv_rbtree_create();
/*
41,38,31,12,19,8
82,76,68,50,25,10,8
12,1,9,2,11,7,19,4,15,18,5,14,13,10,16,6,3,8,17
13,2,10,3,1,12,8,20,5,16,19,6,15,14,11,17,7,4,9,18
1,2,4,5,7,8,11,14,15
11,2,14,1,7,15,5,8,4
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
*/
/* jv_uint_t arr[] = { 6,3,2,5,3,5,1,2,4, 0 }; */
jv_uint_t *a = huge;
while (*a != 0) {
jv_rbtree_data_t data;
data.key = *a;
data.value = (void *) *a;
printf("insert value:%lu\n", data.key);
jv_rbtree_insert(tree, &data);
a++;
}
printf("min:%lu\n", jv_rbtree_min(tree->root, tree->sentinel)->data->key);
printf("max:%lu\n", jv_rbtree_max(tree->root, tree->sentinel)->data->key);
printf("depth:%lu\n", jv_rbtree_depth(tree->root, tree->sentinel));
printf("length:%lu\n", tree->length);
printf("--------------------------traverse 1-----------------------------\n");
jv_rbtree_inorder(tree->root, tree->sentinel);
printf("--------------------------remove 14-----------------------------\n");
/* 11,2,14,1,7,15,5,8,4 */
jv_rbtree_remove(tree, jv_rbtree_get(tree, 7));
jv_rbtree_inorder(tree->root, tree->sentinel);
jv_rbtree_destroy(tree);
}
void test3(void) {
jv_rbtree_t *tree = jv_rbtree_create();
jv_uint_t arr[] = { 6,3,2,5,3,5,1,2,4, 0 };
jv_uint_t *a=arr;
while (*a != 0) {
jv_rbtree_data_t data;
data.key = *a;
data.value = (void *) *a;
printf("insert value:%lu\n", data.key);
jv_rbtree_insert(tree, &data);
a++;
}
printf("min:%lu\n", jv_rbtree_min(tree->root, tree->sentinel)->data->key);
printf("max:%lu\n", jv_rbtree_max(tree->root, tree->sentinel)->data->key);
printf("depth:%lu\n", jv_rbtree_depth(tree->root, tree->sentinel));
printf("length:%lu\n", tree->length);
jv_rbtree_inorder(tree->root, tree->sentinel);
jv_rbtree_remove(tree, jv_rbtree_get(tree, 7));
jv_rbtree_inorder(tree->root, tree->sentinel);
jv_rbtree_destroy(tree);
}
int main(int argc, char *argv[]) {
test1();
test2();
test3();
return 0;
}