Consider a hash table with chaining where the elements with the same hash value are inserted in the same binary search tree (BST) instead of a list.

• Define the abstract data type (ADT) Hash Table.
• Write the corresponding declaration of such data structure.
• Write the following operations:
  • Create a HashTable,
  • Add an element,
  • Search for a given element.

Hint: You may use the function $$\texttt{int Hash(char *s)}$$ that returns a position in the hash table.

typedef char element[N];
typedef struct node
{
	element data; 
	struct node * left, *right;
} *BST;

typedef BST hashtable[M];




void CreateHashtable(hashtable h)
{
    int i;
    for(i=0; i <M; i++)
        h[i]=NULL;
}



int insert_BST(BST *B, element e)
{
    if(*B==NULL)
    {
        *B=(BST)malloc(sizeof(struct node));
        if(!(*B)) return 0;
        strcpy((*B)->data,e);
        (*B)->left = (*B)->right =  NULL;
        return 1;
    }
    if(strcmp((*B)->data,e)==0)
        return 0;
    if(strcmp((*B)->data,e)<0)
        return insert_BST(&((*B)->right),  e);
    return insert_BST(&((*B)->left),  e);
}


int insert(hashtable h, element n)
{
   return insert_BST(&h[hash(n)],n);
}


int search_bst(BST B, element e)
{
    if(!B) return 0;
    if(!strcmp(B->data,e)) return 1;
    if(strcmp(B->data, e) <0)
        return search_bst(B->right, e);
    return search_bst(B->left, e);
}

int search(hashtable h, element e)
{
    return search_bst(h[hash(e)],e);
}