10日で覚えるData Structure & AlgorithmDay 7: 木構造と二分探索木
第 710日で覚えるData Structure & Algorithm

Day 7: 木構造と二分探索木

今日学ぶこと

  • 木構造の基本概念と用語
  • 二分木と走査（トラバーサル）
  • 二分探索木（BST）の実装
  • BSTの操作と計算量

木構造とは

木（Tree） は、ノードが親子関係で接続された階層的なデータ構造です。

flowchart TB
    R["Root\n(根)"] --> A["Node A"]
    R --> B["Node B"]
    A --> C["Leaf C\n(葉)"]
    A --> D["Leaf D"]
    B --> E["Leaf E"]
    B --> F["Node F"]
    F --> G["Leaf G"]
    style R fill:#3b82f6,color:#fff
    style A fill:#8b5cf6,color:#fff
    style B fill:#8b5cf6,color:#fff
    style C fill:#22c55e,color:#fff
    style D fill:#22c55e,color:#fff
    style E fill:#22c55e,color:#fff
    style F fill:#8b5cf6,color:#fff
    style G fill:#22c55e,color:#fff

用語

用語 説明
根（Root） 最上位のノード
葉（Leaf） 子を持たないノード
辺（Edge） ノード間の接続
深さ（Depth） 根からそのノードまでの辺の数
高さ（Height） そのノードから最も遠い葉までの辺の数
部分木（Subtree） あるノードとその子孫全体

二分木（Binary Tree）

各ノードが最大2つの子（左と右）を持つ木です。

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Build a simple binary tree
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

木の走査（Traversal）

flowchart TB
    N1["1"] --> N2["2"]
    N1 --> N3["3"]
    N2 --> N4["4"]
    N2 --> N5["5"]
    N3 --> N6["6"]
    N3 --> N7["7"]
    style N1 fill:#3b82f6,color:#fff
    style N2 fill:#8b5cf6,color:#fff
    style N3 fill:#8b5cf6,color:#fff
    style N4 fill:#22c55e,color:#fff
    style N5 fill:#22c55e,color:#fff
    style N6 fill:#22c55e,color:#fff
    style N7 fill:#22c55e,color:#fff

深さ優先探索（DFS）

// Pre-order: Root → Left → Right (前順)
function preOrder(node) {
  if (!node) return [];
  return [node.value, ...preOrder(node.left), ...preOrder(node.right)];
}
// Result: [1, 2, 4, 5, 3, 6, 7]

// In-order: Left → Root → Right (中順)
function inOrder(node) {
  if (!node) return [];
  return [...inOrder(node.left), node.value, ...inOrder(node.right)];
}
// Result: [4, 2, 5, 1, 6, 3, 7]

// Post-order: Left → Right → Root (後順)
function postOrder(node) {
  if (!node) return [];
  return [...postOrder(node.left), ...postOrder(node.right), node.value];
}
// Result: [4, 5, 2, 6, 7, 3, 1]

幅優先探索（BFS）/ レベル順走査

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}
// Result: [1, 2, 3, 4, 5, 6, 7]
走査方法 順序 用途
前順（Pre-order） Root→Left→Right 木のコピー
中順（In-order） Left→Root→Right BSTのソート出力
後順（Post-order） Left→Right→Root 木の削除
レベル順（Level-order） 上から下、左から右 最短経路探索

二分探索木（BST）

二分探索木（Binary Search Tree） は、以下の性質を持つ二分木です：

  • 左の子孫の値 < 親の値
  • 右の子孫の値 > 親の値
flowchart TB
    N8["8"] --> N3["3"]
    N8 --> N10["10"]
    N3 --> N1["1"]
    N3 --> N6["6"]
    N10 --> N9["9"]
    N10 --> N14["14"]
    N6 --> N4["4"]
    N6 --> N7["7"]
    style N8 fill:#3b82f6,color:#fff
    style N3 fill:#8b5cf6,color:#fff
    style N10 fill:#8b5cf6,color:#fff
    style N1 fill:#22c55e,color:#fff
    style N6 fill:#f59e0b,color:#fff
    style N9 fill:#22c55e,color:#fff
    style N14 fill:#22c55e,color:#fff
    style N4 fill:#22c55e,color:#fff
    style N7 fill:#22c55e,color:#fff

BST の実装

class BST {
  constructor() {
    this.root = null;
  }

  // Insert: O(log n) average, O(n) worst
  insert(value) {
    const node = new TreeNode(value);
    if (!this.root) {
      this.root = node;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = node;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = node;
          return;
        }
        current = current.right;
      }
    }
  }

  // Search: O(log n) average, O(n) worst
  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return current;
      if (value < current.value) current = current.left;
      else current = current.right;
    }
    return null;
  }

  // Find minimum: O(log n) average
  findMin(node = this.root) {
    while (node && node.left) {
      node = node.left;
    }
    return node;
  }

  // Find maximum: O(log n) average
  findMax(node = this.root) {
    while (node && node.right) {
      node = node.right;
    }
    return node;
  }

  // Delete: O(log n) average, O(n) worst
  delete(value, node = this.root, parent = null) {
    while (node) {
      if (value < node.value) {
        parent = node;
        node = node.left;
      } else if (value > node.value) {
        parent = node;
        node = node.right;
      } else {
        // Found the node to delete
        if (node.left && node.right) {
          // Two children: replace with in-order successor
          const successor = this.findMin(node.right);
          node.value = successor.value;
          this.delete(successor.value, node.right, node);
        } else {
          // Zero or one child
          const child = node.left || node.right;
          if (!parent) this.root = child;
          else if (parent.left === node) parent.left = child;
          else parent.right = child;
        }
        return;
      }
    }
  }

  // In-order traversal (sorted output)
  inOrder(node = this.root) {
    if (!node) return [];
    return [...this.inOrder(node.left), node.value, ...this.inOrder(node.right)];
  }
}

const bst = new BST();
[8, 3, 10, 1, 6, 14, 4, 7, 9].forEach(v => bst.insert(v));
console.log(bst.inOrder()); // [1, 3, 4, 6, 7, 8, 9, 10, 14]
console.log(bst.search(6)); // TreeNode { value: 6, ... }
console.log(bst.findMin()); // TreeNode { value: 1 }

BSTの計算量

操作 平均 最悪（偏った木）
検索 O(log n) O(n)
挿入 O(log n) O(n)
削除 O(log n) O(n)
走査 O(n) O(n)

最悪ケースは、ソート済みのデータを順に挿入した場合に発生します（木が直線的になる）。

flowchart TB
    subgraph Balanced["バランスの取れた木"]
        B4["4"] --> B2["2"]
        B4 --> B6["6"]
        B2 --> B1["1"]
        B2 --> B3["3"]
        B6 --> B5["5"]
        B6 --> B7["7"]
    end
    subgraph Skewed["偏った木（最悪ケース）"]
        S1["1"] --> S2["2"]
        S2 --> S3["3"]
        S3 --> S4["4"]
    end
    style Balanced fill:#22c55e,color:#fff
    style Skewed fill:#ef4444,color:#fff

木の高さと検証

// Calculate tree height
function height(node) {
  if (!node) return -1;
  return 1 + Math.max(height(node.left), height(node.right));
}

// Validate BST
function isValidBST(node, min = -Infinity, max = Infinity) {
  if (!node) return true;
  if (node.value <= min || node.value >= max) return false;
  return (
    isValidBST(node.left, min, node.value) &&
    isValidBST(node.right, node.value, max)
  );
}

実践例：ファイルシステム

class FileNode {
  constructor(name, isDirectory = false) {
    this.name = name;
    this.isDirectory = isDirectory;
    this.children = [];
  }

  addChild(node) {
    this.children.push(node);
  }

  // Print tree structure
  print(indent = "") {
    const prefix = this.isDirectory ? "📁 " : "📄 ";
    console.log(indent + prefix + this.name);
    for (const child of this.children) {
      child.print(indent + "  ");
    }
  }
}

const root = new FileNode("src", true);
const components = new FileNode("components", true);
components.addChild(new FileNode("Header.tsx"));
components.addChild(new FileNode("Footer.tsx"));
root.addChild(components);
root.addChild(new FileNode("index.ts"));
root.print();
// 📁 src
//   📁 components
//     📄 Header.tsx
//     📄 Footer.tsx
//   📄 index.ts

まとめ

概念 説明
木 ノードが親子関係で接続された階層構造
二分木 各ノードが最大2つの子を持つ木
BST 左 < 親 < 右の性質を持つ二分木
走査 前順、中順、後順、レベル順
バランス 木の高さが log n に保たれる状態

重要ポイント

  1. BSTの中順走査はソート済みの出力を返す
  2. バランスの取れたBSTは O(log n) で検索・挿入・削除が可能
  3. 偏った木は O(n) に退化する（→ 平衡木で解決）
  4. 木の走査は再帰で自然に実装できる

練習問題

問題1: 基本

二分木の最大深さ（高さ）を求める関数を実装してください。

問題2: 応用

二分木が左右対称（ミラー）かどうかを判定する関数を実装してください。

チャレンジ問題

BSTの2つのノードの最小共通祖先（Lowest Common Ancestor）を見つける関数を実装してください。

参考リンク

次回予告: Day 8では「ヒープと優先度キュー」について学びます。常に最大値・最小値に高速でアクセスできるデータ構造を理解しましょう。