master
1#include "avl_tree.h"
2#include <cgreen/cgreen.h>
3#include <string.h>
4
5Ensure(initialize_returns_new_tree) {
6 AVLTree *tree = avl_tree_initialize(1);
7 assert_that(tree, is_not_equal_to(NULL));
8}
9
10Ensure(size_returns_zero) {
11 AVLTree *tree = avl_tree_initialize(1);
12
13 assert_that(avl_tree_size(tree), is_equal_to(1));
14}
15
16Ensure(insert_changes_size) {
17 AVLTree *tree = avl_tree_initialize(5);
18 avl_tree_insert(tree, 4);
19
20 assert_that(avl_tree_size(tree), is_equal_to(2));
21}
22
23Ensure(insert_changes_height) {
24 AVLTree *tree = avl_tree_initialize(5);
25 tree = avl_tree_insert(tree, 4);
26
27 assert_that(tree->height, is_equal_to(2));
28 assert_that(tree->left->height, is_equal_to(1));
29}
30
31Ensure(insert_creates_a_new_root) {
32 AVLTree *tree = avl_tree_insert(NULL, 10);
33
34 assert_that(tree, is_not_equal_to(NULL));
35 assert_that(tree->value, is_equal_to(10));
36 assert_that(tree->left, is_equal_to(NULL));
37 assert_that(tree->right, is_equal_to(NULL));
38}
39
40Ensure(insert_performs_a_left_rotation) {
41 /*
42 (10) (20)
43 \ / \
44 (20) -> (10) (30)
45 \
46 (30)
47 */
48 AVLTree *tree = avl_tree_initialize(10);
49 tree = avl_tree_insert(tree, 20);
50 tree = avl_tree_insert(tree, 30);
51
52 assert_that(tree->value, is_equal_to(20));
53 assert_that(tree->left->value, is_equal_to(10));
54 assert_that(tree->right->value, is_equal_to(30));
55};
56
57Ensure(insert_performs_a_right_rotation) {
58 /*
59 (30) (20)
60 / / \
61 (20) --> (10) (30)
62 /
63 (10)
64 */
65 AVLTree *tree = avl_tree_initialize(30);
66 tree = avl_tree_insert(tree, 20);
67 tree = avl_tree_insert(tree, 10);
68
69 assert_that(tree->value, is_equal_to(20));
70 assert_that(tree->left->value, is_equal_to(10));
71 assert_that(tree->right->value, is_equal_to(30));
72}
73
74Ensure(insert_performs_a_left_right_rotation) {
75 /*
76 (30) (20)
77 / / \
78 (10) -> (10) (30)
79 \
80 (20)
81 */
82 AVLTree *tree = avl_tree_initialize(30);
83 tree = avl_tree_insert(tree, 10);
84 tree = avl_tree_insert(tree, 20);
85
86 assert_that(tree->value, is_equal_to(20));
87 assert_that(tree->left->value, is_equal_to(10));
88 assert_that(tree->right->value, is_equal_to(30));
89}
90
91Ensure(insert_performs_a_right_left_rotation) {
92 /*
93 (10) (20)
94 \ / \
95 (30) --> (10) (30)
96 /
97 (20)
98 */
99 AVLTree *tree = avl_tree_initialize(10);
100 tree = avl_tree_insert(tree, 30);
101 tree = avl_tree_insert(tree, 20);
102
103 assert_that(tree->value, is_equal_to(20));
104 assert_that(tree->left->value, is_equal_to(10));
105 assert_that(tree->right->value, is_equal_to(30));
106}
107
108Ensure(delete_handles_left_left_case) {
109 /*
110 (z) (y)
111 / \ / \
112 (y) (T4) (X) (z)
113 / \ --> / \ / \
114 (x) (T3) (T1) (T2) (T3) (T4)
115 / \
116 (T1) (T2)
117
118 Delete (37):
119
120 (30) (20)
121 / \ / \
122 (20) (35) (10) (30)
123 / \ \ --> / \ / \
124 (10) (25) *(37) (5) (15) (25) (35)
125 / \
126 (5) (15)
127 */
128
129 AVLTree *tree = avl_tree_initialize(30);
130 tree = avl_tree_insert(tree, 35);
131 tree = avl_tree_insert(tree, 20);
132 tree = avl_tree_insert(tree, 10);
133 tree = avl_tree_insert(tree, 25);
134 tree = avl_tree_insert(tree, 37);
135 tree = avl_tree_insert(tree, 15);
136 tree = avl_tree_insert(tree, 5);
137
138 tree = avl_tree_delete(tree, 37);
139
140 assert_that(tree, is_not_equal_to(NULL));
141 assert_that(tree->value, is_equal_to(20));
142 assert_that(tree->left->value, is_equal_to(10));
143 assert_that(tree->left->left->value, is_equal_to(5));
144 assert_that(tree->left->right->value, is_equal_to(15));
145
146 assert_that(tree->right->value, is_equal_to(30));
147 assert_that(tree->right->left->value, is_equal_to(25));
148 assert_that(tree->right->right->value, is_equal_to(35));
149}
150
151Ensure(delete_handles_left_right_case) {
152 /*
153 (z) (x)
154 / \ / \
155 (y) (T4) (y) (z)
156 / \ --> / \ / \
157 (T1) (x) (T1) (T2) (T3) (T4)
158 / \
159 (T2) (T3)
160
161 Delete (37):
162
163 (30) (25)
164 / \ / \
165 (20) (35) (20) (30)
166 / \ \ --> / \ / \
167 (10) (25) *(37) (10) (22) (27) (35)
168 / \
169 (22) (27)
170 */
171 AVLTree *tree = avl_tree_initialize(30);
172 tree = avl_tree_insert(tree, 20);
173 tree = avl_tree_insert(tree, 35);
174 tree = avl_tree_insert(tree, 10);
175 tree = avl_tree_insert(tree, 37);
176 tree = avl_tree_insert(tree, 25);
177 tree = avl_tree_insert(tree, 22);
178 tree = avl_tree_insert(tree, 27);
179
180 tree = avl_tree_delete(tree, 37);
181
182 assert_that(tree, is_not_equal_to(NULL));
183 assert_that(tree->value, is_equal_to(25));
184 assert_that(tree->left->value, is_equal_to(20));
185 assert_that(tree->left->left->value, is_equal_to(10));
186 assert_that(tree->left->right->value, is_equal_to(22));
187
188 assert_that(tree->right->value, is_equal_to(30));
189 assert_that(tree->right->left->value, is_equal_to(27));
190 assert_that(tree->right->right->value, is_equal_to(35));
191}
192
193Ensure(delete_handles_right_right_case) {
194 /*
195 (z) (y)
196 / \ / \
197 (T4) (y) (z) (x)
198 / \ --> / \ / \
199 (T3) (x) (T4) (T3) (T2) (T1)
200 / \
201 (T2) (T1)
202
203
204 (20) (30)
205 / \ / \
206 (15) (30) (20) (35)
207 / / \ --> / \ / \
208 *(10) (25) (35) (15) (25) (33) (37)
209 / \
210 (33) (37)
211 */
212 AVLTree *tree = avl_tree_initialize(20);
213
214 tree = avl_tree_insert(tree, 30);
215 tree = avl_tree_insert(tree, 15);
216 tree = avl_tree_insert(tree, 10);
217 tree = avl_tree_insert(tree, 20);
218 tree = avl_tree_insert(tree, 25);
219 tree = avl_tree_insert(tree, 35);
220 tree = avl_tree_insert(tree, 33);
221 tree = avl_tree_insert(tree, 37);
222
223 tree = avl_tree_delete(tree, 10);
224
225 assert_that(tree, is_not_equal_to(NULL));
226 assert_that(tree->value, is_equal_to(30));
227
228 assert_that(tree->left->value, is_equal_to(20));
229 assert_that(tree->left->left->value, is_equal_to(15));
230 assert_that(tree->left->right->value, is_equal_to(25));
231
232 assert_that(tree->right->value, is_equal_to(35));
233 assert_that(tree->right->left->value, is_equal_to(33));
234 assert_that(tree->right->right->value, is_equal_to(37));
235}
236
237Ensure(delete_handles_right_left) {
238 /*
239 (z) (x)
240 / \ / \
241 (T4) (y) (z) (y)
242 / \ / \ / \
243 (x) (T1) --> (T4) (T3) (T2) (T1)
244 / \
245 (T3) (T2)
246
247
248 (20) (22)
249 / \ / \
250 (15) (25) (20) (25)
251 / / \ / \ / \
252 *(10) (22) (30) --> (15) (21) (23) (30)
253 / \
254 (21) (23)
255 */
256
257 AVLTree *tree = avl_tree_initialize(20);
258 tree = avl_tree_insert(tree, 15);
259 tree = avl_tree_insert(tree, 25);
260 tree = avl_tree_insert(tree, 10);
261 tree = avl_tree_insert(tree, 22);
262 tree = avl_tree_insert(tree, 30);
263 tree = avl_tree_insert(tree, 21);
264 tree = avl_tree_insert(tree, 23);
265
266 tree = avl_tree_delete(tree, 10);
267
268 assert_that(tree, is_not_equal_to(NULL));
269 assert_that(tree->value, is_equal_to(22));
270 assert_that(tree->left->value, is_equal_to(20));
271 assert_that(tree->left->left->value, is_equal_to(15));
272 assert_that(tree->left->right->value, is_equal_to(21));
273
274 assert_that(tree->right->value, is_equal_to(25));
275 assert_that(tree->right->left->value, is_equal_to(23));
276 assert_that(tree->right->right->value, is_equal_to(30));
277}
278
279Ensure(delete_handles_a_complicated_and_large_tree) {
280 int items[] = {44, 17, 62, 10, 32, 50, 78, 21, 48,
281 54, 72, 88, 45, 49, 52, 56, 81, 92};
282 unsigned int length = sizeof(items) / sizeof(items[0]);
283 AVLTree *tree = NULL;
284
285 for (int i = 0; i < length; i++)
286 tree = avl_tree_insert(tree, items[i]);
287
288 tree = avl_tree_delete(tree, 32);
289
290 assert_that(tree->value, is_equal_to(62));
291}
292
293Ensure(delete_handles_a_complicated_and_small_tree) {
294 int items[] = {9, 1, 10, 0, 5, 11, -1, 2, 6};
295 unsigned int length = sizeof(items) / sizeof(items[0]);
296 AVLTree *tree = NULL;
297
298 for (int i = 0; i < length; i++)
299 tree = avl_tree_insert(tree, items[i]);
300
301 tree = avl_tree_delete(tree, 10);
302
303 assert_that(tree->value, is_equal_to(1));
304}
305
306Ensure(delete_returns_a_null_root) {
307 AVLTree *tree = avl_tree_delete(NULL, 10);
308
309 assert_that(tree, is_equal_to(NULL));
310}
311
312Ensure(to_rb_tree_returns_a_new_red_black_tree) {
313 /*
314 (20:3) (20:b)
315 / \ --> / \
316 (15:2) (30:2) (15:b) (30:b)
317 / \ \ / \ \
318 (10:1) (17:1) (35:1) (10:r) (17:r) (35:r)
319 */
320 AVLTree *tree = NULL;
321 RBTree *expected = NULL;
322 int items[] = {20, 15, 30, 10, 17, 35};
323 int length = sizeof(items) / sizeof(items[0]);
324
325 for (int i = 0; i < length; i++) {
326 tree = avl_tree_insert(tree, items[i]);
327 expected = rb_tree_insert(expected, items[i]);
328 }
329
330 RBTree *actual = avl_tree_to_rb_tree(tree);
331
332 assert_that(rb_equals(expected, actual), is_equal_to(true));
333 assert_that(rb_tree_is_valid(actual), is_equal_to(true));
334 assert_that(rb_tree_is_valid(expected), is_equal_to(true));
335}
336
337Ensure(to_rb_tree_handles_trees_with_a_large_depth) {
338 AVLTree *subject = NULL;
339 int n = 100;
340
341 for (int i = 0; i < n; i++)
342 subject = avl_tree_insert(subject, i);
343
344 RBTree *actual = avl_tree_to_rb_tree(subject);
345
346 assert_that(rb_tree_is_valid(actual), is_equal_to(true));
347
348 for (int i = 0; i < n; i++) {
349 RBTree *node = rb_tree_find(actual, i);
350
351 assert_that(node, is_not_equal_to(NULL));
352 assert_that(node->value, is_equal_to(i));
353 }
354}
355
356TestSuite *avl_tree_tests() {
357 TestSuite *x = create_test_suite();
358 add_test(x, initialize_returns_new_tree);
359
360 add_test(x, size_returns_zero);
361
362 add_test(x, insert_changes_size);
363 add_test(x, insert_changes_height);
364 add_test(x, insert_creates_a_new_root);
365 add_test(x, insert_performs_a_left_rotation);
366 add_test(x, insert_performs_a_right_rotation);
367 add_test(x, insert_performs_a_left_right_rotation);
368 add_test(x, insert_performs_a_right_left_rotation);
369
370 add_test(x, delete_handles_left_left_case);
371 add_test(x, delete_handles_left_right_case);
372 add_test(x, delete_handles_right_right_case);
373 add_test(x, delete_handles_right_left);
374 add_test(x, delete_handles_a_complicated_and_large_tree);
375 add_test(x, delete_handles_a_complicated_and_small_tree);
376 add_test(x, delete_returns_a_null_root);
377
378 add_test(x, to_rb_tree_returns_a_new_red_black_tree);
379 add_test(x, to_rb_tree_handles_trees_with_a_large_depth);
380 return x;
381}
382
383TestSuite *btree_tests();
384TestSuite *graph_tests();
385TestSuite *matrix_tests();
386TestSuite *meldable_heap_tests();
387TestSuite *rb_tree_tests();
388TestSuite *sort_tests();
389
390int main(int argc, char **argv) {
391 TestSuite *suite = create_test_suite();
392 add_suite(suite, avl_tree_tests());
393 add_suite(suite, btree_tests());
394 add_suite(suite, graph_tests());
395 add_suite(suite, matrix_tests());
396 add_suite(suite, meldable_heap_tests());
397 add_suite(suite, rb_tree_tests());
398 add_suite(suite, sort_tests());
399 return run_test_suite(suite, create_text_reporter());
400}