bottomupmergesort

//LLRB-TreeSort.cpp  - Max Goren 6/28/22
//
// TreeSort utilizing Left Leaning Red Black Tree
// the algorithm's input is an array to be sorted, output is the sorted array.
// TreeSort exploits a binary search tree's ordered property in that an in-order
// traversal yields the items in sorted order. This implementation doubles down
// with the use of a Left Leaning Red Black Tree to keep the process of building
// the binary search tree guranteed O(N log N). the traversal itsself is an O(n) operation,
// storing each nodes item in the T* sorted array.
//

bottomupmergesort

void merge_sort(struct node** h)
{
    if (*h == NULL || (*h)->next == NULL)
        return;
    struct node *fast = (*h)->next, *slow = *h;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

bottomupmergesort

void ht_delete(hash_table* ht, char* key)
{
    unsigned int index = hash_function(key, ht->tableSize);
    //first check if its the first slot, as we are using different header structs than link structs
    if (strcmp(ht->table[index]->next->key, key) == 0)
    {
        ht_item* temp = ht->table[index]->next;
        ht->table[index]->next = ht->table[index]->next->next;
        free(temp);
        return;

bottomupmergesort

char* ht_search(hash_table* ht, char* key)
{
    unsigned int index = hash_function(key, ht->tableSize);
    for (ht_item* itr = ht->table[index]->next; itr != NULL; itr = itr->next)
        if (strcmp(itr->key, key) == 0)
            return itr->value;

    return NULL;
}

bottomupmergesort

void ht_insert(hash_table* ht, char* key, char* info)
{
    unsigned int index = hash_function(key, ht->tableSize);
    ht_item* newItem = make_item(key, info);
    newItem->next = ht->table[index]->next;
    ht->table[index]->next = newItem;
    ht->table[index]->slotCount += 1;
    ht->count += 1;
}

bottomupmergesort

typedef struct ht_item {
    char* key;
    char* value;
    struct ht_item* next;
} ht_item;

ht_item* make_item(char* key, char* value)
{
    ht_item* newItem = (ht_item*)malloc(sizeof(ht_item));
    newItem->key = (char*)malloc(sizeof(char) * strlen(key));

bottomupmergesort

char* search(hash_table* ht, char* key)
{
    unsigned int index = hash_function(key);
    while (index < ht->tableSize && ht->table[index] != NULL)
    {
        if (strcmp(ht->table[index]->key, key) == 0)
        {
            return ht->table[index]->value;
        } else {
            index = (index + 1) % ht->tableSize;

bottomupmergesort

void insert(hash_table* ht, char* key, char* value)
{
    if (ht->tableSize == ht->count + 1)
    {
        printf("Table Overflow: Hash Table Full!");
        return 0;
    }
    unsigned int tableIndex = hash_function(key, ht->tableSize);
    if (ht->table[tableIndex] == NULL)
    {

bottomupmergesort

typedef struct hash_table {
    ht_item** table;
    int count;
    int tableSize;
} hash_table;

hash_table* initHashTable(hash_table* ht, int table_size)
{
    ht = (hash_table*)malloc(sizeof(hash_table));
    ht->tableSize = table_size;

bottomupmergesort

typedef struct ht_item_t {
    char* key;
    char* value;
} ht_item;

ht_item* make_item(char* key, char* value)
{
    ht_item* nhti = (ht_item*)malloc(sizeof(ht_item));
    nhti->key = (char*)malloc(sizeof(char) * strlen(key));
    nhti->value = (char*)malloc(sizeof(char) * strlen(value));