rendered paste body#include <stdio.h>#include <stdlib.h>#include <string.h>#include "rbt.h"typedef enum colour_e { RED, BLACK } colour_t;struct rbtnode { char *key; colour_t colour; rbt left; rbt right;};#define IS_BLACK(x) ((NULL == (x)) || (BLACK == (x)->colour))#define IS_RED(x) ((NULL != (x)) && (RED == (x)->colour))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;}rbt rbt_new() { return NULL;}static rbt rbt_right_rotate(rbt r) { rbt tmp; tmp = r; r = r->left; tmp->left = r->right; r->right = tmp; return r;}static rbt rbt_left_rotate(rbt r) { rbt tmp; tmp = r; r = r->right; tmp->right = r->left; r->left = tmp; return r;}rbt rbt_fix(rbt r) { if (IS_RED(r->left) && IS_RED(r->left->left)) { if (IS_RED(r->right)) { r->colour = RED; r->left->colour = BLACK; r->right->colour = BLACK; return r; } else { r = rbt_right_rotate(r); r->colour = BLACK; r->right->colour = RED; return r; } } else if (IS_RED(r->left) && IS_RED(r->left->right)) { if (IS_RED(r->right)) { r->colour = RED; r->left->colour = BLACK; r->right->colour = BLACK; return r; } else { r->left = rbt_left_rotate(r->left); r = rbt_right_rotate(r); r->colour = BLACK; r->right->colour = RED; return r; } } else if (IS_RED(r->right) && IS_RED(r->right->left)) { if (IS_RED(r->left)) { r->colour = RED; r->left->colour = BLACK; r->right->colour = BLACK; return r; } else { r->right = rbt_right_rotate(r->right); r = rbt_left_rotate(r); r->colour = BLACK; r->left->colour = RED; return r; } } else if (IS_RED(r->right) && IS_RED(r->right->right)) { if (IS_RED(r->left)) { r->colour = RED; r->left->colour = BLACK; r->right->colour = BLACK; return r; } else { r = rbt_left_rotate(r); r->colour = BLACK; r->left->colour = RED; return r; } } return r;}int rbt_search(rbt b, char *key) { if (b == NULL) { return 0; } else if (strcmp(b->key, key) == 0) { return 1; } else if (strcmp(b->key, key) > 0) { return rbt_search(b->left, key); } else if (strcmp(b->key, key) < 0) { return rbt_search(b->right, key); } else { return 0; }}rbt rbt_insert(rbt b, char *key) { if (b == NULL) { b = erealloc(NULL, sizeof *b); b->key = erealloc(NULL, sizeof b->key[0] * strlen(key) + 1); b->colour = RED; strcpy(b->key, key); b->right = b->left = NULL; return b; } else if (strcmp(b->key, key) == 0) { return b; } else if (strcmp(b->key, key) > 0) { b->left = rbt_insert(b->left, key); } else if (strcmp(b->key, key) < 0) { b->right = rbt_insert(b->right, key); } b = rbt_fix(b); return b;}void print_key(char *s) { printf("%s\n", s);}void rbt_inorder(rbt b, void f(char *key)) { if (b == NULL) { return; } else { rbt_inorder(b->left, f); f(b->key); rbt_inorder(b->right, f); }}void rbt_preorder(rbt b, void f(char *key)) { if (b == NULL) { return; } else { if (IS_RED(b)) { printf("Red:"); } else { printf("Black:"); } f(b->key); rbt_preorder(b->left, f); rbt_preorder(b->right, f); }}rbt find_successor(rbt b) { if (b == NULL) { return b; } else if (b->left == NULL) { return b; } else if (b->left != NULL) { return find_successor(b->left); } return b;}rbt rbt_remove(rbt b, char *s) { rbt successor; char *tmp; if (b == NULL) { return b; } else if (strcmp(b->key, s) == 0) { if (b->left == NULL && b->right == NULL) { free(b->key); free(b); b = NULL; return b; } else if (b->left != NULL && b->right == NULL) { successor = b->left; free(b->key); free(b); b = successor; return b; } else if (b->left == NULL && b->right != NULL) { successor = b->right; free(b->key); free(b); b = successor; return b; } else { successor = find_successor(b->right); tmp = successor->key; successor->key = b->key; b->key = tmp; b->right = rbt_remove(b->right, s); return b; } } else if (strcmp(b->key, s) > 0) { b->left = rbt_remove(b->left, s); } else if (strcmp(b->key, s) < 0) { b->right = rbt_remove(b->right, s); } return b;}rbt rbt_delete(rbt b) { if (b == NULL) { free(b); } else { rbt_delete(b->left); rbt_delete(b->right); free(b->key); free(b); } return b;}