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
|
#include "avl_tree.h"
#include <cgreen/cgreen.h>
#include <string.h>
Ensure(initialize_returns_new_tree) {
AVLTree *tree = avl_tree_initialize(1);
assert_that(tree, is_not_equal_to(NULL));
}
Ensure(size_returns_zero) {
AVLTree *tree = avl_tree_initialize(1);
assert_that(avl_tree_size(tree), is_equal_to(1));
}
Ensure(insert_changes_size) {
AVLTree *tree = avl_tree_initialize(5);
avl_tree_insert(tree, 4);
assert_that(avl_tree_size(tree), is_equal_to(2));
}
Ensure(insert_changes_height) {
AVLTree *tree = avl_tree_initialize(5);
tree = avl_tree_insert(tree, 4);
assert_that(tree->height, is_equal_to(2));
assert_that(tree->left->height, is_equal_to(1));
}
Ensure(insert_performs_a_left_rotation) {
/*
(10) (20)
\ / \
(20) -> (10) (30)
\
(30)
*/
AVLTree *tree = avl_tree_initialize(10);
tree = avl_tree_insert(tree, 20);
tree = avl_tree_insert(tree, 30);
assert_that(tree->value, is_equal_to(20));
assert_that(tree->left->value, is_equal_to(10));
assert_that(tree->right->value, is_equal_to(30));
};
Ensure(insert_performs_a_right_rotation) {
/*
(30) (20)
/ / \
(20) --> (10) (30)
/
(10)
*/
AVLTree *tree = avl_tree_initialize(30);
tree = avl_tree_insert(tree, 20);
tree = avl_tree_insert(tree, 10);
assert_that(tree->value, is_equal_to(20));
assert_that(tree->left->value, is_equal_to(10));
assert_that(tree->right->value, is_equal_to(30));
}
TestSuite *avl_tree_tests() {
TestSuite *suite = create_test_suite();
add_test(suite, initialize_returns_new_tree);
add_test(suite, size_returns_zero);
add_test(suite, insert_changes_size);
add_test(suite, insert_changes_height);
add_test(suite, insert_performs_a_left_rotation);
add_test(suite, insert_performs_a_right_rotation);
return suite;
}
int main(int argc, char **argv) {
TestSuite *suite = create_test_suite();
add_suite(suite, avl_tree_tests());
return run_test_suite(suite, create_text_reporter());
}
|
