Backing up dataHEADmain

1 files changed, 821 insertions, 0 deletions

diff --git a/il_redblack.cpp b/il_redblack.cpp
new file mode 100644
index 0000000..93fdf72
--- /dev/null
+++ b/il_redblack.cpp
@@ -0,0 +1,821 @@
+#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;
+}