master
1#include "avl_tree.h"
2#include <stdio.h>
3#include <stdlib.h>
4
5/**
6 * Print a visual representation of an AVL Tree.
7 *
8 * @param tree The subtree to print
9 * @param level The level in the tree that this subtree is in
10 */
11static void print_tree(AVLTree *tree, int level) {
12 for (int i = 0; i < level; i++)
13 printf(" ");
14
15 if (tree) {
16 printf("(%d:%d)\n", tree->value, tree->height);
17
18 if (!tree->left && !tree->right)
19 return;
20 print_tree(tree->left, level + 1);
21 print_tree(tree->right, level + 1);
22 } else {
23 printf("( )\n");
24 }
25}
26
27/*
28 * Determines if a integer value is evenly divisibly by 2.
29 *
30 * @param value The integer to check
31 * @return true when the value is even otherwise false
32 */
33static bool is_even(int value) { return value % 2 == 0; }
34
35/*
36 * Determines if a integer value is an odd number
37 *
38 * @param value The integer to check
39 * @return true when the value is odd otherwise false
40 */
41static bool is_odd(int value) { return !is_even(value); }
42
43/**
44 * Converts an AVL tree to a Red Black tree with all
45 * nodes in the tree coloured black.
46 *
47 * @param tree The AVL subtree to convert
48 * @param parent The parent node of the current subtree. Use NULL for the root.
49 * @return The converted Red Black tree
50 */
51static RBTree *to_rb_tree(AVLTree *tree, AVLTree *parent) {
52 if (!tree)
53 return NULL;
54
55 RBTree *rb_tree = rb_tree_initialize(tree->value);
56
57 rb_tree->left = to_rb_tree(tree->left, tree);
58 if (rb_tree->left)
59 rb_tree->left->parent = rb_tree;
60
61 rb_tree->right = to_rb_tree(tree->right, tree);
62 if (rb_tree->right)
63 rb_tree->right->parent = rb_tree;
64 return rb_tree;
65}
66
67/**
68 * Applies the correct colouring to each descendant node in a Red Black tree.
69 *
70 * @param tree The Red Black subtree to colour
71 * @param colour The colour to apply to the provided subtree node.
72 */
73static void change_colour(RBTree *tree, enum Colour colour) {
74 if (!tree)
75 return;
76
77 int l = rb_tree_height(tree->left);
78 int r = rb_tree_height(tree->right);
79
80 tree->colour = colour;
81 change_colour(tree->left, l < r || is_odd(l) ? black : red);
82 change_colour(tree->right, r < l || is_odd(r) ? black : red);
83}
84
85/**
86 * Returns the larger integer between the two provided as arguments.
87 *
88 * @param a An integer value to compare
89 * @param b Another integer value to compare
90 * @return Returns the larger value
91 */
92static int max(int a, int b) { return (a > b) ? a : b; }
93
94/**
95 * Returns the height of an AVL subtree.
96 *
97 * @param tree The subtree to interrogate.
98 * @return The height of the subtree
99 */
100static int height_of(AVLTree *tree) { return tree == NULL ? 0 : tree->height; }
101
102/**
103 * Returns the smallest value stored in the AVL tree.
104 *
105 * @param tree The subtree to traverse to find the smallest value.
106 * @return The subtree node containing the smallest value in the tree.
107 */
108static AVLTree *smallest(AVLTree *tree) {
109 AVLTree *current = tree;
110
111 while (current && current->left != NULL)
112 current = current->left;
113
114 return current;
115}
116
117/**
118 * Performs a right rotation on an AVL subtree
119 *
120 * @param y The subtree to perform the rotation on
121 * @return The new root after the rotation is performed.
122 */
123static AVLTree *rotate_right(AVLTree *y) {
124 AVLTree *x = y->left;
125 AVLTree *t = x->right;
126
127 x->right = y;
128 y->left = t;
129
130 y->height = max(height_of(y->left), height_of(y->right)) + 1;
131 x->height = max(height_of(x->left), height_of(x->right)) + 1;
132
133 return x;
134}
135
136/**
137 * Performs a left rotation on an AVL subtree
138 *
139 * @param x The subtree to perform the rotation on
140 * @return The new root after the rotation is performed.
141 */
142static AVLTree *rotate_left(AVLTree *x) {
143 AVLTree *y = x->right;
144 AVLTree *t = y->left;
145
146 y->left = x;
147 x->right = t;
148
149 x->height = max(height_of(x->left), height_of(x->right)) + 1;
150 y->height = max(height_of(y->left), height_of(y->right)) + 1;
151
152 return y;
153}
154
155/**
156 * Calculates the balance of a subtree by taking the difference
157 * of the height of the left subtree and the right subtree.
158 *
159 * @param tree The tree to investigate.
160 * @return The balace
161 */
162static int balance_of(AVLTree *tree) {
163 return (tree == NULL) ? 0 : height_of(tree->left) - height_of(tree->right);
164}
165
166/**
167 * Compares two integers and returns -1, 0, 1.
168 * If a is equal to b then 0 is returned.
169 * If a is greater than b then 1 is returned.
170 * If a is less than b then -1 is returned.
171 *
172 * @param a An integer
173 * @param b Another integer
174 * @return Returns 0, 1, or -1.
175 */
176static int compare(int a, int b) { return (a < b) ? -1 : ((a > b) ? 1 : 0); }
177
178/**
179 * Initializes an instance of an AVL tree.
180 *
181 * @param value The value to assign to the new node in the tree.
182 * @return Returns the new AVL tree node instance.
183 */
184AVLTree *avl_tree_initialize(int value) {
185 AVLTree *tree = malloc(sizeof(AVLTree));
186 tree->value = value;
187 tree->left = NULL;
188 tree->right = NULL;
189 tree->height = 1;
190 return tree;
191}
192
193/**
194 * Computes the # of nodes stored in an AVL subtree.
195 *
196 * @param tree The subtree to investigate.
197 * @return Returns the # of descendant nodes found in the subtree.
198 */
199int avl_tree_size(AVLTree *tree) {
200 int total = 0;
201 if (tree == NULL)
202 return total;
203 if (tree->left)
204 total += avl_tree_size(tree->left);
205 if (tree->right)
206 total += avl_tree_size(tree->right);
207 return total + 1;
208}
209
210/**
211 * Inserts a new value into an AVL subtree.
212 *
213 * @param tree The subtree to attempt to insert a new value into.
214 * @param value The value to insert.
215 * @return Returns the new root of the subtree.
216 */
217AVLTree *avl_tree_insert(AVLTree *tree, int value) {
218 if (tree == NULL)
219 return avl_tree_initialize(value);
220
221 switch (compare(value, tree->value)) {
222 case -1:
223 tree->left = avl_tree_insert(tree->left, value);
224 break;
225 case 1:
226 tree->right = avl_tree_insert(tree->right, value);
227 break;
228 default:
229 return tree;
230 }
231
232 tree->height = 1 + max(height_of(tree->left), height_of(tree->right));
233
234 int balance = balance_of(tree);
235 if (balance > 1 && value < tree->left->value)
236 return rotate_right(tree);
237
238 if (balance < -1 && value > tree->right->value)
239 return rotate_left(tree);
240
241 if (balance > 1 && value > tree->left->value) {
242 tree->left = rotate_left(tree->left);
243 return rotate_right(tree);
244 }
245
246 if (balance < -1 && value < tree->right->value) {
247 tree->right = rotate_right(tree->right);
248 return rotate_left(tree);
249 }
250
251 return tree;
252}
253
254/**
255 * Deletes a value from an AVL subtree.
256 *
257 * @param tree The subtree to search to find the value to delete.
258 * @param value The value to search for.
259 * @return Returns the new root of the subtree.
260 */
261AVLTree *avl_tree_delete(AVLTree *tree, int value) {
262 if (tree == NULL)
263 return tree;
264
265 switch (compare(value, tree->value)) {
266 case -1:
267 tree->left = avl_tree_delete(tree->left, value);
268 break;
269 case 1:
270 tree->right = avl_tree_delete(tree->right, value);
271 break;
272 default:
273 if (tree->left && tree->right) {
274 AVLTree *min = smallest(tree->right);
275 tree->value = min->value;
276 tree->right = avl_tree_delete(tree->right, min->value);
277 } else {
278 AVLTree *tmp = tree->left ? tree->left : tree->right;
279
280 if (tmp) {
281 *tree = *tmp;
282 free(tmp);
283 } else {
284 free(tree);
285 return NULL;
286 }
287 }
288 break;
289 }
290
291 tree->height = 1 + max(height_of(tree->left), height_of(tree->right));
292
293 int balance = balance_of(tree);
294 if (balance > 1 && balance_of(tree->left) >= 0)
295 return rotate_right(tree);
296
297 if (balance > 1 && balance_of(tree->left) < 0) {
298 tree->left = rotate_left(tree->left);
299 return rotate_right(tree);
300 }
301
302 if (balance < -1 && balance_of(tree->right) <= 0)
303 return rotate_left(tree);
304
305 if (balance < -1 && balance_of(tree->right) > 0) {
306 tree->right = rotate_right(tree->right);
307 return rotate_left(tree);
308 }
309
310 return tree;
311}
312
313/**
314 * Converts an AVL tree to a Red Black tree.
315 *
316 * @param tree The AVL tree to convert.
317 * @return Returns a new Red Black tree.
318 */
319RBTree *avl_tree_to_rb_tree(AVLTree *tree) {
320 if (!tree)
321 return NULL;
322
323 RBTree *rb_tree = to_rb_tree(tree, NULL);
324 change_colour(rb_tree, black);
325 return rb_tree;
326}
327
328/**
329 * Prints a visual inspection of
330 * an AVL tree for debugging purposes to stdout.
331 *
332 * @param tree The tree to visualize
333 */
334void avl_tree_inspect(AVLTree *tree) { print_tree(tree, 0); }