アルゴリズム

[C言語] 2分木の基本と実装方法

2分木(バイナリツリー)は、各ノードが最大で2つの子ノードを持つデータ構造です。

基本的な要素は「ノード」で、各ノードにはデータと2つのポインタ(左子と右子)が含まれます。

C言語での実装には、まずノードを表す構造体を定義し、次にノードを動的に割り当てるための関数を作成します。

挿入、削除、探索などの操作は再帰的に行われることが多いです。

これにより、データの効率的な管理と検索が可能になります。

目次から探す

2分木の基本

2分木とは

2分木(にぶんぎ)とは、各ノードが最大で2つの子ノードを持つことができる木構造の一種です。

2分木は、データを階層的に管理するための基本的なデータ構造であり、さまざまなアルゴリズムやデータベースの基盤として利用されます。

2分木の各ノードは、データ要素と、左の子ノードおよび右の子ノードへのポインタを持っています。

2分木の特徴

2分木には以下のような特徴があります。

特徴	説明
階層構造	ノードが階層的に配置され、親子関係を持つ
最大2つの子ノード	各ノードは最大で2つの子ノードを持つことができる
再帰的構造	各子ノードもまた2分木であるため、再帰的に処理が可能

このような特徴により、2分木はデータの効率的な管理や検索に適しています。

2分木の用途

2分木はさまざまな用途で利用されます。

以下に代表的な用途を示します。

用途	説明
データ検索	二分探索木として利用することで、効率的なデータ検索が可能
データの整列	ヒープとして利用することで、効率的なデータの整列が可能
データの管理	データベースやファイルシステムでのデータ管理に利用

これらの用途により、2分木は多くのプログラムやシステムで重要な役割を果たしています。

2分木の構造

ノードの構成

2分木の基本単位であるノードは、以下の要素で構成されています。

要素	説明
データ	ノードが保持する情報。整数や文字列など、任意のデータ型が格納可能
左の子ノードへのポインタ	左側の子ノードを指すポインタ
右の子ノードへのポインタ	右側の子ノードを指すポインタ

この構成により、ノードは他のノードとリンクし、木全体の構造を形成します。

左右の子ノード

2分木の各ノードは、最大で2つの子ノードを持つことができます。

これらは「左の子ノード」と「右の子ノード」として区別されます。

左右の子ノードは、それぞれのポインタを通じて親ノードと接続され、木の構造を形成します。

左の子ノード: 親ノードの左側に位置するノード。

通常、親ノードよりも小さい値を持つことが多い。

右の子ノード: 親ノードの右側に位置するノード。

通常、親ノードよりも大きい値を持つことが多い。

この左右の子ノードの概念は、特に二分探索木において重要な役割を果たします。

根ノードと葉ノード

2分木には特別なノードとして「根ノード」と「葉ノード」が存在します。

根ノード: 木の最上部に位置するノードで、親ノードを持たない唯一のノードです。

木全体のエントリーポイントとして機能します。

葉ノード: 子ノードを持たないノードで、木の末端に位置します。

データの終端を示すノードとして機能します。

根ノードから葉ノードまでの経路をたどることで、木全体のデータを探索することができます。

これにより、2分木は効率的なデータ管理と検索を可能にします。

2分木の基本操作

ノードの挿入

2分木にノードを挿入する操作は、特定のルールに従って行われます。

以下は、二分探索木におけるノードの挿入の基本的な手順です。

#include <stdio.h>
#include <stdlib.h>
// ノードの定義
typedef struct Node {
    int data; // データ
    struct Node* left; // 左の子ノード
    struct Node* right; // 右の子ノード
} Node;
// 新しいノードを作成する関数
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// ノードを挿入する関数
Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    return root;
}

このコードでは、新しいノードを作成し、適切な位置に挿入することで、2分木を構築します。

ノードの削除

ノードの削除は、削除するノードの子ノードの数によって処理が異なります。

以下は、基本的な削除操作の例です。

// 最小値のノードを見つける関数
Node* findMin(Node* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}
// ノードを削除する関数
Node* deleteNode(Node* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

このコードは、削除するノードが持つ子ノードの数に応じて、適切にノードを削除します。

ノードの探索

ノードの探索は、木の構造を利用して効率的に行われます。

以下は、探索の基本的な例です。

// ノードを探索する関数
Node* searchNode(Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return searchNode(root->left, data);
    }
    return searchNode(root->right, data);
}

このコードは、指定されたデータを持つノードを探索し、見つかった場合はそのノードを返します。

木の巡回方法

2分木の巡回には、主に以下の3つの方法があります。

巡回方法	説明
前順巡回 (Pre-order)	根ノード、左の子ノード、右の子ノードの順に巡回
中順巡回 (In-order)	左の子ノード、根ノード、右の子ノードの順に巡回
後順巡回 (Post-order)	左の子ノード、右の子ノード、根ノードの順に巡回

以下は、中順巡回の例です。

// 中順巡回を行う関数
void inOrderTraversal(Node* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

このコードは、2分木を中順巡回し、ノードのデータを順に出力します。

中順巡回は、二分探索木においてデータを昇順に出力するのに適しています。

2分木の実装例

ノードの作成関数

2分木のノードを作成するための関数は、ノードのメモリを動的に確保し、初期化を行います。

以下はその実装例です。

#include <stdio.h>
#include <stdlib.h>
// ノードの定義
typedef struct Node {
    int data; // データ
    struct Node* left; // 左の子ノード
    struct Node* right; // 右の子ノード
} Node;
// 新しいノードを作成する関数
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("メモリの確保に失敗しました。\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

この関数は、新しいノードを作成し、データを設定して返します。

挿入関数の実装

ノードを2分木に挿入する関数は、適切な位置を見つけて新しいノードを追加します。

以下はその実装例です。

// ノードを挿入する関数
Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    return root;
}

この関数は、再帰的に木を探索し、適切な位置にノードを挿入します。

削除関数の実装

ノードを削除する関数は、削除するノードの子ノードの数に応じて異なる処理を行います。

以下はその実装例です。

// 最小値のノードを見つける関数
Node* findMin(Node* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}
// ノードを削除する関数
Node* deleteNode(Node* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

この関数は、削除するノードの子ノードの数に応じて、適切にノードを削除します。

探索関数の実装

ノードを探索する関数は、指定されたデータを持つノードを見つけます。

以下はその実装例です。

// ノードを探索する関数
Node* searchNode(Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return searchNode(root->left, data);
    }
    return searchNode(root->right, data);
}

この関数は、再帰的に木を探索し、指定されたデータを持つノードを返します。

完成したプログラム

以下は、これまでに紹介した関数を組み合わせた2分木の基本的なプログラムです。

#include <stdio.h>
#include <stdlib.h>
// ノードの定義
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;
// 新しいノードを作成する関数
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("メモリの確保に失敗しました。\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// ノードを挿入する関数
Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    return root;
}
// 最小値のノードを見つける関数
Node* findMin(Node* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}
// ノードを削除する関数
Node* deleteNode(Node* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}
// ノードを探索する関数
Node* searchNode(Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return searchNode(root->left, data);
    }
    return searchNode(root->right, data);
}
// 中順巡回を行う関数
void inOrderTraversal(Node* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}
int main() {
    Node* root = NULL;
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 20);
    root = insertNode(root, 40);
    root = insertNode(root, 70);
    root = insertNode(root, 60);
    root = insertNode(root, 80);
    printf("中順巡回: ");
    inOrderTraversal(root);
    printf("\n");
    printf("ノード 20 を削除\n");
    root = deleteNode(root, 20);
    printf("中順巡回: ");
    inOrderTraversal(root);
    printf("\n");
    printf("ノード 30 を削除\n");
    root = deleteNode(root, 30);
    printf("中順巡回: ");
    inOrderTraversal(root);
    printf("\n");
    printf("ノード 50 を削除\n");
    root = deleteNode(root, 50);
    printf("中順巡回: ");
    inOrderTraversal(root);
    printf("\n");
    return 0;
}

中順巡回: 20 30 40 50 60 70 80 
ノード 20 を削除
中順巡回: 30 40 50 60 70 80 
ノード 30 を削除
中順巡回: 40 50 60 70 80 
ノード 50 を削除
中順巡回: 40 60 70 80

このプログラムは、2分木にノードを挿入し、削除し、そして中順巡回を行ってノードのデータを出力します。

実行すると、ノードの挿入と削除の結果を確認できます。

2分木の応用例

二分探索木への応用

二分探索木(Binary Search Tree, BST)は、2分木の一種で、各ノードが特定の順序に従って配置されるように設計されています。

具体的には、任意のノードにおいて、左の子ノードの値はそのノードの値より小さく、右の子ノードの値はそのノードの値より大きくなります。

この特性により、二分探索木は効率的なデータ検索、挿入、削除を可能にします。

検索の効率化: 平均的な場合、探索の時間計算量はO(log n)であり、線形探索よりも高速です。
データの整列: 中順巡回を行うことで、ノードのデータを昇順に取得できます。

二分探索木は、データベースや検索アルゴリズムの基盤として広く利用されています。

平衡二分木への応用

平衡二分木は、二分探索木の一種で、木の高さを最小限に保つように設計されています。

これにより、最悪の場合でも効率的な操作が可能になります。

代表的な平衡二分木には、以下のようなものがあります。

AVL木: 各ノードの左右の部分木の高さの差が1以下になるように調整されます。
赤黒木: ノードに色(赤または黒)を持たせ、特定の色のルールに従って木を平衡に保ちます。

平衡二分木は、データの挿入や削除が頻繁に行われるアプリケーションで、パフォーマンスを向上させるために使用されます。

ヒープへの応用

ヒープは、2分木の特性を利用したデータ構造で、特に優先度キューの実装に適しています。

ヒープには以下の2種類があります。

最大ヒープ: 親ノードの値が子ノードの値よりも常に大きい。
最小ヒープ: 親ノードの値が子ノードの値よりも常に小さい。

ヒープは、以下のような用途で利用されます。

優先度キュー: 優先度の高い要素を効率的に取り出すことができる。
ヒープソート: ヒープの特性を利用して、効率的にデータを整列するアルゴリズム。

ヒープは、特にリアルタイムシステムやスケジューリングアルゴリズムで重要な役割を果たします。

2分木の利点と欠点

2分木の利点

2分木には、以下のような利点があります。

効率的なデータ検索: 二分探索木として利用することで、平均的な検索時間がO(log n)となり、線形探索よりも高速です。
データの整列: 中順巡回を行うことで、ノードのデータを昇順に取得でき、データの整列が容易です。
柔軟なデータ管理: 挿入や削除が比較的簡単に行えるため、動的なデータ管理に適しています。
再帰的な処理: 再帰的なアルゴリズムを用いることで、実装がシンプルになります。

これらの利点により、2分木は多くのアルゴリズムやデータベースで利用されています。

2分木の欠点

一方で、2分木には以下のような欠点もあります。

不均衡な木の問題: 挿入順序によっては、木が不均衡になり、最悪の場合、線形リストと同じO(n)の時間計算量になることがあります。
メモリのオーバーヘッド: 各ノードがポインタを持つため、メモリの使用量が増加します。
複雑な削除操作: ノードの削除は、特に子ノードを持つ場合に複雑で、実装が難しいことがあります。

これらの欠点を克服するために、平衡二分木や他のデータ構造が利用されることがあります。

他のデータ構造との比較

2分木は、他のデータ構造と比較して、特定の用途において優れた特性を持っています。

以下に、2分木と他のデータ構造の比較を示します。

データ構造	利点	欠点
2分木	効率的な検索と整列	不均衡な木の問題
リンクリスト	挿入と削除が容易	検索が遅い
配列	インデックスによる高速アクセス	挿入と削除が遅い
ハッシュテーブル	高速な検索	順序が保証されない