rendered paste body#include <stdio.h>#include <stdlib.h>#include <string.h>#include "tree.h"typedef enum colour_e { RED, BLACK } colour_t;struct treenode { char *key; colour_t colour; tree_type type; tree left; tree right;};#define IS_BLACK(x) ((NULL == (x)) || (BLACK == (x)->colour))#define IS_RED(x) ((NULL != (x)) && (RED == (x)->colour))/** * allocates memory to the given pointer. * */static void *erealloc(void *ptr, size_t s) { ptr = realloc(ptr, s); if (NULL == ptr) { fprintf(stderr, "Can't allocate memory\n"); exit(EXIT_FAILURE); } return ptr;}/** * creates a new tree. * */tree tree_new(tree_type type) { tree t = erealloc(NULL, sizeof *t); t->left = t->right = NULL; t->type = type; t->key = NULL; return t;}static tree tree_right_rotate(tree t) { tree tmp; tmp = t; t = t->left; tmp->left = t->right; t->right = tmp; return t;}static tree tree_left_rotate(tree t) { tree tmp; tmp = t; t = t->right; tmp->right = t->left; t->left = tmp; return t;}tree tree_fix(tree t) { if (IS_RED(t->left) && IS_RED(t->left->left)) { if (IS_RED(t->right)) { t->colour = RED; t->left->colour = BLACK; t->right->colour = BLACK; return t; } else { t = tree_right_rotate(t); t->colour = BLACK; t->right->colour = RED; return t; } } else if (IS_RED(t->left) && IS_RED(t->left->right)) { if (IS_RED(t->right)) { t->colour = RED; t->left->colour = BLACK; t->right->colour = BLACK; return t; } else { t->left = tree_left_rotate(t->left); t = tree_right_rotate(t); t->colour = BLACK; t->right->colour = RED; return t; } } else if (IS_RED(t->right) && IS_RED(t->right->left)) { if (IS_RED(t->left)) { t->colour = RED; t->left->colour = BLACK; t->right->colour = BLACK; return t; } else { t->right = tree_right_rotate(t->right); t = tree_left_rotate(t); t->colour = BLACK; t->left->colour = RED; return t; } } else if (IS_RED(t->right) && IS_RED(t->right->right)) { if (IS_RED(t->left)) { t->colour = RED; t->left->colour = BLACK; t->right->colour = BLACK; return t; } else { t = tree_left_rotate(t); t->colour = BLACK; t->left->colour = RED; return t; } } return t;}int tree_search(tree t, char *key) { if (t == NULL) { return 0; } else if (strcmp(t->key, key) == 0) { return 1; } else if (strcmp(t->key, key) > 0) { return tree_search(t->left, key); } else if (strcmp(t->key, key) < 0) { return tree_search(t->right, key); } else { return 0; }}tree tree_insert(tree t, char *key) { if (t->key == NULL) { t->key = erealloc(NULL, sizeof t->key[0] * strlen(key) + 1); if (t->type == RBT) { t->colour = RED; } strcpy(t->key, key); printf("Inserted key %s\n", t->key); return t; } else if (strcmp(t->key, key) == 0) { return t; } else if (strcmp(t->key, key) > 0) { if (t->left == NULL) { t->left = tree_new(t->type); } t->left = tree_insert(t->left, key); } else if (strcmp(t->key, key) < 0) { if (t->right == NULL) { t->right = tree_new(t->type); } t->right = tree_insert(t->right, key); } if (t->type == RBT) { t = tree_fix(t); } return t;}void print_key(char *s) { printf("%s\n", s);}void tree_inorder(tree t, void f(char *key)) { if (t == NULL) { return; } else { if (t->type == RBT) { if (IS_RED(t)) { printf("Red:"); } else { printf("Black:"); } } tree_inorder(t->left, f); f(t->key); tree_inorder(t->right, f); }}void tree_preorder(tree t, void f(char *key)) { if (t == NULL) { return; } else { if (t->type == RBT) { if (IS_RED(t)) { printf("Red:"); } else { printf("Black:"); } } f(t->key); tree_preorder(t->left, f); tree_preorder(t->right, f); }}tree find_successor(tree t) { if (t == NULL) { return t; } else if (t->left == NULL) { return t; } else if (t->left != NULL) { return find_successor(t->left); } return t;}tree tree_delete(tree t) { if (t == NULL) { free(t); } else { tree_delete(t->left); tree_delete(t->right); free(t->key); free(t); } return t;}