59543


上の表題にもある通り、二分探索木を利用して動的なハッシュマップを自分で作ろうとしたのですが、私が書いた以下のコードは実行しても入力に対して期待された出力をしません。  
どのように以下のコードに改善すれば、期待された出力を得られるのでしょうか？  
とても読みづらいコードになってしまっていて申し訳ないのですが、アドバイスを頂けると大変助かります。

実行したコード:

[code]

    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    typedef struct tnode{ //二分木内のノード
        char* key;
        char* value;
        struct tnode* left;
        struct tnode* right;
    } tnode;
    
    tnode* btree_empty()
    {
        tnode* t;
        t = (tnode*)malloc(sizeof(tnode));
        t->key = (char*)malloc(sizeof(char)*100);
        t->value = (char*)malloc(sizeof(char)*100);
        t->left = NULL;
        t->right = NULL;
        return t;
    }
    
    tnode* btree_insert_helper(tnode* parent, char* key, char* val, tnode* t)
    {
        if(t == NULL){
            tnode* node = btree_empty();
            strcpy(node->key, key);
            strcpy(node->value, val);
            if(parent == NULL){
                ;
            }else if(strcmp(parent->key, node->key) < 0){
                parent->right = node;
            }else{
                parent->left = node;
            }
            return node;
        }
        int cmp = strcmp(key, t->key);
        if(cmp < 0){
            if(t->left == NULL){
                t->left = btree_empty();
                tnode* node = t->left;
                strcpy(node->key, key);
                strcpy(node->value, val);
                return node;
            }else{
                tnode* node = btree_insert_helper(t, key, val, t->left);
                return node;
            }
        }else if(cmp > 0){
            if(t->right == NULL){
                t->right = btree_empty();
                tnode* node = t->right;
                strcpy(node->key, key);
                strcpy(node->value, val);
                return node;
            }else{
                tnode* node = btree_insert_helper(t, key, val, t->right);
                return node;
            }
        }else{
            strcpy(t->value, val);
            return t;
        }
    }
    
    tnode* btree_insert(char* key, char* val, tnode* t)
    {
        return btree_insert_helper(NULL, key, val, t);
    }
    
    tnode** deletemin(tnode* node){
        tnode** res = (tnode**)malloc(2*sizeof(tnode*));
        if(node->left != NULL){
            tnode** temp = deletemin(node->left);
            tnode* min;
            node->left = temp[0];
            min = temp[1];
            res[0] = node;
            res[1] = min;
        }else{
            res[0] = node->right;
            res[1] = node;
        }
        return res;
    }
    
    tnode* btree_delete(char* key, tnode* t)
    {
        if(t == NULL){
            return NULL;
        }
        int cmp = strcmp(key, t->key);
        if(cmp < 0){
            t->left = btree_delete(key, t->left);
            return t;
        }else if(cmp > 0){
            t->right = btree_delete(key, t->right);
            return t;
        }else{
            if(t->left == NULL && t->right == NULL){
                return NULL;
            }else if(t->left != NULL && t->right == NULL){
                return t->left;
            }else if(t->left == NULL && t->right != NULL){
                return t->right;
            }else{
                tnode** temp = deletemin(t->right);
                tnode* right = temp[0];
                tnode* min = temp[1];
                free(temp);
                min->right = right;
                min->left = t->left;
                return min;
            }
        }
    }
    
    tnode* btree_search(char* key, tnode* t){
        int cmp = 0;
        tnode* result = NULL;
        
        if(t == NULL){
            result = NULL;
        }else{
            cmp = strcmp(key, t->key);
            if(cmp == 0){
                result = t;
            }else if(cmp < 0){
                result = btree_search(key, t->left);
            }else{
                result = btree_search(key, t->right);
            }
        }
        
        return result;
    }
    
    void btree_destroy(tnode* t)
    {
        if(t == NULL){
            ;
        }else{
            btree_destroy(t->left);
            btree_destroy(t->right);
            free(t->key);
            free(t->value);
            free(t);
        }
        return;
    }
    
    int main(){
        char command[100];
        char word[100];
        char tango[100];
        tnode *tree = NULL;
        tnode *temp = NULL;
        
        while(1){
            scanf("%s", command);
            if(strcmp(command, "insert") == 0){
                scanf("%s %s", word, tango);
                temp = btree_insert(word, tango, tree);
                if(tree == NULL){
                    tree = temp;
                }
            }else if(strcmp(command, "delete") == 0){
                scanf("%s", word);
                temp = tree_delete(word, tree);
                /*
                 if(temp == tree->left){
                 tree = tree->left;
                 }else if(temp == tree->right){
                 tree = tree->right;
                 }else{
                 ;
                 }
                 */
            }else if(strcmp(command, "search") == 0){
                scanf("%s", word);
                temp = btree_search(word, tree);
                if(temp == NULL){
                    printf("(not found)\n");
                }else{
                    printf("%s\n", temp->value);
                }
            }else if(strcmp(command, "quit") == 0){
                break;
            }else{
                printf("ERROR\n");
            }
        }
        btree_destroy(tree);
        return 0;
    }
    
[/code]


CC BY-SA 4.0
2019-10-07T12:33:05.153
59536
2022-06-15T17:03:32.837
2022-06-15T17:03:32.837
31249
31249
question
c アルゴリズム binary-tree
二分探索木を用いて英単語をキーとした連想配列を動的に作りたいが、連想配列が期待通りの動作をしてくれない。

[code]

      temp = btree_delete(word, tree);
    
[/code]

の行を

[code]

      tree = btree_delete(word, tree);
    
[/code]

に変えれば求める出力は得られます。

コメントアウトしてある部分を見るに、何か気にかかることがあって敢えてこういう書き方をしなかったのかとも思いますが、全体の流れからするとこれが想定された用法でしょう。

質問の趣旨から外れるので深入りしませんが一応付言しておくと、deleteの処理関連でメモリリークがあるので、そこは修正が必要です。


CC BY-SA 4.0
2019-10-07T18:49:04.883
59543
2019-10-07T18:49:04.883
33033
59536
answer