C Academy · レッスン

検索と解放

Q: 「検索と解放」で何を学びますか？

ノードを検索してメモリを解放します。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

ノードを検索してメモリを解放します。

レッスン 4/413 ステップ

「検索と解放」はCoddyKit上の無料C Academyレッスンです。これはレッスン4/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。

BSTを探索する

探索では、値の順序規則を利用します。各ノードで目的の値とノードの値を比較し、片方の部分木だけへ進みます。

各ステップで残りのノードの半分を除外するため、探索コストは木の大きさではなく高さに応じて増えます。

再帰による探索

再帰による探索には2つのベースケースがあります。空の部分木なら見つからず、一致する値なら見つかったことを意味します。

それ以外の場合は、比較結果に応じて左または右へ再帰します。

Node *search(Node *root, int target) {
    if (root == NULL || root->value == target)
        return root;
    if (target < root->value)
        return search(root->left, target);
    return search(root->right, target);
}

反復による探索

探索は単純なループで行うこともでき、再帰のオーバーヘッドを避けられます。

目的の値が見つかるか、NULLで木の終端に達するまで、木を下方向へポインタでたどります。

Node *search_iter(Node *root, int target) {
    while (root != NULL) {
        if (target == root->value) return root;
        root = (target < root->value)
             ? root->left : root->right;
    }
    return NULL;  /* not found */
}

探索の実行例

このプログラムはBSTを構築し、存在する値と存在しない値を探索して、それぞれが見つかったかどうかを出力します。

NULLではない戻り値は見つかったことを、NULLはその値が木に存在しないことを意味します。

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

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
Node *search(Node *r,int t){
    if(!r||r->value==t) return r;
    return t<r->value ? search(r->left,t) : search(r->right,t);
}

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("7:%s 99:%s\n",
        search(root,7)?"found":"no",
        search(root,99)?"found":"no");
    return 0;
}

最小値を見つける

BSTでは最小値は最も左にあるノードです。leftがNULLになるまでたどり続けます。

同様に、最大値は最も右にあるノードです。これらのヘルパーは、削除や範囲クエリで重要になります。

Node *find_min(Node *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

解放が重要な理由

すべてのノードはmallocで確保されているため、すべてのノードをfreeで返さなければなりません。解放を忘れるとメモリリークが発生します。

ただし、ノードを解放した後にその子ノードへのポインタを読み取ることはできないため、解放する順序が重要です。

Post-Orderで解放する

木を安全に解放するにはpost-orderを使い、まず両方の子ノードを解放してから、ノード自体を解放します。

これにより、ノードのメモリを解放する前に、そのleftとrightのポインタを読み取れることが保証されます。

void free_tree(Node *root) {
    if (root == NULL) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

危険な誤った順序

子ノードへ再帰する前にノードを解放すると、未定義動作が発生します。部分木へ到達するために、解放済みメモリを逆参照することになるためです。

これは典型的なuse-after-freeバグです。必ず子ノードを先に解放してください。

/* WRONG: use-after-free */
void bad_free(Node *root) {
    if (!root) return;
    free(root);                 /* freed here */
    bad_free(root->left);       /* reads freed memory! */
    bad_free(root->right);
}

ダングリングポインタを避ける

free_treeが戻った後も、元のルートポインタには古いアドレスが残っていますが、メモリ自体はなくなっています。

呼び出し元でそれをNULLに戻せば、ダングリングポインタを誤って再利用するのを防げます。

free_tree(root);
root = NULL;   /* avoid a dangling pointer */

解放したノードを数える

post-orderでたどりながらノード数を数え、その後で各ノードを解放することで、解放が正しく動作することを確認できます。

このプログラムは木を構築して解放し、解放されたノード数を報告します。

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

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
int free_count(Node *r){
    if(!r) return 0;
    int c = free_count(r->left) + free_count(r->right);
    free(r);
    return c + 1;
}

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("freed=%d\n", free_count(root));
    root = NULL;
    return 0;
}

探索と解放をまとめて行う

木を構築し、探索し、その後で解放するという完全なライフサイクルです。この3つをすべて行うことで、プログラムを正しく保ち、メモリリークを防げます。

Valgrindのようなツールを使えば、すべてのmallocに対応するfreeが行われていることを確認できます。

/* lifecycle
 * 1. insert values     (allocate)
 * 2. search as needed   (read-only)
 * 3. free_tree(root)    (deallocate)
 * 4. root = NULL        (avoid dangling)
 */

簡単な確認

安全なメモリ解放について考えてみましょう。

対話的なレッスンで答える

まとめ

BSTの探索では、比較を行い、各ステップで1つの部分木へ進むため、時間コストは木の高さに比例します。最小値は最も左のノード、最大値は最も右のノードです。

木はpost-orderで解放し、子ノードを親ノードより先に解放します。その後、ルートをNULLに設定してダングリングポインタを避けます。

無料で開始

AI チューターと学ぶ C — 無料

ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。

コース: 39
レッスン: 144

無料で学習を始めるコース全体を表示

よくある質問

「検索と解放」レッスンは無料ですか？

はい。「検索と解放」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。

「検索と解放」で何を学びますか？

ノードを検索してメモリを解放します。ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン4/4です。

「検索と解放」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC Academyレッスンでコードを書いて実行できますか？

はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← C Academyに戻る