0Pricing
C Academy · レッスン

BSTに挿入する

二分探索木を構築します。

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

BSTの順序規則

二分探索木（BST）は、二分木にもう1つ規則を加えたものです。すべてのノードについて、左部分木の値はすべてそのノードより小さく、右部分木の値はすべて大きくなります。

この順序付けにより、木の高さに比例する時間で検索、挿入、削除を行えます。

値が属する場所

挿入では、ルートから開始して比較します。新しい値が小さければ左へ、大きければ右へ進みます。

空いている場所（NULL）に到達するまで繰り返します。そこが新しいノードの入る場所です。

/* insert 7 into:
 *        10
 *       /  \
 *      5    15
 * 7 < 10 -> left;  7 > 5 -> right of 5
 */

create_nodeヘルパー

挿入では新しい葉ノードを作成するため、ノードを確保して初期化するコンストラクターを再利用します。

新しく挿入されたノードは常に葉なので、両方の子はNULLから始まります。

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (!n) return NULL;
    n->value = value;
    n->left = n->right = NULL;
    return n;
}

再帰的な挿入

最もすっきりした挿入方法は、再帰を使い、場合によっては新しくなった部分木のルートを返す方法です。

部分木が空なら新しいノードを返します。それ以外の場合は左または右へ再帰し、その結果を再接続してから、変更されていないルートを返します。

Node *insert(Node *root, int value) {
    if (root == NULL)
        return create_node(value);
    if (value < root->value)
        root->left = insert(root->left, value);
    else if (value > root->value)
        root->right = insert(root->right, value);
    return root;  /* equal: ignore duplicate */
}

ルートを返す理由

部分木のルートを返すと、親側でリンクを1行で再接続できます。root->left = insert(root->left, v)のように記述します。

部分木が空だった場合は、返された新しいノードが子になります。空でなかった場合は同じルートが返され、リンクは変わりません。

/* The assignment does double duty:
 * - empty case: stores the new node
 * - non-empty:  stores the same pointer back (no-op)
 */
root->left = insert(root->left, value);

重複値の扱い

実際のBSTでは、同じ値をどう扱うかを決める必要があります。よくある選択肢は重複を無視することで、ここでのinsertも等しい場合の分岐を持たないことでそのように動作します。

ほかの方法として、ノードごとに個数を保持したり、重複値を常に片側へ送ったりすることもできます。

if (value < root->value)
    root->left = insert(root->left, value);
else if (value > root->value)
    root->right = insert(root->right, value);
/* value == root->value -> do nothing */

BSTを構築する

値の列を挿入すると、挿入順序に応じた形状の木ができます。

ここでは複数の数値を挿入し、順序規則が保たれていることを確認するため、ルートの直接の子を表示します。

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

typedef struct Node { int value; struct Node *left, *right; } Node;

Node *create_node(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 create_node(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 main(void){
    Node *root = NULL;
    int data[] = {10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,data[i]);
    printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
    return 0;
}

反復的な挿入

再帰を使わずに挿入することもできます。ポインターで下へ進み、親を記録しながら空いている場所を探します。

その後、新しいノードを親の正しい側に接続します。

void insert_iter(Node **rootp, int value) {
    Node *cur = *rootp, *parent = NULL;
    while (cur) {
        parent = cur;
        cur = (value < cur->value) ? cur->left : cur->right;
    }
    Node *n = create_node(value);
    if (!parent) *rootp = n;
    else if (value < parent->value) parent->left = n;
    else parent->right = n;
}

挿入順序が木の形を決める

1、2、3、4、5をソート済みの順序で挿入すると、リンクリストのような退化した木になり、高さは要素数と等しくなります。

バランスのよい順序で挿入すると、高さをlog(n)に近く保てます。バランスは検索速度に直接影響します。

/* sorted insert 1..5 ->
 * 1
 *  \
 *   2
 *    \
 *     3   (height = 4, like a list)
 */

挿入のコスト

各挿入ではルートから葉までの1本の経路をたどるため、木の高さに比例する処理量になります。

バランスのよい木ではおよそlog(n)回の比較ですが、退化した木ではn回になる場合があります。これが自己平衡木が存在する理由です。

完全な挿入デモ

このプログラムは値を挿入した後、ノード数を数えて、重複しない5つの値が格納され、重複値が無視されたことを確認します。

重複する10を挿入しても個数が増えないのは、insertが同じ値を破棄するためです。

#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 count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }

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

簡単な確認

挿入の動作について考えてみましょう。

まとめ

BSTへの挿入では、新しい値を各ノードと比較し、小さければ左へ、大きければ右へ進み、空いている位置が見つかるまで繰り返します。

再帰形式では部分木のルートを返すため、親ノードはリンクをきれいに付け直せます。挿入コストは木の高さに応じて増えるため、挿入順序が重要です。

よくある質問

「BSTに挿入する」レッスンは無料ですか？

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

「BSTに挿入する」で何を学びますか？

二分探索木を構築します。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「BSTに挿入する」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

  1. 木構造のノードと構造
  2. BSTに挿入する
  3. 走査
  4. 検索と解放
← C Academyに戻る