Java | ツリー構造の実践的な操作

ツリー構造の実践的な操作（後半）

前半では、ツリー構造を「実務でどう扱うか」という視点で、 検索・追加・削除・パス取得といった基本操作を整理しました。 後半では、さらに一歩進んで 幅優先探索（BFS）を使った操作、 フィルタリング・集計・権限チェック、 そして 安全性とパフォーマンスを意識したツリー操作設計 を深掘りします。

ツリー構造は「階層を持つデータ」を扱うための最強の道具です。 後半では、その道具を“実務レベルで使いこなす”ための視点を身につけていきます。

幅優先探索（BFS）で階層ごとの処理を行う

DFS は「深く潜る」探索でしたが、 BFS は「横に広く進む」探索です。 階層ごとの処理が必要な場面では、BFS が圧倒的に便利です。

BFS の実務的な用途

階層ごとのノード数を数える 階層ごとに権限チェックを行う 階層ごとに UI を構築する（メニューやフォルダ表示） 階層ごとのログ出力

Java で BFS を使って階層ごとのノード数を数える例を見てみます。

import java.util.*;

public static void countByLevel(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        System.out.println("Level " + level + ": " + size + " nodes");

        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            for (Node child : node.children) {
                queue.add(child);
            }
        }
        level++;
    }
}

import java.util.*;

public static void countByLevel(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        System.out.println("Level " + level + ": " + size + " nodes");

        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            for (Node child : node.children) {
                queue.add(child);
            }
        }
        level++;
    }
}

このコードは、階層ごとにノード数を出力します。 実務では「階層ごとの集計」は非常に多く、BFS がその中心になります。

フィルタリング：条件に合うノードだけを抽出する

ツリー構造では「特定条件に合うノードだけを集めたい」という場面が多くあります。

例 「名前に ‘report’ を含むフォルダだけを抽出したい」 「権限が ‘admin’ のノードだけを抽出したい」 「サイズが 1MB 以上のファイルだけを抽出したい」

DFS を使ったフィルタリングの例を見てみます。

public static void filter(Node root, String keyword, List<Node> result) {
    if (root.name.contains(keyword)) {
        result.add(root);
    }
    for (Node child : root.children) {
        filter(child, keyword, result);
    }
}

public static void filter(Node root, String keyword, List<Node> result) {
    if (root.name.contains(keyword)) {
        result.add(root);
    }
    for (Node child : root.children) {
        filter(child, keyword, result);
    }
}

このメソッドは、ツリー全体を走査しながら 「条件に合うノードだけを result に追加する」処理です。

深掘り：フィルタリングは「探索＋条件判定」の組み合わせ

ツリー構造のフィルタリングは、 探索（DFS または BFS）と条件判定を組み合わせるだけで実現できます。

このシンプルな構造を理解すると、 どんなフィルタリングでも自分で書けるようになります。

集計：ツリー全体の情報をまとめる

ツリー構造では「集計」もよく使われます。

例 フォルダ内のファイル数を数える 組織図で社員数を数える メニュー構造で項目数を数える

DFS を使った集計の例を見てみます。

public static int countNodes(Node root) {
    int count = 1;
    for (Node child : root.children) {
        count += countNodes(child);
    }
    return count;
}

public static int countNodes(Node root) {
    int count = 1;
    for (Node child : root.children) {
        count += countNodes(child);
    }
    return count;
}

このメソッドは、 「自分自身を1として、子の数を足していく」 というシンプルな再帰構造で動きます。

深掘り：集計は「帰りがけ処理」が本質

DFS の「帰りがけ処理」（子の処理が終わった後に自分の処理をする）を使うことで、 集計は非常に自然に書けます。

権限チェック：ツリー構造での実務的な応用

ツリー構造は「権限の継承」を表現するのに非常に向いています。

例 root に admin 権限がある → 子にも継承される docs に read-only 権限がある → 配下の reports も read-only 特定のノードで権限を上書きする

権限チェックの例を見てみます。

public static boolean hasPermission(Node node, String permission) {
    Node current = node;
    while (current != null) {
        if (current.name.equals(permission)) {
            return true;
        }
        current = current.parent;
    }
    return false;
}

public static boolean hasPermission(Node node, String permission) {
    Node current = node;
    while (current != null) {
        if (current.name.equals(permission)) {
            return true;
        }
        current = current.parent;
    }
    return false;
}

このメソッドは「親に向かって権限を探す」処理です。 ツリー構造では「上位の設定が下位に影響する」ことが多いため、 親参照を使った権限チェックは非常に実務的です。

非再帰 DFS：安全性とパフォーマンスを高める

前半でも触れましたが、再帰 DFS は深いツリーで危険です。 攻撃者が「極端に深い JSON」などを送り込むと、 StackOverflowError を誘発する可能性があります。

そのため、実務では「非再帰 DFS」を使うことがあります。

import java.util.Stack;

public static void dfsNonRecursive(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        System.out.println(node.name);

        for (int i = node.children.size() - 1; i >= 0; i--) {
            stack.push(node.children.get(i));
        }
    }
}

import java.util.Stack;

public static void dfsNonRecursive(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        System.out.println(node.name);

        for (int i = node.children.size() - 1; i >= 0; i--) {
            stack.push(node.children.get(i));
        }
    }
}

深掘り：非再帰 DFS のメリット

スタックオーバーフローが起きない 深さが極端に深くても安全 再帰よりも制御しやすい ログやデバッグがしやすい

実務では「安全性のために非再帰 DFS を使う」という判断が非常に重要です。

セキュリティの観点から見たツリー操作の注意点

ツリー構造は便利ですが、攻撃者に悪用される可能性があります。

深さが極端に深いツリー

再帰 DFS が落ちる BFS がメモリを使い果たす 処理時間が異常に長くなる

ノード数が極端に多いツリー

探索が O(n) なので、DoS攻撃の入り口になる フィルタリングや集計が重くなる

安全にするための設計

深さの上限を設ける ノード数の上限を設ける 非再帰 DFS を使う 処理時間のタイムアウトを設ける

ツリー構造は「入力の形に依存する」ため、 セキュリティスペシャリストは常に深さとノード数を監視します。

後半のまとめ

後半では、ツリー構造の実務的な操作をさらに深掘りしました。

BFS を使った階層処理 フィルタリング・集計・権限チェック 非再帰 DFS による安全性向上 セキュリティ・パフォーマンスを意識した設計

ツリー構造は「階層を持つデータ」を扱うための最強の道具です。 その道具を安全かつ効率的に使うためには、 探索アルゴリズムと設計の両方を理解する必要があります。