ツリー

ツリー

ツリーは階層的なデータ構造で、ルート（根）からノード（節）が作られ、最終的にリーフ（葉）にたどり着く。

用語	意味
ノード	節。全ての要素
ルート	根。最上位のノード
ブランチ	枝。ノードとノードをつなぐ

また、ノードは子孫を持つことができ、祖先をもつこともある。

用語	意味
子	直接の子孫
親	直接の祖先
リーフ	葉。子を持たないノード

サブツリーは、ひとつのノードからの以下の全ての子孫のこと。

ツリーの中身を辿って移動していく操作のことを「トラバース」と呼ぶ。

ツリーの種類として、二分木・バイナリツリーがある。これは全ての枝の分岐が2つ以下のツリーのこと。探索などによく使われる。

二分木には、完全二分木（根から葉までがすべて等しい深さとなっている）や二分探索木（左の子は必ず親より小さく、右の子は必ず親より大きい）、ヒープ木などがある。

ヒープは完全二分木の一種で、「常に子が親より大きい」の場合と、「常に子が親より小さい」の場合のどちらかになるように整列される。最大値または最小値を求めるのに適している。

また、ツリーの応用例として、構文の意味と構造を解析する構文解析ツリーや、HTMLやXMLのドキュメント要素をツリー構造にしたDOMツリーなどがある。

（Ruby Way 第2版 (Professional Ruby Series)を参考に執筆しました。）

• 徹底攻略 応用情報技術者教科書 平成30年度
• Code Reading ~オープンソースから学ぶソフトウェア開発技法~ (プレミアムブックス版)
• 平成18年度 イメージ&クレバー方式でよくわかる栢木先生の基本情報技術者教室 (情報処理技術者試験)

二分木による単語のカウント

データ構造を用いたテクニックとして、たとえばテキスト内の単語の数を数えるなどといった問題を解決する場合、単語が既に出現した単語であるかどうか、全単語さかのぼって検索するのは時間がかかります。

このような時、二分木を用いて、ひとつの単語（たとえばopen）があった時、その単語よりもアルファベット順に前の単語（たとえばcat）があれば、それをopenのツリーの下の左の要素とし、アルファベット順に後の単語であれば、ツリーの下の右の要素とします。

このようにすることで、アルファベット順に前か後どちらかの単語がでてきたら、もう一方の木を検索することが必要なく、最短で一致する単語を検索できます。

このツリーを常に保持し、整理された状態を維持することで、とても効率的に単語を検索できます。

ほかにも、ポインタを上手く使うことで、データの構造が効率的になることがあります。

テキストを行単位で整理するのであれば、文字列（行）へのポインタの配列を作り、行を入れ替える際にはポインタだけを交換すればいいのです。

ポインタを使うもうひとつの例として、データ構造とは関係ありませんが、関数ポインタを使うことで、「場合によって別の関数を呼び出す」ことができ、これはソートのプログラムなどで、場合によって別のアルゴリズムでソートを行う場合などに有用です。

（詳しくはプログラミング言語C（K&R）が参考になります。）

ツリーを作るのは簡単

実際のところ、C言語でツリーを作るのは意外と簡単です。

要するに、親要素へのポインタと、子要素へのポインタ（二分木であれば右と左の二つ）、そして要素が値を保持するためのデータ変数を、構造体として持てばいいだけだからです。

連結リスト、双方向リスト、グラフなども、同様の方法で作れます。単にポインタの参照の仕方が変わるだけです。

ただし、トラバース（木を辿っていく操作）を作るのは少し難易度が高めかもしれません。ひとつひとつ子を参照するのは簡単ですが、右と左のどちらに子があるのかを判断するのが難しいでしょう。

ハッシュテーブルも難易度が高めですが、配列の中にリストへのポインタを格納するようにすれば作れます。あるいは、キーのハッシュ値を配列の添え字にする方法でも作れます。

詳しい作り方は、以下の書籍に書かれているので、参照してください。

• Code Reading ~オープンソースから学ぶソフトウェア開発技法~ (プレミアムブックス版)

データベースインデックスも参照のこと。

AIによるサンプル

以下はGoogleのAIが書いた二分探索木のサンプルコード。

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

// ノードの構造体定義
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

// 新しいノードを作成する関数
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "メモリ確保に失敗しました\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 二分探索木に値を挿入する関数
Node* insert(Node* node, int value) {
    // 空の場所を見つけたら新しいノードを配置
    if (node == NULL) return createNode(value);

    // 値を比較して左右に振り分ける
    if (value < node->data) {
        node->left = insert(node->left, value);
    } else if (value > node->data) {
        node->right = insert(node->right, value);
    }
    return node;
}

// 値を探索する関数
Node* search(Node* root, int key) {
    // 見つからない、または値が一致した場合
    if (root == NULL || root->data == key) return root;

    // キーが現在のノードより小さければ左、大きければ右を探索
    if (key < root->data) return search(root->left, key);
    return search(root->right, key);
}

// 通りがけ順（Inorder）で表示（昇順に出力される）
void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    Node* root = NULL;

    // データの挿入
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("木の中身（昇順）: ");
    inorder(root);
    printf("\n");

    // 探索のテスト
    int target = 60;
    if (search(root, target) != NULL) {
        printf("値 %d は木の中に存在します。\n", target);
    } else {
        printf("値 %d は見つかりませんでした。\n", target);
    }

    return 0;
}

関連ページ

アルゴリズム

具体的なアルゴリズムも参照のこと。