master
1#include "rb_tree.h"
2#include <cgreen/cgreen.h>
3#include <string.h>
4/*
5 * Every node has a colour. red or black
6 * Root of the tree is always black.
7 * There are no two adjacent red nodes. (red node cannot have red parent or
8child)
9 * Every path from root to child NULL node has same # of black nodes.
10 *
11 *
12 * 1. every node is coloured red or black.
13 * 2. All leaves (nils) are black.
14 * 3. Every red node has black children. black nodes can have any color
15children.
16 * 4. From any node, the # of black nodes on any path to the leaves is the same.
17(same # of black nodes from top to bottom)
18
19height: logn if perfectly balanced.
20
21 (B)
22 / \
23 (R) (R)
24 / \ / \
25 (B) (B) (B) (B)
26 / \
27(nil) (nil)
28 */
29
30Ensure(initialize_returns_a_new_tree) {
31 RBTree *tree = rb_tree_initialize(10);
32
33 assert_that(tree, is_not_equal_to(NULL));
34 assert_that(tree->value, is_equal_to(10));
35 assert_that(tree->colour, is_equal_to(black));
36}
37
38Ensure(insert_returns_a_new_tree_when_null) {
39 RBTree *tree = rb_tree_insert(NULL, 20);
40
41 assert_that(tree, is_not_equal_to(NULL));
42 assert_that(tree->value, is_equal_to(20));
43 assert_that(tree->colour, is_equal_to(black));
44}
45
46Ensure(insert_adds_a_new_item_to_right_subtree) {
47 RBTree *tree = rb_tree_initialize(10);
48
49 tree = rb_tree_insert(tree, 20);
50
51 assert_that(tree, is_not_equal_to(NULL));
52 assert_that(tree->value, is_equal_to(10));
53 assert_that(tree->colour, is_equal_to(black));
54 assert_that(tree->right, is_not_equal_to(NULL));
55 assert_that(tree->right->value, is_equal_to(20));
56}
57
58Ensure(insert_adds_a_new_item_to_left_subtree) {
59 RBTree *tree = rb_tree_initialize(20);
60
61 tree = rb_tree_insert(tree, 10);
62
63 assert_that(tree, is_not_equal_to(NULL));
64 assert_that(tree->value, is_equal_to(20));
65 assert_that(tree->colour, is_equal_to(black));
66 assert_that(tree->left, is_not_equal_to(NULL));
67 assert_that(tree->left->value, is_equal_to(10));
68}
69
70Ensure(rb_tree_insert_performs_a_right_rotation) {
71 /*
72 (30) (20:b)
73 / / \
74 (20) -> (10:r) (30:r)
75 /
76 (10)
77
78 */
79 RBTree *tree = rb_tree_initialize(30);
80
81 tree = rb_tree_insert(tree, 20);
82 tree = rb_tree_insert(tree, 10);
83
84 assert_that(tree, is_not_equal_to(NULL));
85 assert_that(tree->value, is_equal_to(20));
86 assert_that(tree->colour, is_equal_to(black));
87
88 assert_that(tree->left->value, is_equal_to(10));
89 assert_that(tree->left->colour, is_equal_to(red));
90
91 assert_that(tree->right->value, is_equal_to(30));
92 assert_that(tree->right->colour, is_equal_to(red));
93
94 assert_that(rb_tree_is_valid(tree), is_equal_to(true));
95}
96
97Ensure(rb_tree_insert_performs_a_left_rotation) {
98 /*
99 (10) (20:b)
100 \ / \
101 (20) -> (10:r) (30:r)
102 \
103 (30)
104 */
105
106 RBTree *tree = rb_tree_initialize(10);
107 tree = rb_tree_insert(tree, 20);
108 tree = rb_tree_insert(tree, 30);
109
110 assert_that(tree, is_not_equal_to(NULL));
111 assert_that(tree->value, is_equal_to(20));
112 assert_that(tree->colour, is_equal_to(black));
113 assert_that(tree->left->value, is_equal_to(10));
114 assert_that(tree->left->colour, is_equal_to(red));
115 assert_that(tree->right->value, is_equal_to(30));
116 assert_that(tree->right->colour, is_equal_to(red));
117
118 assert_that(rb_tree_is_valid(tree), is_equal_to(true));
119}
120
121Ensure(rb_tree_insert_repaints_the_new_node) {
122 /*
123 (20:b) (20:b)
124 / \ / \
125 (10:r) (30:r) --> (10:b) (30:b)
126 / /
127 (5:r) (5:r)
128 */
129
130 RBTree *tree = rb_tree_initialize(20);
131 tree = rb_tree_insert(tree, 10);
132 tree = rb_tree_insert(tree, 30);
133 tree = rb_tree_insert(tree, 5);
134
135 assert_that(tree, is_not_equal_to(NULL));
136 assert_that(tree->value, is_equal_to(20));
137 assert_that(tree->colour, is_equal_to(black));
138
139 assert_that(tree->left->value, is_equal_to(10));
140 assert_that(tree->left->colour, is_equal_to(black));
141
142 assert_that(tree->left->left->value, is_equal_to(5));
143 assert_that(tree->left->left->colour, is_equal_to(red));
144
145 assert_that(tree->right->value, is_equal_to(30));
146 assert_that(tree->right->colour, is_equal_to(black));
147
148 assert_that(rb_tree_is_valid(tree), is_equal_to(true));
149}
150
151Ensure(rb_tree_insert_handles_large_trees) {
152 RBTree *tree = NULL;
153 int n = 100;
154
155 for (int i = n; i > 0; i--)
156 tree = rb_tree_insert(tree, i);
157
158 assert_that(tree, is_not_equal_to(NULL));
159 assert_that(tree->value, is_equal_to(69));
160 assert_that(tree->colour, is_equal_to(black));
161
162 assert_that(rb_tree_size(tree), is_equal_to(n));
163 assert_that(rb_tree_is_valid(tree), is_equal_to(true));
164}
165
166Ensure(equals_returns_false_when_tree_is_NULL) {
167 assert_that(rb_equals(NULL, rb_tree_initialize(10)), is_equal_to(false));
168}
169
170Ensure(equals_returns_false_when_other_tree_is_NULL) {
171 assert_that(rb_equals(rb_tree_initialize(10), NULL), is_equal_to(false));
172}
173
174Ensure(equals_returns_true_when_both_trees_are_NULL) {
175 assert_that(rb_equals(NULL, NULL), is_equal_to(true));
176}
177
178Ensure(equals_returns_false_when_tree_has_one_node) {
179 RBTree *tree = rb_tree_initialize(20);
180 RBTree *other_tree = rb_tree_initialize(10);
181
182 assert_that(rb_equals(tree, other_tree), is_equal_to(false));
183}
184
185Ensure(equals_returns_false_when_tree_has_one_node_with_different_colours) {
186 RBTree *tree = rb_tree_initialize(20);
187 RBTree *other_tree = rb_tree_initialize(20);
188
189 tree->colour = black;
190 other_tree->colour = red;
191
192 assert_that(rb_equals(tree, other_tree), is_equal_to(false));
193}
194
195Ensure(equals_returns_true_when_tree_has_one_node) {
196 RBTree *tree = rb_tree_initialize(20);
197 RBTree *other_tree = rb_tree_initialize(20);
198
199 assert_that(rb_equals(tree, other_tree), is_equal_to(true));
200}
201
202Ensure(equals_returns_true_when_root_and_left_subtree_are_equal) {
203 RBTree *tree = rb_tree_initialize(20);
204 tree = rb_tree_insert(tree, 10);
205
206 RBTree *other_tree = rb_tree_initialize(20);
207 other_tree = rb_tree_insert(other_tree, 10);
208
209 assert_that(rb_equals(tree, other_tree), is_equal_to(true));
210}
211
212Ensure(equals_returns_false_when_root_and_left_subtree_are_not_equal) {
213 RBTree *tree = rb_tree_initialize(20);
214 tree = rb_tree_insert(tree, 10);
215
216 RBTree *other_tree = rb_tree_initialize(20);
217 other_tree = rb_tree_insert(other_tree, 15);
218
219 assert_that(rb_equals(tree, other_tree), is_equal_to(false));
220}
221
222Ensure(equals_returns_false_when_root_and_right_subtree_are_not_equal) {
223 RBTree *tree = rb_tree_initialize(20);
224 tree = rb_tree_insert(tree, 30);
225
226 RBTree *other_tree = rb_tree_initialize(20);
227 other_tree = rb_tree_insert(other_tree, 25);
228
229 assert_that(rb_equals(tree, other_tree), is_equal_to(false));
230}
231
232Ensure(equals_returns_false_when_parent_is_not_equal) {
233 RBTree *tree = rb_tree_initialize(20);
234 tree = rb_tree_insert(tree, 30);
235
236 RBTree *other_tree = rb_tree_initialize(20);
237 other_tree = rb_tree_insert(other_tree, 30);
238
239 other_tree->right->parent = NULL;
240
241 assert_that(rb_equals(tree, other_tree), is_equal_to(false));
242 assert_that(rb_equals(other_tree, tree), is_equal_to(false));
243}
244
245Ensure(is_valid_returns_false_when_root_is_red) {
246 RBTree *tree = rb_tree_initialize(20);
247 tree->colour = red;
248
249 assert_that(rb_tree_is_valid(tree), is_equal_to(false));
250}
251
252Ensure(is_valid_returns_false_when_red_node_has_red_child) {
253 RBTree *tree = NULL;
254
255 for (int i = 10; i > 0; i--)
256 tree = rb_tree_insert(tree, i);
257
258 tree->left->colour = red;
259 tree->left->left->colour = red;
260
261 assert_that(rb_tree_is_valid(tree), is_equal_to(false));
262}
263
264Ensure(
265 is_valid_returns_false_when_each_path_to_leaves_does_not_contain_the_same_number_of_black_nodes) {
266 RBTree *tree = NULL;
267
268 for (int i = 10; i > 0; i--)
269 tree = rb_tree_insert(tree, i);
270
271 tree->left->left->colour = black;
272 assert_that(rb_tree_is_valid(tree), is_equal_to(false));
273}
274
275Ensure(is_valid_return_true) {
276 RBTree *tree = NULL;
277
278 for (int i = 0; i < 100; ++i)
279 tree = rb_tree_insert(tree, i);
280
281 assert_that(rb_tree_is_valid(tree), is_equal_to(true));
282}
283
284Ensure(height_returns_one) {
285 assert_that(rb_tree_height(NULL), is_equal_to(1));
286}
287
288Ensure(height_returns_three_when_left_subtree_is_present) {
289 RBTree *tree = rb_tree_initialize(10);
290 tree = rb_tree_insert(tree, 5);
291
292 assert_that(rb_tree_height(tree), is_equal_to(3));
293}
294
295Ensure(height_returns_three_when_right_subtree_is_present) {
296 RBTree *tree = rb_tree_initialize(10);
297 tree = rb_tree_insert(tree, 15);
298
299 assert_that(rb_tree_height(tree), is_equal_to(3));
300}
301
302TestSuite *rb_tree_tests() {
303 TestSuite *x = create_test_suite();
304
305 add_test(x, initialize_returns_a_new_tree);
306
307 add_test(x, insert_returns_a_new_tree_when_null);
308 add_test(x, insert_adds_a_new_item_to_right_subtree);
309 add_test(x, insert_adds_a_new_item_to_left_subtree);
310 add_test(x, rb_tree_insert_performs_a_right_rotation);
311 add_test(x, rb_tree_insert_performs_a_left_rotation);
312 add_test(x, rb_tree_insert_repaints_the_new_node);
313 add_test(x, rb_tree_insert_handles_large_trees);
314
315 add_test(x, equals_returns_false_when_tree_is_NULL);
316 add_test(x, equals_returns_false_when_other_tree_is_NULL);
317 add_test(x, equals_returns_true_when_both_trees_are_NULL);
318 add_test(x, equals_returns_false_when_tree_has_one_node);
319 add_test(x,
320 equals_returns_false_when_tree_has_one_node_with_different_colours);
321 add_test(x, equals_returns_true_when_tree_has_one_node);
322 add_test(x, equals_returns_true_when_root_and_left_subtree_are_equal);
323 add_test(x, equals_returns_false_when_root_and_left_subtree_are_not_equal);
324 add_test(x, equals_returns_false_when_root_and_right_subtree_are_not_equal);
325 add_test(x, equals_returns_false_when_parent_is_not_equal);
326
327 add_test(x, is_valid_returns_false_when_root_is_red);
328 add_test(x, is_valid_returns_false_when_red_node_has_red_child);
329 add_test(
330 x,
331 is_valid_returns_false_when_each_path_to_leaves_does_not_contain_the_same_number_of_black_nodes);
332 add_test(x, is_valid_return_true);
333
334 add_test(x, height_returns_one);
335 add_test(x, height_returns_three_when_left_subtree_is_present);
336 add_test(x, height_returns_three_when_right_subtree_is_present);
337 return x;
338}