C言語 二分木探索による辞書の作成

Question

###前提・実現したいこと
以下のようなコマンドを入力としてうけつける辞書を作ろうと考えています。
「insert <word> <tango>」: <word>の翻訳が<tango>であるとデータベースに登録する。既に登録されている場合は上書きする。
「delete <word>」: <word>をデータベースから削除する。
「search <word>」: <word>をデータベースから検索し、その翻訳を表示する。 単語がデータベースに存在しないときには、「(not found)」と表示する。
「quit」: プログラムを終了する。

例えば、以下のような入力が想定されています。

insert apple 林檎
insert orange オレンジ
insert grape 葡萄
insert pear 梨
insert strawberry 苺
insert raspberry 木苺
insert fig 無花果
insert kaki 柿
insert apricot 杏
insert peach 桃
search orange
insert orange 蜜柑
search orange
delete orange
search orange
search strawberry
quit

これを入力すると、以下のように出力されるはずです。
オレンジ
蜜柑
(not found)
苺

###発生している問題・エラーメッセージ

deleteの動作を行うと、セグフォに陥ってしまいますが、なぜかがわかりません。

###該当のソースコード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef char *String;
typedef struct tnode *BTree;
struct tnode {
    String key;
    String value;
    BTree left;
    BTree right;
};

BTree btree_empty()
{
    /* 空木を返す。 */
  return NULL;
}

int btree_isempty(BTree t)
{
    /* `t'が空木なら0以外を、そうでないなら0を返す。 */
  if (t == (btree_empty())) return 1;
      return 0;
}

BTree btree_insert(String key, String val, BTree t)
{
    /*
    * 文字列`key'をキーとして、文字列`val'を二分探索木`t'に挿入し、その木を返す。
    * `key'と`val'の内容はデータベースにコピーされる。
    * 同じキーを持つ項目が既に存在する場合は、その項目を上書きする。
    */
    if(btree_isempty(t) != 0){
      BTree tree = malloc(sizeof(struct tnode));
      tree->key = key;
      tree->value = val;
      tree->left = btree_empty();
      tree->right = btree_empty();
      return tree;
    }
    if(strcmp(key, t->key) < 0){
      t->left = btree_insert(key, val, t->left);
      return t;
    }else if(strcmp(key, t->key) > 0){
      t->right = btree_insert(key,val, t->right);
      return t;
    }
    t->value = val;
    return t;
}

BTree btree_searchmin(BTree t)
{
  while(btree_isempty(t->left) != 0) t = t->left;
  return t;
}

 BTree btree_deletemin(BTree t)
{
  if(btree_isempty(t->left) == 0){
    BTree tree = malloc(sizeof(struct tnode));
    tree->left = btree_deletemin(t);
    tree->right = t->right;
    tree->key = t->key;
    tree->value = t->value;
    return tree;
  }
  return t->right;
}
    

BTree btree_delete(String key, BTree t)
{
    /*
    * 文字列`key'をキーとする項目を、二分探索木`t'から削除し、その木を返す。
    */
  if (btree_isempty(t) != 0) return t;
  
  if(strcmp(key, t->key) < 0){
      t->left = btree_delete(key, t->left);
      return t;
    }else if(strcmp(key, t->key) > 0){
      t->right = btree_delete(key, t->right);
      return t;
    }
  BTree min = btree_searchmin(t);
  BTree del = btree_deletemin(t);
  del->key = min->key;
  del->value = min->value;
  return del;
}



struct tnode *btree_search(String key, BTree t)
{
    /*
    * 二分探索木`t'を検索し、文字列`key'をキーとするノードへのポインタを返す。
    * 見付からない場合は、NULLを返す。
    */
  if(btree_isempty(t) != 0) return NULL;
    
    if(strcmp(key, t->key) < 0){
      return btree_search(key, t->left);
    }else if(strcmp(key, t->key) > 0){
      return btree_search(key, t->right);
    }
    return t;
}
void btree_free(BTree t)
{
    /*
     * 二分探索木`t'の内容を全て消去し、メモリを解放する。
     */
     if(t == NULL)
      return;
    btree_free(t->left);
    btree_free(t->right);
    free(t);
}

int main(int argc, char *argv[])
{
  char cmd[100];
  char key[100];
  char val[100];
  struct tnode *search;
  BTree t = btree_empty();
      while (scanf("%99s", cmd) != EOF) {
      if (strncmp(cmd,"insert",6) == 0) {

//insertの操作

scanf("%99s", key);

scanf("%99s", val);

t = btree_insert(key, val, t);
      } else if (strncmp(cmd,"delete",6) == 0) {

scanf("%99s", key);

t = btree_delete(key, t);
        } else if (strncmp(cmd,"search",6) == 0) {

 scanf("%99s", key);

 search = btree_search(key, t);

 if(btree_isempty(search) != 0){

  printf("(not found)\n");

  }else printf("%s\n",search->value);

  }else if(strcmp(cmd,"quit") == 0){
 return 0;
  
  }else{
            printf("(unknown command)\n");
  }
        cmd[0] = '\0';
}
  btree_free(t);
   return 0;
}

###試したこと
自分なりに、gdbを用いてデバッグしてみたのですが、よくわかりませんでした。

###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報

Answer 1

ぱっと見バグだらけで、どこから話すべきか悩ましいですが…
まず、ツリーに登録されている要素へのポインタvalは、常にmain関数の中のvalへのポインタになりますよね…? (複製されていない)
あとquitしたときの解放処理もないですし…。

消去するときのアルゴリズムをゆっくり、口に出してみてください。それが答えです。

追記: 肝心のヒントを書き忘れていました。
参考文献
https://www.google.co.jp/url?sa=t&source=web&rct=j&url=http://f-server.ics.kagoshima-u.ac.jp/~fuchida/algorithm/alg10-%25E4%25BA%258C%25E5%2588%2586%25E6%258E%25A2%25E7%25B4%25A2%25E6%259C%25A8.pdf&ved=0ahUKEwjKz6XPx83RAhXLerwKHf2iAhUQFggaMAA&usg=AFQjCNHVcPps2iWdIZJ67uq6m8U1e5tTNg

暴走した理由ですが、

BTree btree_deletemin(BTree t)
{
...
    tree->left = btree_deletemin(t);
...
}

この行のどこかが間違ってましたとだけ。