path: root/il_redblack.cpp

#include "stdio.h"
#include "stdint.h"
#include "assert.h"

#ifndef AMRT_MEMORY
#include "stdlib.h"
#include "string.h"
#define AMRT_MALLOC(X)      malloc((X))
#define AMRT_FREE(X)        free((X))
#define AMRT_MEMZERO(S, N)  memset((S), 0, (N))
#endif

enum AMRT_COLOR {
    AMRT_COLOR_BLACK = 0,
    AMRT_COLOR_RED,
};

enum AMRT_DIR {
    AMRT_DIR_LEFT = 0,
    AMRT_DIR_RIGHT
};

typedef int amrt_status;
typedef int amrt_idx;

#define AMRT_NIL 0;

struct  amrt_rb_node {
    AMRT_COLOR       color;
    AMRT_DIR         dir;
    int              value;
    size_t           __size;
    size_t           __level;
    amrt_idx         parent;
    union {
        amrt_idx     child[2];
        struct {
            amrt_idx left;
            amrt_idx right;
        };
        struct {
            amrt_idx prev;
            amrt_idx next;
        };
    };
};

struct amrt_rb_tree {
    amrt_idx     head;
    amrt_idx     freelist;
    size_t       node_max;
    size_t       node_count;
    amrt_rb_node *nodes;
};

// Core Functions
amrt_rb_tree    amrt_RBInit(size_t max_ele);
amrt_status     amrt_RbInsert(amrt_rb_tree *tree, int value);
size_t          amrt_RBSearch(amrt_rb_tree *tree, int value);
amrt_status     amrt_RBIndexedDelete(amrt_rb_tree *tree, amrt_idx node_idx); 
amrt_status     amrt_RBDelete(amrt_rb_tree *tree, int value);
void            amrt_RBClear(amrt_rb_tree *tree);
void            amrt_RBTerminate(amrt_rb_tree *tree);
void            amrt_RBPrint(amrt_rb_tree *tree);

// Helper Functions
amrt_status amrt__RBFreelistPop(amrt_rb_tree *tree); 
amrt_status amrt__RBFreelistReclaim(amrt_rb_tree *tree, amrt_idx node_idx); 
void        amrt__RBRotateUp(amrt_rb_tree *tree, amrt_idx node_idx);
amrt_idx    amrt__RBSubtreeFindSmallestNode(amrt_rb_tree *tree, amrt_idx node_idx); 
amrt_status amrt__RBIgnoreNode(amrt_rb_tree *tree, amrt_idx node_idx);
void        amrt__RBUpdateLevels(amrt_rb_tree *tree, amrt_idx node_idx, int level); 

// Testing Functions
int         amrt__RBValidateColors(amrt_rb_tree, amrt_idx node_idx);
int         amrt__RBCountNodes(amrt_rb_tree tree, amrt_idx node_idx); 
bool        amrt__RBSetupValid(amrt_rb_tree tree, amrt_idx node_idx);
amrt_status amrt__RBValidate(amrt_rb_tree tree); 


amrt_rb_tree amrt_RBInit(size_t max_ele) {
    amrt_rb_tree tree = {0};
    if (!max_ele) return tree;

    size_t cap = 1 + max_ele; // 1 (index 0) is reserved for nil node
    tree.node_max = cap;
    tree.nodes = (amrt_rb_node*)AMRT_MALLOC(sizeof(amrt_rb_node)*tree.node_max);
    tree.freelist = tree.head + 1;

    amrt_rb_node free = tree.nodes[tree.freelist];
    free.__size = max_ele - tree.freelist;
    tree.nodes[tree.freelist] = free;

    return tree;
}

amrt_status amrt_RBInsert(amrt_rb_tree *tree, int value) {
    amrt_idx search_idx = tree->head;
    amrt_rb_node search_node = tree->nodes[search_idx];
    amrt_idx parent_idx = search_node.parent;
    AMRT_DIR search_dir = search_node.dir;

    // @step: find index for node insertion
    while(search_idx) {
        parent_idx = search_idx;
        if (value < search_node.value) {
            search_idx = search_node.left;
            search_dir = AMRT_DIR_LEFT;
        } else {
            search_idx = search_node.right;
            search_dir = AMRT_DIR_RIGHT;
        }
        search_node = tree->nodes[search_idx];
    }

    // @step: 
    // pop slot from free list
    amrt_idx node_idx = amrt__RBFreelistPop(tree);
    amrt_rb_node node = {};
    node.value = value;
    node.dir = search_dir;
    node.color = AMRT_COLOR_BLACK;
    node.parent = parent_idx;
    node.left = AMRT_NIL;
    node.right = AMRT_NIL;
    tree->nodes[node_idx] = node;

    // update parent
    amrt_rb_node parent = tree->nodes[parent_idx];
    if (parent_idx) {
        parent.child[node.dir] = node_idx;
        tree->nodes[parent_idx] = parent;
    }

    tree->node_count++;


    // @step: color node
    int colored = 0;
    while (!colored) {
        if (!parent_idx) {
            tree->head = node_idx;
            colored = 1;
        } else if (parent.color == AMRT_COLOR_BLACK) {
            node.color = AMRT_COLOR_RED;
            tree->nodes[node_idx] = node;
            colored = 1;
        } else if (parent.color == AMRT_COLOR_RED) {
            amrt_idx grandparent_idx = parent.parent;
            amrt_rb_node grandparent = tree->nodes[grandparent_idx];
            AMRT_DIR unc_dir = (AMRT_DIR)!parent.dir;
            amrt_idx unc_idx = grandparent.child[unc_dir];
            amrt_rb_node uncle = tree->nodes[unc_idx];
            if (unc_idx && uncle.color == AMRT_COLOR_RED) {
                node.color = AMRT_COLOR_RED;
                parent.color = AMRT_COLOR_BLACK;
                uncle.color = AMRT_COLOR_BLACK;

                tree->nodes[node_idx] = node;
                tree->nodes[parent_idx] = parent;
                tree->nodes[unc_idx] = uncle;

                // update variables for node n-2
                node_idx = grandparent_idx;
                node = grandparent;
                parent_idx = grandparent.parent;
                parent = tree->nodes[parent_idx];

                // not needed but signifies that we will loop again
                colored = 0; 

            } else {
                if (node.dir != parent.dir) {
                    // node near uncle 
                    amrt__RBRotateUp(tree, node_idx);
                    // get updated node
                    node = tree->nodes[node_idx];
                    parent_idx = node.parent;
                    amrt__RBRotateUp(tree, node_idx);
                    // get update node
                    node = tree->nodes[node_idx];
                    amrt_idx old_parent_idx = parent_idx;
                    amrt_rb_node old_parent = tree->nodes[old_parent_idx];

                    // update colors
                    node.color = AMRT_COLOR_BLACK;
                    old_parent.color = AMRT_COLOR_RED;
                    tree->nodes[node_idx] = node;
                    tree->nodes[old_parent_idx] = old_parent;

                    colored = 1;

                } else {
                    // node away from uncle
                    amrt__RBRotateUp(tree, parent_idx);
                    // get update nodes
                    grandparent = tree->nodes[grandparent_idx];
                    parent = tree->nodes[parent_idx];
                    node = tree->nodes[node_idx];
                    
                    // update colors
                    parent.color = AMRT_COLOR_BLACK;
                    grandparent.color = AMRT_COLOR_RED;
                    node.color = AMRT_COLOR_RED;

                    tree->nodes[node_idx] = node;
                    tree->nodes[parent_idx] = parent;
                    tree->nodes[grandparent_idx] = grandparent;

                    colored = 1;

                }
            }
        }
    }

    // @step: update head
    amrt_idx head_idx = tree->head;
    amrt_rb_node head = tree->nodes[head_idx];
    while(head.parent) {
        head_idx = head.parent;
        head = tree->nodes[head_idx];
    }
    tree->head = head_idx;

    return 0;
}

amrt_idx amrt_RBSearch(amrt_rb_tree tree, int to_find) {
    amrt_idx node_idx = tree.head;
    amrt_idx to_find_idx = AMRT_NIL;

    while (node_idx && !to_find_idx) {
        amrt_rb_node node = tree.nodes[node_idx];
        if (to_find == node.value) {
            to_find_idx = node_idx;
        } else if (to_find < node.value) {
            node_idx = node.left;
        } else {
            node_idx = node.right;
        }
    }

    return to_find_idx;
}

amrt_status amrt_RBDelete(amrt_rb_tree *tree, int to_delete) {
    amrt_idx idx = amrt_RBSearch(*tree, to_delete);
    amrt_status status = amrt_RBIndexedDelete(tree, idx);
    return status;
}

amrt_status amrt_RBIndexedDelete(amrt_rb_tree *tree, amrt_idx node_idx) {
    if (!node_idx) return 0;

    amrt_rb_node node = tree->nodes[node_idx];

    if (node.left && node.right) {
        // @step: both child present, narrow down to case of 1 or no child
        amrt_idx right_smallest_idx = amrt__RBSubtreeFindSmallestNode(tree, node.right);

        if (right_smallest_idx) {
            // replace node with smallest node
            amrt_rb_node right_smallest = tree->nodes[right_smallest_idx];
            node.value = right_smallest.value;
            tree->nodes[node_idx] = node;

            node_idx = right_smallest_idx;
            node = right_smallest;
        }
    }

    bool colored = false;
    while (!colored) {
        AMRT_DIR child_dir = node.left ? AMRT_DIR_LEFT : AMRT_DIR_RIGHT;
        amrt_idx parent_idx = node.parent;
        amrt_idx child_idx = node.child[child_dir];
        amrt_rb_node parent = tree->nodes[parent_idx];
        amrt_rb_node child = tree->nodes[child_idx];

        bool no_parent = !parent_idx;
        bool node_black = node.color == AMRT_COLOR_BLACK;
        bool node_red = node.color == AMRT_COLOR_RED;
        bool child_black = child.color == AMRT_COLOR_BLACK;
        bool child_red = child.color == AMRT_COLOR_RED;
        bool node_black_child_red = node_black && child_red;

        if (no_parent || node_red || node_black_child_red) {
            // color child
            if (child_idx) {
                child.color = AMRT_COLOR_BLACK;
                tree->nodes[child_idx] = child;
            }

            colored = 1;
            // ??remove parent??
        } else {
            // node black child black
            amrt_idx sibling_idx = parent.child[!node.dir];
            amrt_rb_node sibling = tree->nodes[sibling_idx];
            amrt_idx close_nephew_idx = sibling.child[!sibling.dir];
            amrt_idx far_nephew_idx = sibling.child[sibling.dir];
            amrt_rb_node close_nephew = tree->nodes[close_nephew_idx];
            amrt_rb_node far_nephew = tree->nodes[far_nephew_idx];
            if (parent.color == AMRT_COLOR_RED) {
                if (!close_nephew_idx || 
                    close_nephew.color == AMRT_COLOR_BLACK) {
                    amrt__RBRotateUp(tree, sibling_idx);
                    colored = 1;
                    // ??remove parent??
                } else {
                    amrt__RBRotateUp(tree, close_nephew_idx);
                    // update vars and colors
                    parent = tree->nodes[parent_idx];
                    parent.color = AMRT_COLOR_BLACK;
                    tree->nodes[parent_idx] = parent;
                    amrt__RBRotateUp(tree, close_nephew_idx);
                    colored = 1;
                    // ??remove parent??
                }
            } else {
                // CASE: Parent Black
                if (sibling_idx && sibling.color == AMRT_COLOR_RED) {
                    // SUBCASE: Sibling Red
                    // make parent red
                    // make sibling black
                    parent.color = AMRT_COLOR_RED;
                    sibling.color = AMRT_COLOR_BLACK;
                    tree->nodes[parent_idx] = parent;
                    tree->nodes[sibling_idx] = sibling;
                    // rotate sibling up
                    amrt__RBRotateUp(tree, sibling_idx);

                    colored = 0;
                } else {
                    // SUBCASE: Sibling Black
                    if (far_nephew_idx && far_nephew.color == AMRT_COLOR_RED) {
                        // SUBCASE: Far Nephew Red
                        // color far nephew black
                        far_nephew.color = AMRT_COLOR_BLACK;
                        tree->nodes[far_nephew_idx] = far_nephew;
                        // rotate sibling up
                        amrt__RBRotateUp(tree, sibling_idx);

                        colored = 1;
                    } else {
                        // SUBCASE: Far Nephew Black
                        if (close_nephew_idx && close_nephew.color == AMRT_COLOR_RED) {
                            // SUBCASE: Close Nephew Red
                            // color close nephew black
                            close_nephew.color = AMRT_COLOR_BLACK;
                            tree->nodes[close_nephew_idx] = close_nephew;
                            // rotate close nephew up
                            amrt__RBRotateUp(tree, close_nephew_idx);
                            // rotate close nephew up
                            amrt__RBRotateUp(tree, close_nephew_idx);

                            colored = 1;
                        } else {
                            // SUBCASE: Close Nephew Black
                            
                            // Color Sibling Red
                            sibling.color = AMRT_COLOR_RED;
                            tree->nodes[sibling_idx] = sibling;

                            // Move X Up and try to resolve again
                            // @todo: possibly, remove this function 
                            // and do everything here, might be cleaner
                            amrt__RBIgnoreNode(tree, node_idx);

                            // update parent
                            parent = tree->nodes[parent_idx];
                            amrt_idx grandparent_idx = parent.parent;
                            if (parent_idx) {
                                parent.parent = node_idx;
                                node.child[child_dir] = AMRT_NIL;
                                node.child[!node.dir] = parent_idx;
                                AMRT_DIR parent_dir = parent.dir;
                                parent.dir = (AMRT_DIR)!node.dir;
                                node.dir = parent_dir;

                                tree->nodes[parent_idx] = parent;
                            }
                            node.parent = grandparent_idx;
                            if (grandparent_idx) {
                                amrt_rb_node grandparent = tree->nodes[grandparent_idx];
                                grandparent.child[node.dir] = node_idx;
                                tree->nodes[grandparent_idx] = grandparent;
                            }
                            tree->nodes[node_idx] = node;

                            colored = 0;
                        }
                    }
                }
            }
        }
    }
    amrt__RBIgnoreNode(tree, node_idx);
    amrt__RBFreelistReclaim(tree, node_idx);
    tree->node_count--;

    return 0;
}

void amrt_RBClear(amrt_rb_tree *tree) {
    AMRT_MEMZERO(tree->nodes, tree->node_max);
    tree->head = AMRT_NIL;
    tree->node_count = 0;
    tree->freelist = tree->head + 1;
    amrt_rb_node free = tree->nodes[tree->freelist];
    free.__size = tree->node_max - tree->freelist;
    tree->nodes[tree->freelist] = free;
}

void amrt_RBTerminate(amrt_rb_tree *tree) {
    AMRT_FREE(tree->nodes);
    *tree = {};
};

void amrt_RBPrint(amrt_rb_tree *tree) {
    amrt_idx *item_queue = (amrt_idx*)AMRT_MALLOC(sizeof(amrt_idx)*tree->node_max);

    amrt__RBUpdateLevels(tree, tree->head, 0);

    item_queue[0] = tree->head;
    int i = 0;
    int qidx = 1;
    do {
        amrt_idx iter_idx = item_queue[i];
        if (!iter_idx) continue;
        amrt_rb_node iter = tree->nodes[iter_idx];
        if (iter.left) item_queue[qidx++] = iter.left;
        if (iter.right) item_queue[qidx++] = iter.right;
    } while (i++ < tree->node_count);

    int level = 0;
    printf("\n============= BEGIN OF TREE ==========\n");
    for (i=0; i<qidx; i++) {
        amrt_idx item_idx = item_queue[i];
        if (!item_idx) continue;
        amrt_rb_node item = tree->nodes[item_idx];
        if (item.__level > level) {
            printf("> Level %d: \n", level);
            level++;
        }
        printf("Idx: %d, Color: %d, Item: %d, Dir: %d, Parent: %d, Left: %d, Right: %d\n", 
               item_idx, item.color, item.value, item.dir, item.parent, item.left, item.right);
    }
    printf("\n============= END OF TREE ==========\n");
    AMRT_FREE(item_queue);
}

// Helper Functions

amrt_idx amrt__RBFreelistPop(amrt_rb_tree *tree) {
    amrt_idx head_idx = tree->freelist;
    amrt_idx curr_free_idx = head_idx;
    amrt_idx next_free_idx = curr_free_idx;
    amrt_rb_node curr_free_node = tree->nodes[curr_free_idx];
    amrt_rb_node next_free_node = curr_free_node;

    // check if there is a free node available
    // assumption is that head is valid
    if (!curr_free_idx || !curr_free_node.__size) return curr_free_idx;

    if (curr_free_node.__size - 1) {
        // free node has space
        // move head 1 index ahead
        next_free_idx = curr_free_idx + 1;
        next_free_node = tree->nodes[next_free_idx];
        // decrease size
        next_free_node.__size = curr_free_node.__size-1;
    } else if (curr_free_node.next) {
        // Other free nodes present
        // move head to next free node
        next_free_idx = curr_free_node.next;
    } else {
        // This is the last available free node
        // Do nothing 
        // Keep it marked as head
        // But keep providing this
        // Alternatives: 
        // - assert and crash
        // - allocate more
    }

    tree->nodes[next_free_idx] = next_free_node;
    tree->freelist = next_free_idx;

    return curr_free_idx;
}

amrt_status amrt__RBFreelistReclaim(amrt_rb_tree *tree, amrt_idx node_idx) {
    // @todo:
    // implement freelist reclaim
    // cases as far as i understand
    //
    // node before freelist head
    // - check if node is right before old freelist head
    // - mark node as freelist head and update size accordingly
    //
    // node after freelist head
    // - get free idx just before node idx
    // - join node with previous free and update size if continguous OR
    // - update next and prev 
    //
    // also dont forget to update nodes with proper elements

    if (!node_idx || tree->freelist == node_idx) return 0;

    amrt_idx freelist_idx = tree->freelist;
    amrt_rb_node freelist = tree->nodes[freelist_idx];
    if (node_idx < freelist_idx) {
        // node before freelist
        amrt_rb_node node = {};
        node.__size = 1;
        node.next = freelist_idx;
        if (node_idx + 1 == freelist_idx) {
            node.__size += freelist.__size;
            node.next = freelist.next;
        }        
        tree->nodes[node_idx] = node;
        tree->freelist = node_idx;
    } else {
        amrt_idx iter_idx = freelist_idx;
        amrt_rb_node iter = tree->nodes[iter_idx];
        while (iter.next < node_idx) {
            iter_idx = iter.next;
            iter = tree->nodes[iter_idx];
        }
        // we have iter --- fit node here ------>iter.next
        amrt_rb_node node = {};
        node.__size = 1;
        node.next = iter.next;
        iter.next = node_idx;
        if (iter.__size + iter_idx == node_idx) {
            // node right next to iter
            // extend iter
            iter.next = node.next;
            iter.__size++;
        }
        tree->nodes[iter_idx] = iter;
        tree->nodes[node_idx] = node;
    }

    return 0;
}

void amrt__RBRotateUp(amrt_rb_tree *tree, amrt_idx node_idx) {
    if (node_idx) {
        amrt_rb_node node = tree->nodes[node_idx];
        amrt_idx parent_idx = node.parent;
        if (parent_idx) {
            amrt_rb_node parent = tree->nodes[parent_idx];
            amrt_idx grandparent_idx = parent.parent;
            amrt_rb_node grandparent = tree->nodes[grandparent_idx];

            amrt_idx near_child_idx = node.child[!node.dir]; 
            amrt_rb_node near_child = tree->nodes[near_child_idx];

            node.parent = grandparent_idx;
            parent.parent = node_idx;
            node.child[!node.dir] = parent_idx;
            parent.child[node.dir] = near_child_idx; 

            if (near_child_idx) {
                near_child.parent = parent_idx;
                near_child.dir = node.dir;
            }            

            AMRT_DIR parent_dir = parent.dir;
            parent.dir = (AMRT_DIR)!node.dir;

            if (grandparent_idx) {
                grandparent.child[parent_dir] = node_idx;
                node.dir = parent_dir;
            }

            // update
            tree->nodes[grandparent_idx] = grandparent;
            tree->nodes[parent_idx] = parent;
            tree->nodes[near_child_idx] = near_child;
            tree->nodes[node_idx] = node;
        }
    }

    return;
}

amrt_idx amrt__RBSubtreeFindSmallestNode(amrt_rb_tree *tree, amrt_idx node_idx) {

    amrt_idx smallest_node_idx = node_idx;
    amrt_rb_node node = tree->nodes[smallest_node_idx];
    while(node.left) {
        smallest_node_idx = node.left;
        node = tree->nodes[smallest_node_idx];
    }
    return smallest_node_idx;
}

amrt_status amrt__RBIgnoreNode(amrt_rb_tree *tree, amrt_idx node_idx) {
    amrt_rb_node node = tree->nodes[node_idx];
    amrt_idx parent_idx = node.parent;
    amrt_idx left_idx = node.left;
    amrt_idx right_idx = node.right;

    if (left_idx && right_idx) return 1;

    amrt_idx child_idx = left_idx ? left_idx : right_idx;
    amrt_rb_node parent = tree->nodes[parent_idx];
    amrt_rb_node child = tree->nodes[child_idx];

    if (child_idx) {
        child.parent = parent_idx;
        child.dir = node.dir;
        tree->nodes[child_idx] = child;
    }
    if (parent_idx) {
        parent.child[node.dir] = child_idx;
        tree->nodes[parent_idx] = parent;
    } else {
        // grandparent was nil
        // parent would have been root
        // child is new root
        tree->head = child_idx;
    }

    return 0;
}

void amrt__RBUpdateLevels(amrt_rb_tree *tree, amrt_idx node_idx, int level) {
    tree->nodes[node_idx].__level = level++;
    amrt_rb_node node = tree->nodes[node_idx];
    if (node.left) {
        amrt__RBUpdateLevels(tree, node.left, level);
    }
    if (node.right) {
        amrt__RBUpdateLevels(tree, node.right, level);
    }
}

int amrt__RBValidateColors(amrt_rb_tree tree, amrt_idx node_idx) {
    if (!node_idx) return 0;
    amrt_rb_node node = tree.nodes[node_idx];

    // validate red equality
    bool red_equality_met = true;
    if (node.color == AMRT_COLOR_RED) {
        amrt_idx child_idx = node.left;
        amrt_rb_node child = tree.nodes[child_idx];
        red_equality_met =  (
            red_equality_met && 
            !child_idx || child.color == AMRT_COLOR_BLACK
        );   
        child_idx = node.right;
        child = tree.nodes[child_idx];
        red_equality_met =  (
            red_equality_met && 
            !child_idx || child.color == AMRT_COLOR_BLACK
        );   
    }
    int black_count = node.color == AMRT_COLOR_BLACK;
    int ltree_count = amrt__RBValidateColors(tree, node.left);
    int rtree_count = amrt__RBValidateColors(tree, node.right);
    black_count += rtree_count;

    bool black_equality_met = ltree_count >= 0 && ltree_count == rtree_count;
    if (black_equality_met && red_equality_met) {
        return black_count;
    } else {
        return -1;
    }
}

int amrt__RBCountNodes(amrt_rb_tree tree, amrt_idx node_idx) {
    if (!node_idx) return 0;

    int node_count = 1;
    amrt_rb_node node = tree.nodes[node_idx];
    node_count += amrt__RBCountNodes(tree, node.left);
    node_count += amrt__RBCountNodes(tree, node.right);

    return node_count;
}

bool amrt__RBSetupValid(amrt_rb_tree tree, amrt_idx node_idx) {
    amrt_rb_node node = tree.nodes[node_idx];
    amrt_idx left_idx = node.left;
    amrt_idx right_idx = node.right;
    bool is_valid = true;
    if (left_idx) { 
        amrt_rb_node left = tree.nodes[left_idx];
        bool subtree_valid = amrt__RBSetupValid(tree, left_idx);
        is_valid = (
            is_valid && left.value <= node.value &&
            subtree_valid
        );
    }
    if (right_idx) {
        amrt_rb_node right = tree.nodes[right_idx];
        bool subtree_valid = amrt__RBSetupValid(tree, right_idx);
        is_valid = (
            is_valid && node.value <= right.value &&
            subtree_valid
        );
    }
    return is_valid;
}

amrt_status amrt__RBValidate(amrt_rb_tree tree) {
    // 1. root is black
    amrt_idx head_idx = tree.head;
    bool is_root_black = tree.nodes[head_idx].color == AMRT_COLOR_BLACK;
    // 2. equal number of black nodes on each path
    // 3. no consecutive red node
    bool is_coloring_valid = amrt__RBValidateColors(tree, head_idx) >= 0;
    // 4. inserted nodes match nodes in tree
    bool is_node_count_valid = amrt__RBCountNodes(tree, head_idx) == tree.node_count;
    // 5. validate node values are btree correct
    bool is_btree_setup_valid = amrt__RBSetupValid(tree, head_idx);

    bool is_tree_valid = (
        is_root_black && is_coloring_valid && is_node_count_valid && 
        is_btree_setup_valid
    );
    if (is_tree_valid) {
        printf("RB Tree Validation: Success! all rules are mantained\n");
    } else {
        printf("RB Tree Validation: Failure! \n");
        if (!is_root_black) {
            printf("root is not black\n");
        }
        if (!is_coloring_valid) {
            printf("coloring is not correct. (Not sure which coloring)\n");
        }
        if (!is_node_count_valid) {
            printf("node count is not matching number of accessible nodes in the tree\n");
        }
        if (!is_btree_setup_valid) {
            printf("btree setup is not valid\n");
        }
    }
    return is_tree_valid;
}

int main(void) {
    amrt_rb_tree test_tree = amrt_RBInit(100);
    amrt_RBInsert(&test_tree, 10);
    amrt_RBInsert(&test_tree, 11);
    amrt_RBInsert(&test_tree, 12);
    amrt_RBInsert(&test_tree, 13);
    amrt_RBInsert(&test_tree, 14);
    amrt_RBInsert(&test_tree, 15);
    amrt_RBInsert(&test_tree, 20);
    amrt_RBInsert(&test_tree, 21);
    amrt_RBInsert(&test_tree, 22);
    amrt_RBInsert(&test_tree, 23);
    amrt_RBInsert(&test_tree, 24);
    amrt_RBInsert(&test_tree, 25);
    amrt_RBInsert(&test_tree, 30);
    amrt_RBInsert(&test_tree, 31);
    amrt_RBInsert(&test_tree, 32);
    amrt_RBInsert(&test_tree, 33);
    amrt_RBInsert(&test_tree, 34);
    amrt_RBInsert(&test_tree, 35);
    amrt_RBInsert(&test_tree, 40);
    amrt_RBInsert(&test_tree, 41);
    amrt_RBInsert(&test_tree, 42);
    amrt_RBInsert(&test_tree, 43);
    amrt_RBInsert(&test_tree, 44);
    amrt_RBInsert(&test_tree, 45);
    amrt_RBInsert(&test_tree, 50);
    amrt_RBInsert(&test_tree, 51);
    amrt_RBInsert(&test_tree, 52);
    amrt_RBInsert(&test_tree, 53);
    amrt_RBInsert(&test_tree, 54);
    amrt_RBInsert(&test_tree, 55);

    assert(amrt__RBValidate(test_tree));

    assert(amrt_RBSearch(test_tree, 33));
    assert(!amrt_RBSearch(test_tree, 1998));

    amrt_RBPrint(&test_tree);
    amrt_RBDelete(&test_tree, 54);
    amrt_RBDelete(&test_tree, 50);
    amrt_RBDelete(&test_tree, 52);
    amrt_RBDelete(&test_tree, 53);

    assert(amrt__RBValidate(test_tree));

    // Testing Operations on duplicates
    printf("\nTesting operations on duplicates\n");
    amrt_RBClear(&test_tree);
    amrt_RBInsert(&test_tree, 32);
    amrt_RBInsert(&test_tree, 32);
    amrt_RBInsert(&test_tree, 32);
    amrt_RBInsert(&test_tree, 32);
    amrt_RBInsert(&test_tree, 32);
    amrt_RBInsert(&test_tree, 54);
    amrt_RBInsert(&test_tree, 54);
    amrt_RBInsert(&test_tree, 54);
    amrt_RBInsert(&test_tree, 54);
    amrt_RBInsert(&test_tree, 54);
    amrt_RBInsert(&test_tree, 85);
    amrt_RBInsert(&test_tree, 85);
    amrt_RBInsert(&test_tree, 85);

    amrt_RBDelete(&test_tree, 54);
    amrt_RBDelete(&test_tree, 54);
    amrt_RBDelete(&test_tree, 32);
    amrt_RBDelete(&test_tree, 54);
    amrt_RBDelete(&test_tree, 32);
    amrt_RBDelete(&test_tree, 32);
    assert(amrt__RBValidate(test_tree));

    amrt_RBTerminate(&test_tree);

    return 0;
}