Java の木の究極ガイド: 根から枝 (そして葉も!)

1. 木の紹介

ああ、地味な木ですね。窓の外にある単なる葉っぱの構造ではなく、コンピューター サイエンスにおける基本的な多目的データ構造です。ツリーは、ファイル システムから式の解析、データベースの管理に至るまで、あらゆる場所に存在します。木を理解することは木に登るように感じるかもしれませんが、心配しないでください。私があなたのハーネス、ヘルメット、そしてこの旅のガイドになります。

2. ツリーとは何ですか?

ツリーは、エッジで接続されたノードで構成される階層データ構造です。楽しいことやゲームばかりだった子供の頃のツリーハウスとは異なり、コンピューター サイエンスのツリーは真剣なビジネスです:

• ルート ノード: 会社の CEO などの出発点であり、最終的には全員がその下に報告されます。
• 子ノード: 別のノード (親) の下に直接接続されているノード。
• 親ノード: 子の直上のノード (保護者など)。
• リーフノード: 子のないノード。彼らは最終ライン (別名、退職前の最後の従業員) です。
• サブツリー: より大きな構造内のミニツリー。独自の分裂チームを形成している可能性があります。
• 深さ: ルートから特定のノードまでのエッジの数。
• 高さ: ノードから最も深いリーフまでのエッジの数。

3. なぜ木なのか?目的

そもそもなぜ木を使うのでしょうか?質問してよかったです。木は次のような用途に最適です:

• 階層データ表現: ファイル システム、組織構造、デシジョン ツリー。
• 検索と並べ替え: 二分探索木 (BST) は O(log n) 時間で検索できます。
• データ管理: データベース (B ツリー) などの効率的な保存と取得。
• 動的データ: ツリーは、サイズやコンテンツが動的に変化する構造が必要な場合に最適です。

4. 木の種類とその使用例

4.1 バイナリツリー

• 定義: 各ノードには最大 2 つの子 (左と右) があります。
• 目的: シンプルで効率的なトラバース。階層データとバイナリ式の表現に最適です。

4.2 二分探索木 (BST)

• 定義: 制約が追加されたバイナリ ツリー。左側の子ノードは親ノードより小さく、右側の子ノードは大きくなります。
• 目的: 高速な検索、挿入、削除。

• コード例:
  

  class TreeNode {
      int value;
      TreeNode left, right;
  
      public TreeNode(int item) {
          value = item;
          left = right = null;
      }
  }
  
  

4.3 バランスの取れたツリー (AVL、赤黒など)

• AVL ツリー: 左右のサブツリーの高さの差が 1 を超えることができない自己平衡型二分探索ツリー。
• 赤黒ツリー: 他のパスの 2 倍を超える長さのパスがないことを保証するプロパティを備えたバランスの取れた二分探索ツリーです。
• 目的: 挿入、削除、検索操作に O(log n) 時間を維持します。

4.4 N 分木

• 定義: 各ノードが最大 N 個の子を持つことができるツリー。
• 目的: バイナリ ツリーよりも柔軟で、ファイル システムなどのより複雑な構造を表すためによく使用されます。

4.5 トライ (プレフィックスツリー)

• 定義: 各ノードが文字を表す文字列を格納するために使用されるツリー。
• 目的: 単語と接頭辞の高速検索 (オートコンプリート機能など)。

4.6 セグメントツリーとフェンウィックツリー

• セグメント ツリー: 配列に対する範囲クエリに効率的に答えるために使用されます。
• フェンウィック ツリー: 累積度数表に使用される、よりシンプルでスペース効率の高いツリー。

5. ツリートラバーサルテクニック

木を横断することは、社内のすべての従業員を訪問するようなものです。どのように行うかが重要です:

5.1 深さ優先検索 (DFS)

• 予約注文: ルートにアクセスし、次に左にアクセスし、次に右にアクセスします。ツリーのコピーを作成するのに最適です。
• 順序: 左、ルート、右。 BST が要素を昇順で取得するのに役立ちます。
• ポストオーダー: 左、右、ルート。ツリーの削除に適しています (逆階層の従業員を解雇するなど)。

DFS の例:

void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.print(node.value + " ");
    inOrder(node.right);
}

5.2 幅優先検索 (BFS)

• レベル順トラバーサル: レベルごとにノードを訪問します。最短経路問題に最適です。

• キューを使用した実装:
  

  class TreeNode {
      int value;
      TreeNode left, right;
  
      public TreeNode(int item) {
          value = item;
          left = right = null;
      }
  }
  
  

6. ツリーアルゴリズムとその応用

6.1 BST の挿入と削除

• 挿入: 新しいノードを正しい位置に再帰的に配置します。
• 削除: 3 つのケース - リーフ ノードの削除、1 つの子、および 2 つの子 (順序どおりの後続ノードと置換)。

6.2 ツリーのバランスをとる

• 回転: AVL および赤黒ツリーでバランスを維持するために使用されます。
  • 片右回転 (LL 回転)
  • 単一左回転 (RR 回転)
  • 左右二重回転 (RL 回転)
  • 左右二重回転 (LR 回転)

6.3 最下位共通祖先 (LCA) 問題

• 定義: 指定された 2 つのノードの祖先である最下位のノードを検索します。
• 手法: 現在のノードが指定された 2 つのノードに共通であるかどうかを再帰的にチェックします。

LCA コード例:

void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.print(node.value + " ");
    inOrder(node.right);
}

7. 木の記憶配置

ツリーは通常、以下を使用してメモリ内で表現されます。

• 動的ノードベースの表現: 各ノードは、その子へのポインター (参照) を持つオブジェクトです。
• 配列表現: 左の子が 2*i 1 にあり、右の子が 2*i 2 (0 インデックス付き) にある完全なバイナリ ツリーに使用されます。

視覚的表現:

void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.value + " ");
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

8. ツリーに適した問題の特定

木がその仕事に適した道具であるかどうかはどうやってわかりますか?次の兆候を探してください:

• 階層データ: 家系図、組織図。
• 高速検索: オートコンプリート、スペルチェック。
• 範囲クエリ: 範囲の合計または最小値。
• 親子関係: ルートまで追跡する必要がある関係に関わる問題。

9. ツリーの問題を解決するためのヒントとコツ

• 再帰的思考: ほとんどのツリーの問題には、本質的に再帰的な性質があります。左右のサブツリーの問題をどのように解決するかを考えて組み立ててください。
• 視覚化: 直接コーディングしている場合でも、常にツリーを描画します。エッジケースをマッピングするのに役立ちます。
• エッジケース: ノードが 1 つだけ、すべての左側のノード、またはすべての右側のノードを持つツリーに注意してください。 null ノードについても忘れないでください!
• バランスのとれたツリー: 一貫して高速なパフォーマンスが必要な場合は、ツリーのバランスが保たれていることを確認してください (AVL または Red-Black ツリーを使用します)。

10. 木の現実世界への応用

• データベース: インデックス作成用の B ツリーおよびバリアント (B ツリーなど)。
• コンパイラー: 解析用の抽象構文ツリー (AST)。
• AI: 機械学習アルゴリズムのデシジョン ツリー。
• ネットワーク: ルーターとパスファインディング用のスパニング ツリー。

11. ツリーインタビューでよくある質問

1. バイナリツリーの最大パス合計
2. 対称ツリーチェック
3. バイナリ ツリーのシリアル化と逆シリアル化
4. 二分木の直径
5. ツリーのバランスが取れているかどうかを確認します

---

結論

ツリーをマスターするということは、再帰を受け入れ、自分のタイプを知り、問題を通して練習することです。木を単なるデータ構造としてではなく、バランスと手入れが必要な生き物として捉え始めると、その力を理解できるようになります。自社のツリーを熟知している開発者は常に他の開発者よりも優れているということを忘れないでください!

コーディング (そして登山) を楽しんでください! ?

以上がJava の木の究極ガイド: 根から枝 (そして葉も!)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。