Concerning Red-Black BST

This post presents the various Red-Black BST functions; functions that are absent can be found in
previous posts on BST(they are the same).

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include "linked_list_bag.c"
/**
* A implemented of red-black bst;
* Reference: Algorithms 4ed, by R. Sedgewick & Kevin Wayne
*/

#ifndef LINKED_RBBST
#define LINKED_RBBST
int* Int(int i) {
    int *p = (int*)malloc(sizeof(*p));
    *p = i;
    return p;
}

char* String(char *s) {
    char *p = (char*)malloc((strlen(s) + 1) * sizeof(*p));
    strcpy(p, s);
    return p;
}

int int_cmp(void *k1, void *k2) { return *(int*)k1 - *(int*)k2; }

int str_cmp(void *k1, void *k2) { return strcmp((char*)k1, (char*)k2); }

#define RED true
#define BLK false
enum RBBSTKeyType {
    RBBSTKeyTypeString = 0,
    RBBSTKeyTypeInt = 1
};

typedef struct RBBSTNodeStruct {
    void *key;
    int value;
    int count;
    bool color;
    struct RBBSTNodeStruct *left, *right;
}*RBBSTNode;

typedef struct RBBSTreeStruct {
    LinkedListBag keys;
    RBBSTNode root;
    enum RBBSTKeyType keyType;
    int (*key_cmp)(void*, void*);
}*RBBSTree;

RBBSTNode RBBSTNodeCreate(void *key, int val, bool color) {
    RBBSTNode x = (RBBSTNode)malloc(sizeof(*x));
    x->key = key;
    x->value = val;
    x->left = x->right = NULL;
    x->count = 1;
    x->color = color;
    return x;
}

void RBBSTNodeRelease(RBBSTNode node) {
    if (node == NULL) return;
    free(node->key);
    free(node);
}

RBBSTree RBBSTreeCreate(enum RBBSTKeyType keyType) {
    RBBSTree rbbst = (RBBSTree)malloc(sizeof(*rbbst));
    rbbst->keyType = keyType;
    rbbst->keys = LinkedListBagCreate();
    rbbst->root = NULL;
    if (keyType == RBBSTKeyTypeString) {
        rbbst->key_cmp = str_cmp;
    } else if (keyType == RBBSTKeyTypeInt) {
        rbbst->key_cmp = int_cmp;
    }
    return rbbst;
}

void RBBSTreeRelease_Internal(RBBSTNode root) {
    if (root == NULL) return;
    if (root->left != NULL) { RBBSTreeRelease_Internal(root->left); }
    if (root->right != NULL) { RBBSTreeRelease_Internal(root->right); }
    RBBSTNodeRelease(root);
}

void RBBSTreeRelease(RBBSTree rbbst) {
    if (rbbst == NULL) return;
    LinkedListBagRelease(rbbst->keys);
    RBBSTreeRelease_Internal(rbbst->root);
    free(rbbst);
}

int RBBSTreeCount_Internal(RBBSTNode node) { return node != NULL ? node->count : 0; }

int RBBSTreeCount(RBBSTree rbbst) { return rbbst != NULL ? RBBSTreeCount_Internal(rbbst->root) : 0; }

bool RBBSTNodeIsRed(RBBSTNode x) { return x!= NULL && x->color; }

RBBSTNode RBBSTreeRotateLeft(RBBSTNode root) {
    RBBSTNode right = root->right;
    root->right = right->left;
    right->left = root;
    right->color = root->color;
    root->color = RED;
    right->count = root->count;
    root->count = 1 + RBBSTreeCount_Internal(root->left) + RBBSTreeCount_Internal(root->right);
    return right;
}

RBBSTNode RBBSTreeRotateRight(RBBSTNode root) {
    RBBSTNode left = root->left;
    root->left = left->right;
    left->right = root;
    left->color = root->color;
    root->color = RED;
    left->count = root->count;
    root->count = 1 + RBBSTreeCount_Internal(root->left) + RBBSTreeCount_Internal(root->right);
    return left;
}

void RBBSTreeFlipColors(RBBSTNode root) { root->left->color = root->right->color = !(root->color = !(root->color)); }

RBBSTNode RBBSTreeSet_Internal(RBBSTree rbbst, RBBSTNode root, void *key, int val) {
    if (root == NULL) { return RBBSTNodeCreate(key, val, RED); }
    
    int cmp = rbbst->key_cmp(key, root->key);
    if (cmp < 0) {
        root->left = RBBSTreeSet_Internal(rbbst, root->left, key, val);
    } else if (cmp > 0) {
        root->right = RBBSTreeSet_Internal(rbbst, root->right, key, val);
    } else {
        root->value = val;
    }
    if (RBBSTNodeIsRed(root->right) && !RBBSTNodeIsRed(root->left)) root = RBBSTreeRotateLeft(root);
    if (RBBSTNodeIsRed(root->left) && RBBSTNodeIsRed(root->left->left)) root = RBBSTreeRotateRight(root);
    if (RBBSTNodeIsRed(root->left) && RBBSTNodeIsRed(root->right)) RBBSTreeFlipColors(root);
    
    root->count = RBBSTreeCount_Internal(root->left) + RBBSTreeCount_Internal(root->right) + 1;
    return root;
}

void RBBSTreeSet(RBBSTree rbbst, void *key, int val) {
    if (key == NULL || rbbst == NULL) return;
    if (rbbst->keyType == RBBSTKeyTypeString) { key = String(key); }
    rbbst->root = RBBSTreeSet_Internal(rbbst, rbbst->root, key, val);
    rbbst->root->color = BLK;
} 

int RBBSTreeGet_Internal(RBBSTree rbbst, RBBSTNode root, void *key) {
    if (root == NULL) return INT_MIN;
    int com = rbbst->key_cmp(key, root->key);
    if (com < 0) {
        return RBBSTreeGet_Internal(rbbst, root->left, key);
    } else if (com == 0) {
        return root->value;
    } else {
        return RBBSTreeGet_Internal(rbbst, root->right, key);
    }
}

int RBBSTreeGet(RBBSTree rbbst, void *key) { return key == NULL || rbbst == NULL || rbbst->root == NULL ? INT_MIN : RBBSTreeGet_Internal(rbbst, rbbst->root, key); }

RBBSTNode RBBSTreeMin(RBBSTNode root) {
    if (root == NULL) return NULL;
    if (root->left != NULL) {
        return RBBSTreeMin(root->left);
    } else {
        return root;
    }
}

RBBSTNode RBBSTreeMax(RBBSTNode root) {
    if (root == NULL) return NULL;
    if (root->right != NULL) {
        return RBBSTreeMax(root->right);
    } else {
        return root;
    }
}

RBBSTNode RBBSTreeBalance(RBBSTNode root) {
    if (RBBSTNodeIsRed(root->right) && !RBBSTNodeIsRed(root->left)) root = RBBSTreeRotateLeft(root);
    if (RBBSTNodeIsRed(root->left) && RBBSTNodeIsRed(root->left->left)) root = RBBSTreeRotateRight(root);
    if (RBBSTNodeIsRed(root->left) && RBBSTNodeIsRed(root->right)) RBBSTreeFlipColors(root);
    
    root->count = RBBSTreeCount_Internal(root->left) + RBBSTreeCount_Internal(root->right) + 1;
    return root;
}

RBBSTNode RBBSTreeMoveRedLeft(RBBSTNode root) {
    RBBSTreeFlipColors(root);
    if (RBBSTNodeIsRed(root->right->left)) {
        root->right = RBBSTreeRotateRight(root->right);
        root = RBBSTreeRotateLeft(root);
    }
    return root;
}

RBBSTNode RBBSTreeDeleteMin_Internal(RBBSTNode root) {
    if (root->left == NULL) {
        RBBSTNodeRelease(root);
        return NULL;
    }
    if (!RBBSTNodeIsRed(root->left) && !RBBSTNodeIsRed(root->left->left)) { root = RBBSTreeMoveRedLeft(root); }
    root->left = RBBSTreeDeleteMin_Internal(root->left);
    return RBBSTreeBalance(root);;
}

void RBBSTreeDeleteMin(RBBSTree rbbst) {
    if (rbbst == NULL || rbbst->root == NULL) return;
    if (!RBBSTNodeIsRed(rbbst->root->left)) { rbbst->root->color = RED; }
    rbbst->root = RBBSTreeDeleteMin_Internal(rbbst->root);
    if (RBBSTreeCount_Internal(rbbst->root) != 0) rbbst->root->color = BLK;
}

RBBSTNode RBBSTreeMoveRedRight(RBBSTNode root) {
    RBBSTreeFlipColors(root);
    if (!RBBSTNodeIsRed(root->left->left)) { root = RBBSTreeRotateRight(root); }
    return root;
}

RBBSTNode RBBSTreeDeleteMax_Internal(RBBSTNode root) {
    if (RBBSTNodeIsRed(root->left)) { root = RBBSTreeRotateRight(root); }
    if (root->right == NULL) {
        RBBSTNodeRelease(root);
        return NULL;
    }
    if (!RBBSTNodeIsRed(root->right) && !RBBSTNodeIsRed(root->right->left)) { root = RBBSTreeMoveRedRight(root); }
    root->right = RBBSTreeDeleteMax_Internal(root->right);
    return RBBSTreeBalance(root);
}

void RBBSTreeDeleteMax(RBBSTree rbbst) {
    if (rbbst == NULL || rbbst->root == NULL) return;
    if (!RBBSTNodeIsRed(rbbst->root->left)) rbbst->root->color = RED;
    rbbst->root = RBBSTreeDeleteMax_Internal(rbbst->root);
    if (rbbst->root != NULL) rbbst->root->color = BLK;
}

RBBSTNode RBBSTreeDelete_Internal(RBBSTree rbbst, RBBSTNode root, void *key) {
    int com = rbbst->key_cmp(key, root->key);
    if (com < 0) {
        if (!RBBSTNodeIsRed(root->left) && !RBBSTNodeIsRed(root->left->left)) { root = RBBSTreeMoveRedLeft(root); }
        root->left = RBBSTreeDelete_Internal(rbbst, root->left, key);
    } else {
        if (RBBSTNodeIsRed(root->left)) { root = RBBSTreeRotateRight(root); }
        if (com == 0 && root->right == NULL) {//last node
            RBBSTNodeRelease(root);
            return NULL;
        }
        if (!RBBSTNodeIsRed(root->right) && !RBBSTNodeIsRed(root->right->left)) { root = RBBSTreeMoveRedRight(root); }
        com = rbbst->key_cmp(key, root->key);
        if (com == 0) {
            RBBSTNode min = RBBSTreeMin(root->right);
            root->value = min->value;
            free(root->key);
            if (rbbst->keyType == RBBSTKeyTypeString) {
                root->key = String(min->key);
            } else if (rbbst->keyType == RBBSTKeyTypeInt) {
                root->key = Int(*(int*)min->key);
            }
            root->right = RBBSTreeDeleteMin_Internal(root->right);
        } else {
            root->right = RBBSTreeDelete_Internal(rbbst, root->right, key);
        }
    }
    return RBBSTreeBalance(root);
}

void RBBSTreeDelete(RBBSTree rbbst, void *key) {
    if (key == NULL || rbbst == NULL || rbbst->root == NULL) return;
    if (!RBBSTNodeIsRed(rbbst->root->left)) { rbbst->root->color = RED; }
    rbbst->root = RBBSTreeDelete_Internal(rbbst, rbbst->root, key);
    if (rbbst->root != NULL) rbbst->root->color = BLK;
}

#define L -1
#define R 1
#define P 0
void RBBSTreePrintLevel(RBBSTree rbbst, RBBSTNode root, int level, int k) {
    if (root == NULL) return;
    int i = level;
    while (i-- > 0) { printf("-"); }
    if (rbbst->keyType == RBBSTKeyTypeString) {
        printf("{%s %s: %i; %i %c %s}\n", k == L ? "'" : "", root->key, root->value, root->count, root->color ? 'R' : 'B', k == R ? "'" : "");
    } else if (rbbst->keyType == RBBSTKeyTypeInt) {
        printf("{%s %i: %i; %i %c %s}\n", k == L ? "'" : "", *(int*)(root->key), root->value, root->count, root->color ? 'R' : 'B', k == R ? "'" : "");
    }
    if (root->left != NULL) { RBBSTreePrintLevel(rbbst, root->left, level + 1, L); }
    if (root->right != NULL) { RBBSTreePrintLevel(rbbst, root->right, level + 1, R); }
}

void RBBSTreePrint(RBBSTree rbbst) {
    if (rbbst == NULL) return;
    RBBSTreePrintLevel(rbbst, rbbst->root, 0, P);
}
#endif