master
1#include "rb_tree.h"
2#include <stdio.h>
3#include <stdlib.h>
4
5/*
6 * Implementation derived from:
7 * * https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion
8 */
9
10/**
11 * Returns the larger integer between the two provided as arguments.
12 *
13 * @param a An integer value to compare
14 * @param b Another integer value to compare
15 * @return Returns the larger value
16 */
17static int max(int a, int b) { return a == b ? a : (a > b ? a : b); }
18
19/**
20 * Number of black nodes to leaf.
21 *
22 * @param tree The node to traverse down to a leaf.
23 * @return the # of black nodes from the given node to a leaf.
24 */
25static int depth(RBTree *tree) {
26 int total = 1;
27
28 while (tree) {
29 if (tree->colour == black)
30 total += 1;
31 tree = tree->left;
32 }
33 return total;
34}
35
36/**
37 * Determines if a provided subtree is the root.
38 *
39 * @param node The subtree to investigate
40 * @param Returns tree when the node is the root otherwise false.
41 */
42static bool is_root(RBTree *node) { return node->parent == NULL; }
43
44/**
45 * Returns the parent node of a node.
46 *
47 * @param node The node to investigate.
48 * @return The parent of the node or NULL.
49 */
50static RBTree *parent_of(RBTree *node) { return node ? node->parent : NULL; }
51
52/**
53 * Returns the root of a subtree
54 *
55 * @param node The subtree to investigate
56 * @return Returns the root of the subtree
57 */
58static RBTree *root_of(RBTree *node) {
59 RBTree *current = node;
60 RBTree *next = parent_of(current);
61
62 while (next) {
63 current = next;
64 next = parent_of(current);
65 }
66 return current;
67}
68
69/**
70 * Returns the grand parent node of a node.
71 *
72 * @param node The node to investigate.
73 * @return The grand parent of the node or NULL.
74 */
75static RBTree *grand_parent_of(RBTree *node) {
76 return parent_of(parent_of(node));
77}
78
79/**
80 * Returns a sibling node of a given node.
81 *
82 * @param node The node to investigate.
83 * @return The sibling of the node or NULL.
84 */
85static RBTree *sibling_of(RBTree *node) {
86 RBTree *parent = parent_of(node);
87
88 if (!parent)
89 return NULL;
90
91 return node == parent->left ? parent->right : parent->left;
92}
93
94/**
95 * Returns a pibling (aunt/uncle) node of a given node.
96 *
97 * @param node The node to investigate.
98 * @return The pibling of the node or NULL.
99 */
100static RBTree *pibling_of(RBTree *node) { return sibling_of(parent_of(node)); }
101
102static void rb_rotate_left(RBTree *tree) {
103 RBTree *tmp = tree->right;
104 RBTree *parent = parent_of(tree);
105
106 tree->right = tmp->left;
107 tmp->left = tree;
108 tree->parent = tmp;
109
110 if (tree->right)
111 tree->right->parent = tree;
112
113 if (parent) {
114 if (tree == parent->left)
115 parent->left = tmp;
116 else if (tree == parent->right)
117 parent->right = tmp;
118 }
119 tmp->parent = parent;
120}
121
122/**
123 * Performs a right rotation on a subtree
124 *
125 * @param tree The subtree to perform the rotation on
126 */
127static void rb_rotate_right(RBTree *tree) {
128 RBTree *tmp = tree->left;
129 RBTree *parent = parent_of(tree);
130
131 tree->left = tmp->right;
132 tmp->right = tree;
133 tree->parent = tmp;
134
135 if (tree->left)
136 tree->left->parent = tree;
137
138 if (parent) {
139 if (tree == parent->left)
140 parent->left = tmp;
141 else if (tree == parent->right)
142 parent->right = tmp;
143 }
144 tmp->parent = parent;
145}
146
147/**
148 * Performs any repairs necessary on a subtree
149 *
150 * @param tree The subtree to perform a repair on
151 */
152static void repair_from(RBTree *tree) {
153 RBTree *parent = parent_of(tree);
154 RBTree *pibling = pibling_of(tree);
155
156 if (parent == NULL || parent->colour == black) {
157 return;
158 }
159
160 if (pibling && pibling->colour == red) {
161 parent->colour = black;
162 pibling->colour = black;
163 RBTree *grand_parent = grand_parent_of(tree);
164 if (grand_parent->parent)
165 grand_parent->colour = red;
166 repair_from(grand_parent_of(tree));
167 } else {
168 RBTree *grand_parent = grand_parent_of(tree);
169
170 if (!grand_parent)
171 return;
172 if (tree == parent->right && parent == grand_parent->left) {
173 rb_rotate_left(parent);
174 } else if (tree == parent->left && parent == grand_parent->right) {
175 rb_rotate_right(parent);
176 tree = tree->right;
177 }
178
179 parent = parent_of(tree);
180 grand_parent = grand_parent_of(tree);
181
182 if (tree == parent->left) {
183 rb_rotate_right(grand_parent);
184 } else {
185 rb_rotate_left(grand_parent);
186 }
187 parent->colour = black;
188 if (grand_parent->parent)
189 grand_parent->colour = red;
190 }
191}
192
193/**
194 * Compares two integers and returns -1, 0, 1.
195 * If a is equal to b then 0 is returned.
196 * If a is greater than b then 1 is returned.
197 * If a is less than b then -1 is returned.
198 *
199 * @param a An integer
200 * @param b Another integer
201 * @return Returns 0, 1, or -1.
202 */
203static int compare(int a, int b) { return a == b ? 0 : a < b ? -1 : 1; }
204
205/**
206 * Inserts a new node into a subtree.
207 *
208 * @param tree The subtree to attempt to insert a new value into.
209 * @param node The new node to insert.
210 */
211static void insert(RBTree *root, RBTree *node) {
212 if (!root)
213 return;
214
215 if (compare(node->value, root->value) < 0) {
216 if (root->left)
217 insert(root->left, node);
218 else {
219 root->left = node;
220 node->parent = root;
221 }
222 } else {
223 if (root->right)
224 insert(root->right, node);
225 else {
226 root->right = node;
227 node->parent = root;
228 }
229 }
230}
231
232/**
233 * Print a visual representation of a tree.
234 *
235 * @param tree The subtree to print
236 * @param level The level in the tree that this subtree is in
237 */
238static void print_tree(RBTree *tree, int level) {
239 for (int i = 0; i < level; i++)
240 printf(" ");
241
242 if (tree) {
243 printf("(%d%c H:%d)\n", tree->value, tree->colour == red ? 'R' : 'B',
244 rb_tree_height(tree));
245
246 if (!tree->left && !tree->right)
247 return;
248 print_tree(tree->left, level + 1);
249 print_tree(tree->right, level + 1);
250 } else {
251 printf("( )\n");
252 }
253}
254
255/**
256 * Initializes an instance of a tree.
257 *
258 * @param value The value to assign to the new node in the tree.
259 * @param color The colour to assign to the new node in the tree.
260 * @return Returns the new tree node instance.
261 */
262RBTree *rb_tree_initialize_with(int value, enum Colour colour) {
263 RBTree *tree = malloc(sizeof(RBTree));
264 tree->colour = colour;
265 tree->left = NULL;
266 tree->parent = NULL;
267 tree->right = NULL;
268 tree->value = value;
269 return tree;
270}
271
272/**
273 * Initializes an instance of a tree with a default colour of black.
274 *
275 * @param value The value to assign to the new node in the tree.
276 * @return Returns the new tree node instance.
277 */
278RBTree *rb_tree_initialize(int value) {
279 return rb_tree_initialize_with(value, black);
280}
281
282/**
283 * Inserts a new value into a subtree.
284 *
285 * @param tree The subtree to attempt to insert a new value into.
286 * @param value The value to insert.
287 * @return Returns the new root of the subtree.
288 */
289RBTree *rb_tree_insert(RBTree *tree, int value) {
290 if (tree == NULL)
291 return rb_tree_initialize(value);
292
293 RBTree *node = rb_tree_initialize_with(value, red);
294 insert(tree, node);
295 repair_from(node);
296 return root_of(node);
297}
298
299/**
300 * Prints a visual inspection of
301 * a tree for debugging purposes to stdout.
302 *
303 * @param tree The tree to visualize
304 */
305void rb_tree_inspect(RBTree *tree) { print_tree(tree, 0); }
306
307int rb_tree_size(RBTree *tree) {
308 int total = 0;
309 if (tree == NULL)
310 return total;
311 if (tree->left)
312 total += rb_tree_size(tree->left);
313 if (tree->right)
314 total += rb_tree_size(tree->right);
315 return total + 1;
316}
317
318/**
319 * Determines if two trees are equal by verifying
320 * that each descendant node in each subtree have
321 * the same value and colour.
322 *
323 * @param tree A tree to compare
324 * @param other_tree Another tree to compare
325 * @return Returns true when both subtrees are equal otherwise false
326 */
327bool rb_equals(RBTree *tree, RBTree *other_tree) {
328 if (!tree || !other_tree)
329 return tree == other_tree;
330
331 if (tree->parent && !other_tree->parent)
332 return false;
333
334 if (!tree->parent && other_tree->parent)
335 return false;
336
337 if (tree->parent && tree->parent->value != other_tree->parent->value)
338 return false;
339
340 return tree->value == other_tree->value &&
341 tree->colour == other_tree->colour &&
342 rb_equals(tree->left, other_tree->left) &&
343 rb_equals(tree->right, other_tree->right);
344}
345
346/**
347 * Determines if a tree matches the properties
348 * necessary to claim to be a valid Red Black tree.
349 *
350 * 1. root must be black
351 * 2. there are the same # of black nodes on every root to the leaf path.
352 * 3. No two red nodes are adjacent.
353 *
354 * @param tree The tree to investigate
355 * @return Returns true if the tree meets the criteria otherwise false.
356 */
357bool rb_tree_is_valid(RBTree *tree) {
358 if (tree == NULL)
359 return true;
360
361 if (is_root(tree) && tree->colour == red)
362 return false;
363
364 if (tree->colour == red && tree->parent->colour == red)
365 return false;
366
367 if (depth(tree->left) != depth(tree->right))
368 return false;
369
370 return rb_tree_is_valid(tree->left) && rb_tree_is_valid(tree->right);
371}
372
373/**
374 * Returns the height of a subtree.
375 *
376 * @param tree The subtree to investigate
377 * @return Returns the height of the subtree
378 */
379int rb_tree_height(RBTree *tree) {
380 if (!tree)
381 return 1;
382
383 return 1 + max(rb_tree_height(tree->left), rb_tree_height(tree->right));
384}
385
386/**
387 * Searches for a node in a subtree with a particular value.
388 *
389 * @param t The subtree to search.
390 * @param value The value to search for
391 * @returns Returns the node containing the value otherwise NULL
392 */
393RBTree *rb_tree_find(RBTree *t, int value) {
394 if (!t)
395 return NULL;
396
397 int x = compare(value, t->value);
398 return x == 0 ? t : rb_tree_find(x < 0 ? t->left : t->right, value);
399}