Nella insert non puoi fare semplicemente

e->key = k;

ma devi allocare lo spazio per la stringa.

Devi sostituire quella riga con

e->key = (char *)malloc(strlen(k)+1);
e->key = strcpy(e->key, k);