二分探索木と3つの巡回 — 木にしたのに一直線になる

二分探索木と巡回。左右に枝分かれするデータ模型と経路を追う虫眼鏡。

木にしたのに一直線になることがあります。二分探索木と3つの巡回を実装して、形が崩れる条件を見ます。

前回: ハッシュテーブル — 10万件のincludesで止まる

これは【深掘り】の記事です。本線の順路ではありません。 本線のデータ構造を自作する回で「配列は先頭への挿入が遅い」「リストは途中を探すのが遅い」ところまでやった人が、「では、探すのが速い入れ物はどういう形をしているのか」を確かめるための記事です。飛ばしても本線は進みます。

この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。 VM に Node.js が入っている必要があります。 入れ方は本線のnpmの回にあります。node -v で v20 以上が出れば大丈夫です。 作業場所は ~/cslab/tree/ です。 この記事のためだけに新しく作り、最後に全部消します。 既存のプロジェクトには触りません。 記事に出てくる測定値は私のVMの数字です。 皆さんの数字とは違います。見てほしいのは絶対値ではなく、入れる順番を変えたときに何倍になるかです。


対象レベル: 中級〜上級 / 区分: 発展

目次

木の説明を3回読んで、3回とも何も残らなかった

私は「木構造」の説明を、少なくとも3回読みました。

1回目は入門書です。丸と線の絵があって、上に1つ、下に2つ、その下に4つ、と広がっていました。「根」「葉」「節点」という言葉が並んでいました。絵は分かりました。 そして、その日から一度も使いませんでした。

2回目は面接対策の記事です。「二分探索木の探索は O(log n)」と太字で書いてありました。覚えました。 覚えただけでした。

3回目は、in-order / pre-order / post-order の説明です。矢印が丸のまわりをぐるっと回っている絵があって、「この順番で通ります」と書いてありました。私はこの3つを語呂で暗記しようとして、失敗しました。

この3回に共通していたのは、私が一度もコードを書かなかったことです。

そして、書いていなかったせいで、私は次のことを一度も疑いませんでした。

二分探索木に n 件入れたら、探索は log n 回で終わる。

これは嘘です。 正確には、条件付きの話を、条件を落として覚えていました。

この記事の⑥で、実際に測ります。先に結果だけ出します。同じ40000件を、入れる順番だけ変えた結果です。

--- 並んでいる順 (1,2,3,...) (40000件) ---
  木の高さ        : 39999
  1件あたり比較   : 20000.5 回
--- ばらばらの順 (40000件) ---
  木の高さ        : 37
  1件あたり比較   : 18.9 回

1件探すのに 20000 回。 log2(40000) は約 15 です。15 のはずが 20000 でした。

1000倍以上外れています。 そして外れた原因は、バグでもなく、実装ミスでもなく、「データが最初から並んでいた」ことだけでした。

私が書いたコードは1文字も間違っていませんでした。 それでも、木は木にならず、右に一直線に伸びた連結リストになっていました。

この記事は、丸と線の絵を眺める記事ではありません。 木を自分で作って、わざと一直線に壊して、高さを数える記事です。

この記事でわかること

  • 「木」の条件は「親が1つ・子が複数・輪にならない」の3つだけであること。丸と線の絵は木の説明ではなく、ディレクトリ・DOM・JSON・組織図が全部同じ形だったという話
  • 「輪にならない」は飾りの条件ではないこと。輪を1本足すだけで、たどるコードは Maximum call stack size exceeded で止まり、JSON.stringify も失敗する(実際に出します)
  • 二分探索木の「左は小さい・右は大きい」という1つの規則だけで、探索が「候補を半分ずつ捨てる」になること。1023件を10回の比較で当てる過程を、残り候補数付きで表示します
  • 削除だけが本当に難しいこと。子が0個・1個は3行で終わるのに、子が2個のときだけ「別の値を持ってきて、そいつを消し直す」という手順になる
  • 3つの巡回は暗記するものではないこと。「左を見る・自分を処理する・右を見る」の3行を並べ替えただけで、名前は結果に付いたラベルにすぎない
  • in-order で出すとソート済みで出てくること。そしてその並びで木を作り直すと、木が一直線に潰れる(同じ記事の中で2回、同じ現象に出会います)
  • 並んでいるデータを順に入れると、二分探索木は連結リストになること。高さ 39999、左の子を持つ節点が 0 件。これがバランス木が必要な理由そのもの
  • 一直線の木は、再帰の巡回で落ちること。20000件で Maximum call stack size exceeded。9637件目まで進んで止まりました。明示的なスタックに置き換えると 200000 件でも通ります

この記事でやること

  1. ~/cslab/tree/ を作り、まず自分のフォルダを find で表示して、それが木であることを確かめる。JSON も同じ形であることをコードで出し、輪を1本足して壊す
  2. 用語(根・葉・深さ・高さ・部分木)を、コードの出力と文字で描いた図で片づける。二分木・完全二分木・全二分木の違いもここで
  3. 二分探索木を書く(insert / search / min / max / delete)。探索の経路を表示して「半分ずつ捨てる」ところを見る。削除の3パターンは、消した後の木を毎回描いて確かめる
  4. 3つの巡回を書いて、同じ木を3通りで出力して並べる。post-order でディレクトリの合計サイズを出し、pre-order で木をコピーする
  5. 幅優先(レベル順)を、前回のキューで書く
  6. 山場。並んだデータを入れて木を一直線にし、高さと探索時間を10000/20000/40000件で実測して表にする
  7. 再帰版の巡回をわざと落とし、明示的なスタックのループ版に書き換えて、~/cslab/ を消す

先に知る言葉

この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。

言葉意味
木(tree)親が1つ、子は複数持ってよく、輪にならないつながり方。この3つが条件で、絵の形は条件ではない
節点 / ノード(node)木の1個分。値と、子への参照を持っている
根(root)親がいない、いちばん上の1つ。木には必ず1つだけある
葉(leaf)子がいない節点。木のいちばん外側
深さ(depth)根からその節点までの距離。根の深さは 0
高さ(height)その節点から、いちばん遠い葉までの距離。深さは上から数え、高さは下から数える。木全体の高さ=根の高さ
部分木(subtree)ある節点と、その下に付いている全部。部分木もそれ自体が木なので、同じ関数をそのまま呼べる
二分木(binary tree)子を最大2つまでに限った木。左の子と右の子、と名前が付く
二分探索木(BST)二分木のうち、どの節点でも「左の部分木は全部その節点より小さい・右の部分木は全部大きい」を守っているもの
バランスが取れている左右の部分木の高さがほぼ同じ。崩れると探索が O(log n) から O(n) に落ちる。この記事の⑥で崩します
N分木 / K分木子を最大 N 個持てる木。ディレクトリも DOM も N分木。子の数に上限が無い形のほうが、身の回りには多い
巡回 / 走査(traversal)木の全部の節点を1回ずつ見て回ること。順番の違いで3〜4種類ある

① 木は覚えるものではなく、すでに使っているもの

まず作業場所を作ります。

bash
$ mkdir -p ~/cslab/tree
$ cd ~/cslab/tree
$ node -v
v22.14.0

v20 以上なら大丈夫です。 出ない場合は本線のnpmの回に戻ってください。

この記事では npm install を1回もしません。ライブラリは使いません。 使うと、正体を確かめるという目的が消えます。

package.json だけ置きます。import を使うためです。

bash
$ cat > package.json <<'EOF'
  { "name": "tree", "type": "module" }
  EOF

"type": "module" の意味は「このフォルダの .js は ESM(import / export が使える形式)として読む」です。これが無いと import が構文エラーになります。

自分のフォルダを表示してみる

木の絵を見る前に、すでに手元にあるものを見ます。

練習用に、少し階層のあるフォルダを作ります。

bash
$ mkdir -p sample/docs/2026/09 sample/docs/2026/10 sample/src/lib sample/src/bin
$ printf 'hello\n'            > sample/README.md
$ printf '# 9月のメモ\n'      > sample/docs/2026/09/a.md
$ printf '# もう1本\n'        > sample/docs/2026/09/b.md
$ printf '# 10月\n'           > sample/docs/2026/10/c.md
$ printf 'console.log(1)\n'   > sample/src/index.js
$ printf 'export const x = 1\n' > sample/src/lib/util.js
$ printf '#!/bin/sh\necho run\n' > sample/src/bin/run.sh

木の形で見たいので tree コマンドを打ちます。

bash
$ tree sample
Command 'tree' not found, but can be installed with:
sudo apt install tree

素の Ubuntu Server には tree は入っていません。 私の手元でも入っていませんでした。

この記事では入れません。 find で代用します。find は最初から入っています(本線の基本コマンドの回で使いました。組み立て方はfindの深掘りにあります)。

bash
$ find sample | sort
sample
sample/README.md
sample/docs
sample/docs/2026
sample/docs/2026/09
sample/docs/2026/09/a.md
sample/docs/2026/09/b.md
sample/docs/2026/10
sample/docs/2026/10/c.md
sample/src
sample/src/bin
sample/src/bin/run.sh
sample/src/index.js
sample/src/lib
sample/src/lib/util.js

これが木です。

  • sample に親はいません → これが根
  • README.md や a.md は下に何も持ちません → これが葉
  • sample/docs/2026 の親は sample/docs だけ。2つの親を持つフォルダはありません
  • sample/docs の中から sample に戻ってくる道はありません → 輪になっていない

「親が1つ・子が複数・輪にならない」の3つが揃っています。 丸と線の絵ではなく、これが木の定義です。

同じ形のものが、他にもあります。

身の回りのもの根節点葉子の数
ファイルシステム/ディレクトリファイル上限なし(N分木)
HTML の DOM<html>要素テキスト上限なし(N分木)
JSON一番外の {}オブジェクト・配列文字列・数値・真偽値上限なし(N分木)
組織図社長部・課一人ひとり上限なし(N分木)
二分探索木根の節点節点節点最大2つ

身の回りの木は、ほとんど子の数に上限がありません。 「最大2つ」は、探索を速くするために人間が付けた制約です。自然にそうなっているのではありません。

DOM が木であることは、本線のDOM操作の回で parentElement と children を触ったときに、すでに使っていました。parentElement が1つしか無いのは、木だからです。

JSON も木であることを、コードで出す

json-tree.js を作ります。

bash
$ cat > json-tree.js <<'EOF'
  const data = {
    name: 'obmes',
    owner: { name: 'senbo', contact: { mail: 'a@example.com' } },
    posts: [
      { title: '木構造', tags: ['cs', 'tree'] },
      { title: 'キュー', tags: ['cs'] },
    ],
  };
  
  // JSON も木。親が1つ、子が複数、輪にならない
  function walk(node, key = '(root)', depth = 0) {
    const pad = '  '.repeat(depth);
    if (node !== null && typeof node === 'object') {
      const kind = Array.isArray(node) ? '配列' : 'オブジェクト';
      console.log(`${pad}${key} : ${kind}(節点)`);
      for (const [k, v] of Object.entries(node)) walk(v, k, depth + 1);
    } else {
      console.log(`${pad}${key} = ${JSON.stringify(node)}(葉)`);
    }
  }
  
  walk(data);
  
  // 深さを測る
  function maxDepth(node) {
    if (node === null || typeof node !== 'object') return 0;
    const children = Object.values(node);
    if (children.length === 0) return 0;
    return 1 + Math.max(...children.map(maxDepth));
  }
  console.log('');
  console.log('この JSON の深さ:', maxDepth(data));
  EOF
$ node json-tree.js
(root) : オブジェクト(節点)
  name = "obmes"(葉)
  owner : オブジェクト(節点)
    name = "senbo"(葉)
    contact : オブジェクト(節点)
      mail = "a@example.com"(葉)
  posts : 配列(節点)
    0 : オブジェクト(節点)
      title = "木構造"(葉)
      tags : 配列(節点)
        0 = "cs"(葉)
        1 = "tree"(葉)
    1 : オブジェクト(節点)
      title = "キュー"(葉)
      tags : 配列(節点)
        0 = "cs"(葉)

この JSON の深さ: 4

walk は、自分と同じ関数を子に対して呼んでいるだけです。 8行しかありません。

これが木の一番大事な性質です。 部分木もそれ自体が木なので、同じ関数をそのまま子に投げれば、勝手に全部たどれます。 ループを何重にも書く必要がありません。

「輪にならない」を破ってみる

用語の説明でよく出てくる「輪にならない(非巡回)」は、読んでも意味が分かりません。 破ってみます。

bash
$ cat > cycle.js <<'EOF'
  // 「輪にならない」がなぜ条件なのかを、輪を作って確かめる
  const a = { name: 'a', children: [] };
  const b = { name: 'b', children: [] };
  const c = { name: 'c', children: [] };
  a.children.push(b);
  b.children.push(c);
  c.children.push(a);          // ここで輪ができた
  
  let steps = 0;
  function walk(node) {
    steps++;
    for (const child of node.children) walk(child);
  }
  
  try {
    walk(a);
    console.log('終わった');
  } catch (e) {
    console.log(`${e.constructor.name}: ${e.message}`);
    console.log(`${steps} 歩で止まりました。木ではないので、終わりが来ません`);
  }
  
  // JSON にもできない
  try {
    JSON.stringify(a);
  } catch (e) {
    console.log(`JSON.stringify も無理: ${e.constructor.name}`);
  }
  EOF
$ node cycle.js
RangeError: Maximum call stack size exceeded
5695 歩で止まりました。木ではないので、終わりが来ません
JSON.stringify も無理: TypeError

c.children.push(a) の1行を足しただけで、たどるコードが終わらなくなりました。

そして 前回の記事で出したのとまったく同じエラーが出ました。コールスタックが溢れています。

「輪にならない」は、性質の説明ではなく、コードが終わることの保証です。 木だと分かっているから、終了条件を書かずに再帰できるのです。

JSON.stringify が TypeError になるのも同じ理由です。輪があるものは、木の形の文字列にできません。

スクリーンショットを撮ってください: 01_cycle_overflow.png node cycle.js を実行して、Maximum call stack size exceeded と歩数が出ている画面。1行足すだけで壊れることが、この記事の残り全部の前提になります。


② 用語を、図と表で1回だけ片づける

言葉は6つだけです。文字で描いた図で確かめます。

これから作る木を、先に図で出します。

              50            ← 根(親がいない)
             /  \
           30    70
          /  \   / \
        20   40 60  80      ← 20, 60, 80 は葉(子がいない)
             /
           35               ← 35 も葉

この木について、深さと高さを出すコードを書きます。

bash
$ cat > depth.js <<'EOF'
  import { BST } from './bst.js';
  
  const t = new BST();
  for (const v of [50, 30, 70, 20, 40, 60, 80, 35]) t.insert(v);
  
  function walk(node, depth = 0) {
    if (node === null) return;
    const kind = node.left === null && node.right === null ? '葉'
      : node.left !== null && node.right !== null ? '子2つ' : '子1つ';
    const h = height(node);
    console.log(`値 ${String(node.value).padStart(2)} : 深さ ${depth} / 高さ ${h} / ${kind}`);
    walk(node.left, depth + 1);
    walk(node.right, depth + 1);
  }
  
  function height(node) {
    if (node === null) return -1;
    return 1 + Math.max(height(node.left), height(node.right));
  }
  
  walk(t.root);
  console.log('');
  console.log('木全体の高さ = 根の高さ =', height(t.root));
  EOF

bst.js はまだ無いので、これは③で作ってから動かします。 先に結果を出しておきます。

値 50 : 深さ 0 / 高さ 3 / 子2つ
値 30 : 深さ 1 / 高さ 2 / 子2つ
値 20 : 深さ 2 / 高さ 0 / 葉
値 40 : 深さ 2 / 高さ 1 / 子1つ
値 35 : 深さ 3 / 高さ 0 / 葉
値 70 : 深さ 1 / 高さ 1 / 子2つ
値 60 : 深さ 2 / 高さ 0 / 葉
値 80 : 深さ 2 / 高さ 0 / 葉

木全体の高さ = 根の高さ = 3

読み方はこれだけです。

数え方この木での例
深さ根から下へ数える。根は 035 の深さは 3
高さその節点から、いちばん遠い葉まで。葉は 040 の高さは 1、70 の高さは 1
木の高さ根の高さ。葉が無い(空の)木は -1 とするこの木は 3

深さと高さを混ぜると、あとで測定結果が読めなくなります。 上から数えるのが深さ、下から数えるのが高さです。

height(null) を -1 にしているのは都合ではありません。 そう決めると「葉の高さ = 1 + max(-1, -1) = 0」がそのまま成り立ち、場合分けが1つ消えます。

二分木の種類

名前がいくつもありますが、区別が必要になる場面はそれほど多くありません。 一度だけ図で並べます。

【完全二分木に近い形】               【全二分木(子は0か2)】
        50                                  50
       /  \                                /  \
     30    70                            30    70
    /  \   / \                          /  \
  20   40 60  80                      20   40
  ぜんぶ埋まっている                    子1つの節点が無い

【この記事で作る木】                 【一直線(⑥で作る)】
        50                            1
       /  \                            \
     30    70                           2
    /  \   / \                           \
  20   40 60  80                          3
       /                                   \
     35                                     4
  40 の子が1つだけ                      左が全部 null
呼び方条件高さ
完全二分木(complete)上の段から左詰めで埋まっているほぼ log2(n)
全二分木(full)どの節点も子が 0 個か 2 個。1個は無い決まらない
バランスが取れているどの節点でも左右の部分木の高さの差が小さいO(log n)
一直線(縮退)どの節点も子が1つ以下で、片側に伸びているn – 1

覚える必要があるのは、いちばん下の2行だけです。 「バランスが取れているか」と「一直線になっていないか」。残りは、この2つを説明するための言葉です。

そして⑥で分かりますが、普通に書いた二分探索木は、放っておくと一直線に近づきます。


③ 二分探索木を書く

節点と insert

bst.js を作ります。

bash
$ cat > bst.js <<'EOF'
  export class Node {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }
  
  export class BST {
    constructor() {
      this.root = null;
      this.size = 0;
    }
  
    insert(value) {
      const node = new Node(value);
      if (this.root === null) {
        this.root = node;
        this.size++;
        return this;
      }
      let cur = this.root;
      while (true) {
        if (value === cur.value) return this;          // 重複は入れない
        if (value < cur.value) {
          if (cur.left === null) { cur.left = node; this.size++; return this; }
          cur = cur.left;
        } else {
          if (cur.right === null) { cur.right = node; this.size++; return this; }
          cur = cur.right;
        }
      }
    }
  
    // 見つかったか+通った道を返す
    searchPath(value) {
      const path = [];
      let cur = this.root;
      while (cur !== null) {
        path.push(cur.value);
        if (value === cur.value) return { found: true, path };
        cur = value < cur.value ? cur.left : cur.right;
      }
      return { found: false, path };
    }
  
    search(value) {
      return this.searchPath(value).found;
    }
  
    min(node = this.root) {
      if (node === null) return null;
      while (node.left !== null) node = node.left;
      return node.value;
    }
  
    max(node = this.root) {
      if (node === null) return null;
      while (node.right !== null) node = node.right;
      return node.value;
    }
  
    height(node = this.root) {
      if (node === null) return -1;
      return 1 + Math.max(this.height(node.left), this.height(node.right));
    }
  }
  EOF

規則は1つだけです。

入れる値が、いまいる節点より小さければ左へ、大きければ右へ。空いていたらそこに置く。

min と max を見てください。

min(node = this.root) {
  while (node.left !== null) node = node.left;   // 左に行き続ける
  return node.value;
}

これで最小値です。 全件を見ていません。比較もしていません。「左は小さい」という規則が守られているなら、いちばん左が最小だからです。

規則を1つ守るだけで、最小値の取得がタダになりました。 ここがデータ構造の見返りです。

動かす

bash
$ cat > use-bst.js <<'EOF'
  import { BST } from './bst.js';
  
  const t = new BST();
  for (const v of [50, 30, 70, 20, 40, 60, 80, 35]) t.insert(v);
  
  console.log('件数:', t.size);
  console.log('最小:', t.min(), '/ 最大:', t.max());
  console.log('高さ:', t.height());
  
  for (const v of [35, 60, 55]) {
    const r = t.searchPath(v);
    console.log(`${v} を探す → ${r.found ? '見つかった' : '無い'} : ${r.path.join(' → ')} (${r.path.length}回比較)`);
  }
  EOF
$ node use-bst.js
件数: 8
最小: 20 / 最大: 80
高さ: 3
35 を探す → 見つかった : 50 → 30 → 40 → 35 (4回比較)
60 を探す → 見つかった : 50 → 70 → 60 (3回比較)
55 を探す → 無い : 50 → 70 → 60 (3回比較)

②で書いた depth.js も、これで動きます。

bash
$ node depth.js

55 を探したときを見てください。 木の中に 55 はありません。それでも3回で「無い」と分かっています。

配列で includes を使ったら、無いことを確かめるには全件見るしかありません(本線の計算量の回でやった O(n) です)。木は、無いことも log n 回で分かります。

木を文字で描く

これから削除をやります。消したあとの形を毎回確認したいので、描くコードを先に作ります。

bash
$ cat > draw.js <<'EOF'
  // 木を横倒しにして文字で描く。右の部分木が上、左が下に出る
  export function draw(node, prefix = '', pos = 'root') {
    if (node === null) return;
    draw(node.right, prefix + '    ', 'R');
    const mark = pos === 'R' ? '/-- ' : pos === 'L' ? '\\-- ' : '';
    console.log(prefix + mark + node.value);
    draw(node.left, prefix + '    ', 'L');
  }
  EOF
$ cat > use-draw.js <<'EOF'
  import { BST } from './bst.js';
  import { draw } from './draw.js';
  
  const t = new BST();
  for (const v of [50, 30, 70, 20, 40, 60, 80, 35]) t.insert(v);
  draw(t.root);
  EOF
$ node use-draw.js
        /-- 80
    /-- 70
        \-- 60
50
        /-- 40
            \-- 35
    \-- 30
        \-- 20

横倒しです。 右の部分木が上、左が下に出ます。首を左に90度傾けると、②で書いた図になります。

draw の中身は「右を描く・自分を出す・左を描く」の3行です。 これは④でやる巡回の1つ(順番を逆にした in-order)そのものです。描画のために書いたコードが、すでに巡回でした。

探索が「半分ずつ捨てる」ところを見る

「O(log n)」は式で見ても何も分かりません。捨てている候補の数を表示します。

bash
$ cat > halving.js <<'EOF'
  import { BST } from './bst.js';
  
  // 1〜1023 をバランスよく入れる(真ん中から入れれば偏らない)
  function buildBalanced(t, lo, hi) {
    if (lo > hi) return;
    const mid = Math.floor((lo + hi) / 2);
    t.insert(mid);
    buildBalanced(t, lo, mid - 1);
    buildBalanced(t, mid + 1, hi);
  }
  
  const t = new BST();
  buildBalanced(t, 1, 1023);
  console.log('件数:', t.size, '/ 高さ:', t.height());
  
  // 探すたびに「残っている候補の数」を数える
  function searchCounting(t, value) {
    let cur = t.root;
    let lo = 1, hi = 1023, step = 0;
    while (cur !== null) {
      step++;
      console.log(`  ${step}回目: ${cur.value} と比べる → 残る候補は ${hi - lo + 1} 件のうち`);
      if (value === cur.value) { console.log(`  → 見つかった(${step}回)`); return; }
      if (value < cur.value) { hi = cur.value - 1; cur = cur.left; }
      else { lo = cur.value + 1; cur = cur.right; }
    }
  }
  console.log('777 を探す:');
  searchCounting(t, 777);
  console.log('総当たりなら最悪 1023 回、この木では上の回数');
  EOF
$ node halving.js
件数: 1023 / 高さ: 9
777 を探す:
  1回目: 512 と比べる → 残る候補は 1023 件のうち
  2回目: 768 と比べる → 残る候補は 511 件のうち
  3回目: 896 と比べる → 残る候補は 255 件のうち
  4回目: 832 と比べる → 残る候補は 127 件のうち
  5回目: 800 と比べる → 残る候補は 63 件のうち
  6回目: 784 と比べる → 残る候補は 31 件のうち
  7回目: 776 と比べる → 残る候補は 15 件のうち
  8回目: 780 と比べる → 残る候補は 7 件のうち
  9回目: 778 と比べる → 残る候補は 3 件のうち
  10回目: 777 と比べる → 残る候補は 1 件のうち
  → 見つかった(10回)
総当たりなら最悪 1023 回、この木では上の回数

1023 → 511 → 255 → 127 → 63 → 31 → 15 → 7 → 3 → 1。

毎回、候補がぴったり半分になっています。 1023 件を 10 回で当てました。

なぜ半分になるのか。 512 と比べて「777 は大きい」と分かった瞬間、512 以下の 512 件は、1件も見ずに捨てられます。 「左は全部小さい」という規則を守っているからです。

これが「O(log n)」の中身です。 2 で割り続けて 1 になるまでの回数が log2(n)。1023 なら 10 回。式を覚える話ではなく、半分捨てられるかどうかの話でした。

スクリーンショットを撮ってください: 02_halving_search.png node halving.js の出力全体。1023 → 511 → 255 と半分になっていく列が、この記事でいちばん見てほしい出力です。

削除 — ここだけが本当に難しい

insert と search は、規則をそのまま書けば動きます。削除だけは違います。

理由は単純です。節点を消すと、その節点にぶら下がっていた部分木の行き先がなくなるからです。

場合を分けます。3つあります。

【1. 子が無い】          【2. 子が1つ】         【3. 子が2つ】
     30                      40                     30
    /  \                    /                      /  \
  20    40                35                     20    40
  ↑ 20 を消す              ↑ 40 を消す             ↑ 30 を消す
  そのまま外す             35 を持ち上げる         20 も 40 も残さないと
                                                  いけない → 困る

delete.js を作ります。削除だけ別ファイルにします。 長いからではなく、ここだけ読み返すことになるからです。

bash
$ cat > delete.js <<'EOF'
  // 削除だけを別ファイルにした。3パターンをそのまま書き分ける
  export function removeValue(node, value) {
    if (node === null) return null;
  
    if (value < node.value) {
      node.left = removeValue(node.left, value);
      return node;
    }
    if (value > node.value) {
      node.right = removeValue(node.right, value);
      return node;
    }
  
    // ここに来たら node が消す対象
  
    // パターン1: 子が無い → そのまま消す
    if (node.left === null && node.right === null) {
      return null;
    }
  
    // パターン2: 子が1つ → その子を自分の場所に上げる
    if (node.left === null) return node.right;
    if (node.right === null) return node.left;
  
    // パターン3: 子が2つ → 右の部分木の最小値を持ってきて、それを消す
    let successor = node.right;
    while (successor.left !== null) successor = successor.left;
    node.value = successor.value;
    node.right = removeValue(node.right, successor.value);
    return node;
  }
  EOF

書き方のコツが1つあります。

removeValue は「消す」関数ではなく、「消したあとの部分木の根を返す」関数として書きます。 そして呼び出し側は、返ってきたものを繋ぎ直します。

node.left = removeValue(node.left, value);   // 繋ぎ直す

これをやらずに「親の left を null にする」と書こうとすると、親を持ち歩かないといけなくなり、コードが2倍になります。 返り値で繋ぐと、親の情報が要りません。

パターン3が唯一のややこしいところです。

30(子が2つ)を消したい。30 の場所には、「20 より大きく、40 より小さい値」が来ないと規則が壊れます。そんな値は2つあります。

  • 左の部分木の最大値(20 より大きい中でいちばん大きい)
  • 右の部分木の最小値(40 より小さい中でいちばん小さい)

どちらでもいいので、右の部分木の最小値を使いました。

そして大事なのは最後の1行です。

node.value = successor.value;                          // 値を持ってくる
node.right = removeValue(node.right, successor.value); // 持ってきた元を消す

値をコピーしただけでは、同じ値が2箇所にある状態になります。 だから持ってきた元の節点を消し直します。 そしてその節点は、必ず左の子を持ちません(いちばん左だから)。つまり必ずパターン1か2になり、無限には潜りません。

4パターン全部、消したあとの形を見る

bash
$ cat > use-delete.js <<'EOF'
  import { BST } from './bst.js';
  import { draw } from './draw.js';
  import { removeValue } from './delete.js';
  
  function build() {
    const t = new BST();
    for (const v of [50, 30, 70, 20, 40, 60, 80, 35]) t.insert(v);
    return t;
  }
  
  function inorder(node, out = []) {
    if (node === null) return out;
    inorder(node.left, out);
    out.push(node.value);
    inorder(node.right, out);
    return out;
  }
  
  for (const [label, target] of [['子が無い(20)', 20], ['子が1つ(40)', 40], ['子が2つ(30)', 30], ['根(50)', 50]]) {
    const t = build();
    console.log('--- ' + label + ' を消す ---');
    t.root = removeValue(t.root, target);
    draw(t.root);
    console.log('通りがけ:', inorder(t.root).join(' '));
    console.log('順番は崩れていないか:', JSON.stringify(inorder(t.root)) === JSON.stringify([...inorder(t.root)].sort((a, b) => a - b)));
    console.log('');
  }
  EOF
$ node use-delete.js
--- 子が無い(20) を消す ---
        /-- 80
    /-- 70
        \-- 60
50
        /-- 40
            \-- 35
    \-- 30
通りがけ: 30 35 40 50 60 70 80
順番は崩れていないか: true

--- 子が1つ(40) を消す ---
        /-- 80
    /-- 70
        \-- 60
50
        /-- 35
    \-- 30
        \-- 20
通りがけ: 20 30 35 50 60 70 80
順番は崩れていないか: true

--- 子が2つ(30) を消す ---
        /-- 80
    /-- 70
        \-- 60
50
        /-- 40
    \-- 35
        \-- 20
通りがけ: 20 35 40 50 60 70 80
順番は崩れていないか: true

--- 根(50) を消す ---
        /-- 80
    /-- 70
60
        /-- 40
            \-- 35
    \-- 30
        \-- 20
通りがけ: 20 30 35 40 60 70 80
順番は崩れていないか: true

4つ全部、順番が崩れていません。

「根を消す」を4つ目に入れたのは、根だけ特別扱いが必要かを確かめたかったからです。 必要ありませんでした。t.root = removeValue(t.root, ...) と返り値で受け直しているので、根も普通の節点と同じです。

そして 35 が 30 の位置に上がった形(3つ目)を見てください。 30 を消したあと、35 が根の左に来て、20 と 40 を子にしています。規則は守られていますが、形は変わりました。 削除を繰り返すと、木は少しずつ形が崩れます。 ⑥に繋がります。


④ 3つの巡回 — 暗記しない

「in-order / pre-order / post-order」。私はこれを語呂で覚えようとして失敗しました。

覚えるものではありません。 3行の順番の話です。

bash
$ cat > traverse.js <<'EOF'
  // 3つとも「左を見る・自分を処理する・右を見る」の3行を並べ替えただけ
  
  export function preOrder(node, visit) {   // 行きがけ
    if (node === null) return;
    visit(node.value);
    preOrder(node.left, visit);
    preOrder(node.right, visit);
  }
  
  export function inOrder(node, visit) {    // 通りがけ
    if (node === null) return;
    inOrder(node.left, visit);
    visit(node.value);
    inOrder(node.right, visit);
  }
  
  export function postOrder(node, visit) {  // 帰りがけ
    if (node === null) return;
    postOrder(node.left, visit);
    postOrder(node.right, visit);
    visit(node.value);
  }
  EOF

3つの関数を並べて見てください。 違いはvisit(node.value) が何行目にあるか、だけです。

名前日本語visit の位置覚え方
pre-order行きがけ左右を見る前降りる途中で処理する
in-order通りがけ左のあと、右の前左を全部片づけてから処理する
post-order帰りがけ左右を見た後子を全部片づけてから処理する

「pre / in / post」は、visit が「子より前か・間か・後か」を言っているだけです。 それ以上の意味はありません。

同じ木を3通りで出す

bash
$ cat > use-traverse.js <<'EOF'
  import { BST } from './bst.js';
  import { preOrder, inOrder, postOrder } from './traverse.js';
  
  const t = new BST();
  for (const v of [50, 30, 70, 20, 40, 60, 80, 35]) t.insert(v);
  
  const collect = (fn) => { const out = []; fn(t.root, (v) => out.push(v)); return out; };
  
  console.log('行きがけ pre  :', collect(preOrder).join(' '));
  console.log('通りがけ in   :', collect(inOrder).join(' '));
  console.log('帰りがけ post :', collect(postOrder).join(' '));
  
  const inOrderResult = collect(inOrder);
  const sorted = [...inOrderResult].sort((a, b) => a - b);
  console.log('通りがけはソート済みか:', JSON.stringify(inOrderResult) === JSON.stringify(sorted));
  EOF
$ node use-traverse.js
行きがけ pre  : 50 30 20 40 35 70 60 80
通りがけ in   : 20 30 35 40 50 60 70 80
帰りがけ post : 20 35 40 30 60 80 70 50
通りがけはソート済みか: true

3行だけ見比べてください。

  • pre は 50 から始まっています → 根が最初
  • post は 50 で終わっています → 根が最後
  • in は 20 30 35 40 50 60 70 80 → 完全にソート済み

in-order でソート済みで出てくるのは、偶然ではありません。

「左を全部出す → 自分を出す → 右を全部出す」を、どの節点でもやっている。そして「左は全部自分より小さい・右は全部大きい」。この2つが同時に成り立てば、出てくる順番が小さい順になるのは避けられません。

二分探索木に入れて in-order で取り出せば、ソートになります。 名前が付いています(木ソート)。速いかどうかは、⑥の結果で分かります。

スクリーンショットを撮ってください: 03_three_traversals.png node use-traverse.js の出力3行。同じ木・同じデータで、visit の位置を変えただけで並びが変わっていることが見える画面。

使い分け — これは覚える価値がある

3つの順番を覚える必要はありませんが、「どれを使うか」は覚える価値があります。

やりたいこと使う巡回理由
整列して取り出すin-order小さい順に出てくる
範囲で取り出す(30〜60 だけ)in-order順に出るので、範囲外に入ったら止められる
木をコピーする / シリアライズするpre-order根が先に出るので、受け取った側が同じ順に insert すれば同じ形になる
式や JSON を出力するpre-order外側の構造から先に書き出せる
ディレクトリの合計サイズpost-order子の合計が出ないと自分の合計が出せない
木を消す / 解放するpost-order自分を先に消すと、子への参照が失われる
段ごとに見る / 最短の段を探す幅優先⑤でやります

post-order の2つは、「順番を選べる」のではなく「それしか成り立たない」例です。 覚えるならこの2つです。

post-order の実物 — ディレクトリの合計サイズ

①で作った sample/ の合計サイズを出します。帰りがけです。

bash
$ cat > dirsize.js <<'EOF'
  import { readdirSync, statSync } from 'node:fs';
  import { join } from 'node:path';
  
  // ディレクトリは木。合計サイズは「子を全部足してから自分」=帰りがけ
  function dirSize(path, name, depth = 0) {
    const pad = '  '.repeat(depth);
    const st = statSync(path);
  
    if (!st.isDirectory()) {
      console.log(`${pad}${name} : ${st.size} バイト`);
      return st.size;
    }
  
    let total = 0;
    for (const child of readdirSync(path)) {
      total += dirSize(join(path, child), child, depth + 1);  // 子を先に片づける
    }
    console.log(`${pad}${name}/ の合計 : ${total} バイト`);   // 自分は最後
    return total;
  }
  
  dirSize('sample', 'sample');
  EOF
$ node dirsize.js
        a.md : 16 バイト
        b.md : 13 バイト
      09/ の合計 : 29 バイト
        c.md : 8 バイト
      10/ の合計 : 8 バイト
    2026/ の合計 : 37 バイト
  docs/ の合計 : 37 バイト
  README.md : 6 バイト
      run.sh : 19 バイト
    bin/ の合計 : 19 バイト
    index.js : 15 バイト
      util.js : 19 バイト
    lib/ の合計 : 19 バイト
  src/ の合計 : 53 バイト
sample/ の合計 : 96 バイト

出力の順番を見てください。 深いところから出て、sample/ の合計が最後に出ています。

当たり前です。 sample/ の合計は、中身を全部足し終わるまで出せません。 だから帰りがけ以外に選択肢がありません。

これが du コマンドがやっていることです。 木を帰りがけにたどっているだけです。

pre-order の実物 — 木をコピーする

「pre-order で木をコピーできる」を確かめます。pre-order で出した並びで insert し直すと、同じ形になるはずです。

bash
$ cat > clone.js <<'EOF'
  import { BST } from './bst.js';
  import { preOrder, inOrder } from './traverse.js';
  import { draw } from './draw.js';
  
  const t = new BST();
  for (const v of [50, 30, 70, 20, 40, 60, 80, 35]) t.insert(v);
  
  // 行きがけの順に insert し直すと、まったく同じ形の木ができる
  const preList = [];
  preOrder(t.root, (v) => preList.push(v));
  const copyFromPre = new BST();
  for (const v of preList) copyFromPre.insert(v);
  
  // 通りがけの順に insert し直すと……
  const inList = [];
  inOrder(t.root, (v) => inList.push(v));
  const copyFromIn = new BST();
  for (const v of inList) copyFromIn.insert(v);
  
  console.log('行きがけの順で作り直した木(高さ ' + copyFromPre.height() + ')');
  draw(copyFromPre.root);
  console.log('');
  console.log('通りがけの順で作り直した木(高さ ' + copyFromIn.height() + ')');
  draw(copyFromIn.root);
  EOF
$ node clone.js
行きがけの順で作り直した木(高さ 3)
        /-- 80
    /-- 70
        \-- 60
50
        /-- 40
            \-- 35
    \-- 30
        \-- 20

通りがけの順で作り直した木(高さ 7)
                            /-- 80
                        /-- 70
                    /-- 60
                /-- 50
            /-- 40
        /-- 35
    /-- 30
20

pre-order の順で入れ直した木は、高さ 3。元と完全に同じ形です。

in-order の順で入れ直した木は、高さ 7。 一直線に潰れました。

これは、pre-order のほうが偉いという話ではありません。

  • pre-order は根が先に出る → 入れ直すと同じ根から始まる → 同じ形になる
  • in-order はソート済みで出る → ソート済みを順に入れると、必ず一直線になる

同じ8件です。同じコードです。 入れる順番だけで、高さが 3 と 7 になりました。

⑥でやることが、ここで先に顔を出しました。


⑤ 幅優先(レベル順)— これだけキューを使う

3つの巡回は、全部深さ優先です。行けるところまで潜ってから戻ります。

段ごとに見たいときは、別の道具が要ります。

深さ優先は再帰(=スタック)で書けますが、幅優先はキューでしか書けません。 前回の記事で書いたキューを、そのまま持ってきます。

bash
$ cat > bfs.js <<'EOF'
  import { BST } from './bst.js';
  
  // 前回のキューをそのまま持ってきた(先頭の位置を数字で持つ形)
  class Queue {
    #items = [];
    #head = 0;
    enqueue(v) { this.#items.push(v); return this; }
    dequeue() {
      if (this.#head >= this.#items.length) return undefined;
      const v = this.#items[this.#head];
      this.#items[this.#head] = undefined;   // 参照を残さない
      this.#head++;
      if (this.#head * 2 >= this.#items.length) {
        this.#items = this.#items.slice(this.#head);
        this.#head = 0;
      }
      return v;
    }
    get length() { return this.#items.length - this.#head; }
    get isEmpty() { return this.length === 0; }
  }
  
  export function levelOrder(root) {
    const out = [];
    if (root === null) return out;
    const q = new Queue();
    q.enqueue(root);
    while (!q.isEmpty) {
      const node = q.dequeue();
      out.push(node.value);
      if (node.left) q.enqueue(node.left);
      if (node.right) q.enqueue(node.right);
    }
    return out;
  }
  
  // 段ごとに区切って出す版。行列に何人並んでいるかを先に数えるだけ
  export function byLevel(root) {
    const levels = [];
    if (root === null) return levels;
    const q = new Queue();
    q.enqueue(root);
    while (!q.isEmpty) {
      const n = q.length;              // いまの段の人数
      const row = [];
      for (let i = 0; i < n; i++) {
        const node = q.dequeue();
        row.push(node.value);
        if (node.left) q.enqueue(node.left);
        if (node.right) q.enqueue(node.right);
      }
      levels.push(row);
    }
    return levels;
  }
  
  const t = new BST();
  for (const v of [50, 30, 70, 20, 40, 60, 80, 35]) t.insert(v);
  
  console.log('幅優先(レベル順):', levelOrder(t.root).join(' '));
  byLevel(t.root).forEach((row, i) => console.log(`深さ ${i}: ${row.join(' ')}`));
  EOF
$ node bfs.js
幅優先(レベル順): 50 30 70 20 40 60 80 35
深さ 0: 50
深さ 1: 30 70
深さ 2: 20 40 60 80
深さ 3: 35

②で描いた図の、上から1段ずつです。

levelOrder は再帰していません。 キューが空になるまでのループです。再帰を1つも書かずに木を全部たどれます。

byLevel の1行だけ足された工夫を見てください。

const n = q.length;   // いまの段の人数を、先に数える

ループの中で q.enqueue するので、q.length は増えていきます。 だから段の区切りを付けたいなら、その段に入る前に人数を確定させる必要があります。これを忘れると、段がぐちゃぐちゃになります。

使う道具出てくる順得意なこと
深さ優先(pre / in / post)スタック(再帰)枝ごと部分木単位の集計、整列
幅優先(レベル順)キュー段ごと最も浅い場所を探す、段ごとの表示

「最短を探す」なら幅優先です。 段の浅い順に出てくるので、最初に見つかったものが最も浅いと確定します。深さ優先では確定しません。


⑥ 木にしたのに一直線になる

ここが、この記事を書いた理由です。

まず8件で見る

bash
$ cat > straight.js <<'EOF'
  import { BST } from './bst.js';
  import { draw } from './draw.js';
  
  const t = new BST();
  for (const v of [1, 2, 3, 4, 5, 6, 7, 8]) t.insert(v);   // すでに並んでいる
  
  console.log('1〜8 を順に insert した木:');
  draw(t.root);
  
  // 左の子を持っている節点が1つでもあるか数える
  let hasLeft = 0, total = 0;
  let cur = t.root;
  while (cur !== null) {
    total++;
    if (cur.left !== null) hasLeft++;
    cur = cur.right;
  }
  console.log('');
  console.log(`右にたどれた節点 : ${total} 件 / 全 ${t.size} 件`);
  console.log(`左の子を持つ節点 : ${hasLeft} 件`);
  console.log('→ 左が全部 null なら、これは木ではなく連結リストです');
  EOF
$ node straight.js
1〜8 を順に insert した木:
                            /-- 8
                        /-- 7
                    /-- 6
                /-- 5
            /-- 4
        /-- 3
    /-- 2
1

右にたどれた節点 : 8 件 / 全 8 件
左の子を持つ節点 : 0 件

左の子を持つ節点が 0 件。 根から右だけをたどって、8件全部に到達しました。

これは木ではありません。連結リストです。 left という使われないプロパティが1つ付いた、前回の前の記事で書いた連結リストと同じものです。

理由は考えるまでもありません。

  • 1 を入れる → 根
  • 2 を入れる → 1 より大きい → 右
  • 3 を入れる → 1 より大きい → 右 → 2 より大きい → 右
  • 4 を入れる → 右 → 右 → 右

「左は小さい・右は大きい」を1つも破っていません。 規則を完璧に守った結果、一直線になりました。

件数を増やして実測する

8件では時間が測れません。 10000 / 20000 / 40000 で測ります。

注意が1つあります。 一直線の木の高さを、②で書いた再帰の height() で測ると落ちます(高さ 39999 なので、再帰が 40000 段になります)。自分でスタックを持つループ版で測ります。

bash
$ cat > bench-shape.js <<'EOF'
  import { BST } from './bst.js';
  import { performance } from 'node:perf_hooks';
  
  // 高さを、再帰ではなく自分のスタックで測る(一直線の木は再帰だと落ちる)
  function heightIterative(root) {
    if (root === null) return -1;
    let max = 0;
    const stack = [[root, 0]];
    while (stack.length > 0) {
      const [node, d] = stack.pop();
      if (d > max) max = d;
      if (node.left) stack.push([node.left, d + 1]);
      if (node.right) stack.push([node.right, d + 1]);
    }
    return max;
  }
  
  function shuffle(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
  }
  
  const N = Number(process.argv[2] ?? 20000);
  
  for (const [label, values] of [
    ['並んでいる順 (1,2,3,...)', Array.from({ length: N }, (_, i) => i + 1)],
    ['ばらばらの順', shuffle(Array.from({ length: N }, (_, i) => i + 1))],
  ]) {
    const t = new BST();
  
    const t0 = performance.now();
    for (const v of values) t.insert(v);
    const insertMs = performance.now() - t0;
  
    const h = heightIterative(t.root);
  
    // 全件を1回ずつ探して、比較回数の合計を数える
    let compares = 0;
    const t1 = performance.now();
    for (let v = 1; v <= N; v++) {
      let cur = t.root;
      while (cur !== null) {
        compares++;
        if (v === cur.value) break;
        cur = v < cur.value ? cur.left : cur.right;
      }
    }
    const searchMs = performance.now() - t1;
  
    console.log(`--- ${label} (${N}件) ---`);
    console.log(`  木の高さ        : ${h}`);
    console.log(`  理想の高さ      : ${Math.floor(Math.log2(N))}`);
    console.log(`  insert 合計     : ${insertMs.toFixed(1)} ms`);
    console.log(`  全件探索        : ${searchMs.toFixed(1)} ms`);
    console.log(`  比較回数の合計  : ${compares}`);
    console.log(`  1件あたり比較   : ${(compares / N).toFixed(1)} 回`);
  }
  EOF
$ node bench-shape.js 10000
--- 並んでいる順 (1,2,3,...) (10000件) ---
  木の高さ        : 9999
  理想の高さ      : 13
  insert 合計     : 132.2 ms
  全件探索        : 150.2 ms
  比較回数の合計  : 50005000
  1件あたり比較   : 5000.5 回
--- ばらばらの順 (10000件) ---
  木の高さ        : 31
  理想の高さ      : 13
  insert 合計     : 4.1 ms
  全件探索        : 5.6 ms
  比較回数の合計  : 174152
  1件あたり比較   : 17.4 回
bash
$ node bench-shape.js 20000
--- 並んでいる順 (1,2,3,...) (20000件) ---
  木の高さ        : 19999
  理想の高さ      : 14
  insert 合計     : 502.5 ms
  全件探索        : 558.2 ms
  比較回数の合計  : 200010000
  1件あたり比較   : 10000.5 回
--- ばらばらの順 (20000件) ---
  木の高さ        : 36
  理想の高さ      : 14
  insert 合計     : 8.1 ms
  全件探索        : 16.7 ms
  比較回数の合計  : 352675
  1件あたり比較   : 17.6 回
bash
$ node bench-shape.js 40000
--- 並んでいる順 (1,2,3,...) (40000件) ---
  木の高さ        : 39999
  理想の高さ      : 15
  insert 合計     : 1433.8 ms
  全件探索        : 1239.4 ms
  比較回数の合計  : 800020000
  1件あたり比較   : 20000.5 回
--- ばらばらの順 (40000件) ---
  木の高さ        : 37
  理想の高さ      : 15
  insert 合計     : 13.0 ms
  全件探索        : 23.1 ms
  比較回数の合計  : 757565
  1件あたり比較   : 18.9 回

表にします。

件数入れる順木の高さ理想の高さinsert 合計全件探索1件あたり比較
10000並んでいる999913132.2 ms150.2 ms5000.5 回
10000ばらばら31134.1 ms5.6 ms17.4 回
20000並んでいる1999914502.5 ms558.2 ms10000.5 回
20000ばらばら36148.1 ms16.7 ms17.6 回
40000並んでいる39999151433.8 ms1239.4 ms20000.5 回
40000ばらばら371513.0 ms23.1 ms18.9 回

縦に読んでください。

並んでいる順(一直線):

  • 高さは 9999 → 19999 → 39999。件数と同じだけ増えます。n – 1 です
  • 1件あたり比較は 5000 → 10000 → 20000。件数2倍で、比較も2倍。これは O(n) です
  • insert 合計は 132 → 502 → 1433 ms。件数2倍で時間が約4倍。これは O(n²) の顔(O記法の回でやりました)

ばらばらの順:

  • 高さは 31 → 36 → 37。件数を4倍にしても、高さは 6 しか増えていない
  • 1件あたり比較は 17.4 → 17.6 → 18.9。ほとんど増えていません。これが O(log n) です
  • insert 合計は 4.1 → 8.1 → 13.0 ms。件数に比例(1件あたりは一定)

40000件で、探索の速さが 53倍 違います(1239.4 ms 対 23.1 ms)。コードは1文字も違いません。入れた順番だけが違います。

「二分探索木の探索は O(log n)」は、条件付きの文でした。 正確には「バランスが取れている二分探索木では O(log n)、最悪は O(n)」です。 そして最悪ケースは珍しいケースではありません。 「並んでいるデータを順に入れる」は、現実にいちばん起きやすい入れ方です。DB から ORDER BY id で取ってきて、順に入れたら終わりです。

「ばらばらの順」も、答えではない

「じゃあシャッフルして入れればいい」と思いました。それも違います。

  • 後から追加されるデータの順番は、こちらでは決められません。 時刻順に増えるログを入れたら、また一直線です
  • ③で見たとおり、削除でも形は崩れます
  • 高さ 31〜37 は、理想の 13〜15 の2倍以上あります。 ばらばらでも理想にはなりません

必要なのは「運がいい入れ方」ではなく、「どう入れても形が崩れない仕掛け」です。

仕掛けは存在します。 入れるたびに木の形を測って、偏っていたら節点を回して直すという手を打ちます。これを持っている木をバランス木と呼びます(AVL木、赤黒木、B木など)。

この記事では扱いません。 ただ、これで「バランス木」という言葉が、覚える用語ではなくなりました。

いま実測した「高さ 39999」を、どう入れても 15 前後に保つための仕掛けです。次の回で、同じ bench-shape.js を使って、同じ表を出して比べます。


⑦ 再帰と、コールスタックの深さ

木の処理は再帰が自然です。④で書いた巡回は、3つとも3行でした。

一直線の木では、この3行が落ちます。

bash
$ cat > overflow.js <<'EOF'
  import { BST } from './bst.js';
  import { inOrder } from './traverse.js';
  
  const N = Number(process.argv[2] ?? 50000);
  
  const t = new BST();
  for (let v = 1; v <= N; v++) t.insert(v);   // わざと一直線にする
  
  console.log(`${N}件を並んだ順に insert しました`);
  
  let count = 0;
  try {
    inOrder(t.root, () => count++);
    console.log(`再帰版の通りがけ: 成功。${count} 件`);
  } catch (e) {
    console.log(`再帰版の通りがけ: ${e.constructor.name}: ${e.message}`);
    console.log(`  ${count} 件目まで進んで落ちました`);
  }
  EOF
$ node overflow.js 5000
5000件を並んだ順に insert しました
再帰版の通りがけ: 成功。5000 件

5000件は通ります。 増やします。

bash
$ node overflow.js 20000
20000件を並んだ順に insert しました
再帰版の通りがけ: RangeError: Maximum call stack size exceeded
  9637 件目まで進んで落ちました

Maximum call stack size exceeded。 ①の「輪を作ったとき」と同じエラーです。でも今度は、コードは正しく、輪もありません。

木が深すぎるだけです。

inOrder は、左に降りるたびに1段積みます。一直線の木では、高さがそのまま再帰の段数になります。私の環境では 9637段 で溢れました。

bash
$ node overflow.js 50000
50000件を並んだ順に insert しました
再帰版の通りがけ: RangeError: Maximum call stack size exceeded
  9637 件目まで進んで落ちました

50000件でも「9637件目」で落ちています。 件数を増やしても、溢れる段数は変わりません。 上限はデータ量ではなくスタックの容量で決まっているからです(前回で --stack-size を触ったのと同じ話です)。

バランスが取れていれば、この問題は起きません。 40000件でも高さは 37 でした。37段の再帰は何の問題もありません。 深さが問題になるのは、一直線に潰れたときだけです。⑥の話と⑦の話は、同じ1つの問題でした。

明示的なスタックで書き換える

再帰をやめます。 「積む場所を、コールスタックから自分の配列に移す」だけです。

bash
$ cat > iterative.js <<'EOF'
  // 再帰をやめて、自分の配列をスタックとして使う通りがけ
  export function inOrderLoop(root, visit) {
    const stack = [];
    let cur = root;
    while (cur !== null || stack.length > 0) {
      while (cur !== null) {       // 行けるところまで左に降りる
        stack.push(cur);
        cur = cur.left;
      }
      const node = stack.pop();    // 降りきったら1段戻って自分を処理
      visit(node.value);
      cur = node.right;            // そして右へ
    }
  }
  
  // 行きがけのループ版。こちらはもっと単純
  export function preOrderLoop(root, visit) {
    if (root === null) return;
    const stack = [root];
    while (stack.length > 0) {
      const node = stack.pop();
      visit(node.value);
      if (node.right) stack.push(node.right);   // 右を先に積むと、左が先に出る
      if (node.left) stack.push(node.left);
    }
  }
  EOF

inOrderLoop の3つの部分が、再帰版の3行と1対1で対応しています。

再帰版ループ版
inOrder(node.left, visit)while (cur !== null) { stack.push(cur); cur = cur.left; }
visit(node.value)const node = stack.pop(); visit(node.value);
inOrder(node.right, visit)cur = node.right;

preOrderLoop の push の順番に注意してください。 右を先に積みます。 スタックは後から入れたものが先に出るので、左を後に積むと左が先に出ます。逆にすると 50 70 80 60 30 40 35 20 になります。

bash
$ cat > use-iterative.js <<'EOF'
  import { BST } from './bst.js';
  import { inOrder, preOrder } from './traverse.js';
  import { inOrderLoop, preOrderLoop } from './iterative.js';
  
  // まず小さい木で、再帰版と同じ結果か確かめる
  const small = new BST();
  for (const v of [50, 30, 70, 20, 40, 60, 80, 35]) small.insert(v);
  const a = [], b = [], c = [], d = [];
  inOrder(small.root, (v) => a.push(v));
  inOrderLoop(small.root, (v) => b.push(v));
  preOrder(small.root, (v) => c.push(v));
  preOrderLoop(small.root, (v) => d.push(v));
  console.log('in  再帰 :', a.join(' '));
  console.log('in  ループ:', b.join(' '));
  console.log('pre 再帰 :', c.join(' '));
  console.log('pre ループ:', d.join(' '));
  console.log('一致:', a.join() === b.join(), c.join() === d.join());
  
  // 次に、再帰版が落ちた大きさで試す
  const N = Number(process.argv[2] ?? 500000);
  const big = new BST();
  for (let v = 1; v <= N; v++) big.insert(v);
  
  let count = 0, last = null;
  inOrderLoop(big.root, (v) => { count++; last = v; });
  console.log(`\n一直線の ${N} 件: ループ版は ${count} 件、最後の値 ${last}`);
  EOF
$ node use-iterative.js 50000
in  再帰 : 20 30 35 40 50 60 70 80
in  ループ: 20 30 35 40 50 60 70 80
pre 再帰 : 50 30 20 40 35 70 60 80
pre ループ: 50 30 20 40 35 70 60 80
一致: true true

一直線の 50000 件: ループ版は 50000 件、最後の値 50000

小さい木では結果が完全に一致し、50000件の一直線でも落ちませんでした。

200000件でも通りました(ただし insert に 86 秒かかりました。⑥の O(n²) です)。

ループ版はメモリを節約していません。 一直線の木では、stack に 50000 件積まれます。積む場所をコールスタックから普通の配列に移しただけです。 なぜそれで直るのか。 コールスタックは容量が固定で数MBしかないのに、配列はヒープに置かれるので、はるかに大きくできるからです。同じ「積む」でも、置き場所の広さが違います。

どちらを書くべきか。

状況書き方
バランスが取れている木(高さが log n)再帰でよい。3行で読める
深さが分からないデータをたどる(ユーザー入力の JSON、ディレクトリ)ループ版か、深さの上限チェックを入れる
一直線になりうる木ループ版。または、そもそも一直線にしない(バランス木)

「再帰は危ないからループで書く」ではありません。 深さが log n に収まっていれば、再帰のほうが読めます。 判断するには高さを知る必要がある、というのがこの記事の結論です。


つまずいたところ

1. tree コマンドが無くて、最初の1行から止まった

①です。木の記事なので tree を打とうとして、Command 'tree' not found でした。

素の Ubuntu Server に tree は入っていません。 私の環境にも入っていませんでした。

sudo apt install tree で入りますが、この記事のために新しいパッケージを入れるのは筋が違うと考えて find にしました。find は最初から入っています。

教訓は、記事を書く側の話です。 「自分の環境に入っていたから読者の環境にもある」は、毎回間違います。

2. 木を描くコードで、バックスラッシュが消えた

draw.js です。左の子に \-- を付けたいのに、出力が -- になりました。

原因はJavaScript の文字列の中で \- が「ただの -」になることでした。\ は次の文字を打ち消す記号なので、\ 自体を出したいなら \\ と2つ書く必要があります。

const mark = pos === 'R' ? '/-- ' : pos === 'L' ? '\\-- ' : '';

エラーは1つも出ませんでした。 静かに文字が1つ消えるだけでした。「動いているのに出力が違う」はエラーより時間を取られます。

3. 一直線の木の高さを測ろうとして、測定コードが落ちた

⑥です。bench-shape.js を書いて動かしたら、測定する前に Maximum call stack size exceeded で落ちました。

bst.js の height() が再帰だったからです。 高さ 39999 の木を再帰で測ろうとして、40000段積もうとしていました。

測りたい対象が、測定器を壊しました。 heightIterative() を書いて解決しました。

これ自体が⑦の予告でした。 「一直線の木は再帰で扱えない」を、⑦を書く前に、測定コードで先に体験していました。 消さずに残しました。

4. 削除で、消したはずの値が2つになった

delete.js のパターン3です。最初、こう書いていました。

node.value = successor.value;   // 値を持ってきた
return node;                    // ← これで終わりにした

動きました。 そして通りがけの出力に、同じ値が2回出ました。

successor の節点が、木の中に残っていたからです。値をコピーしただけで、元を消していませんでした。

node.right = removeValue(node.right, successor.value);  // これが必要

「順番は崩れていないか」のチェックを毎回出していたので気づけました。 draw だけ見ていたら、深い場所の重複は見落としていました。確認の出力を1つ足しておくかどうかで、気づける不具合が変わります。

5. byLevel で、段の区切りがぐちゃぐちゃになった

⑤です。最初はこう書きました。

while (!q.isEmpty) {
  const row = [];
  for (let i = 0; i < q.length; i++) {   // ← これが間違い
    ...
  }
}

ループの中で enqueue するので、q.length が増え続けます。 条件式は毎回評価されるので、段の区切りが伸びていきました。

const n = q.length;              // 先に確定させる
for (let i = 0; i < n; i++) { ... }

1行を上に出すだけでした。 「ループの条件が、ループの中で変わる」は、キューを使うときに毎回踏みます。

6. 「ばらばらの順」の高さが、理想の2倍以上あって焦った

⑥です。40000件をシャッフルして入れたら、高さが 37 でした。log2(40000) は約 15 です。「実装がおかしいのでは」と3回測り直しました。

おかしくありません。 ばらばらに入れた二分探索木の高さの期待値は、理想の 2〜3 倍程度になることが知られています。

大事なのはそこではありませんでした。 39999 と 37 の差です。15 と 37 の差を気にしていて、39999 を見落としかけました。 桁が違うものと、2倍のものを、同じ目で見てはいけませんでした。

7. insert に 86 秒かかって、止まったと思った

⑦で use-iterative.js 200000 を動かしたときです。1分半、何も出ませんでした。 Ctrl+C を押しかけました。

止まっていませんでした。 一直線の木に 200000 件入れるのは、200000 の2乗の半分=約 200億歩です。86秒かかって、正しく終わりました。

記事では 50000 件(2.2秒)に下げました。 「⑥で測った O(n²) が、⑦の実験時間として自分に返ってきた」のが、いちばん納得した瞬間でした。

8. in-order でソートできると知って、ソートに使おうとした

④です。「木に入れて in-order で出せばソートになる」と分かって、sort() の代わりに使えるのではと考えました。

⑥の結果を見て、やめました。ソート済みに近いデータを入れると、木が一直線になって O(n²) になります。 そしてソートしたいデータは、部分的に並んでいることがよくあります。

「できる」と「使うべき」は別でした。 木ソートは、木が既にある場合に、並んだ結果もタダで取れるという話であって、ソートのために木を作る理由にはなりません。


後片づけ

この記事で作ったものを、全部消します。

まず、何があるか確認します。

bash
$ cd ~/cslab/tree
$ ls
bench-shape.js  clone.js   delete.js  dirsize.js  halving.js    iterative.js  overflow.js   sample      traverse.js  use-delete.js  use-iterative.js
bfs.js          cycle.js   depth.js   draw.js     json-tree.js  package.json  straight.js   use-bst.js  use-draw.js  use-traverse.js

node_modules はありません。 この記事では npm install を1回もしていないので、消すものは自分で書いたファイルと sample/ だけです。

消す前に、場所を確かめます。

bash
$ pwd
/home/user/cslab/tree

pwd で必ず確認してください。 これから rm -rf を打ちます。別の場所で打つと、消してはいけないものが消えます。 rm で消したものは戻りません(本線の基本コマンドの回で扱いました)。

bash
$ cd ~
$ rm -rf ~/cslab
$ ls ~

cslab が消えていれば終わりです。

何も入れていないので、これで完全に元通りです。 apt で tree を入れなかったので、システムには一切触っていません。

残しておきたい場合は、bst.js delete.js traverse.js iterative.js の4つだけコピーしておくと使い回せます。 特に delete.js の3パターンと iterative.js の対応表は、詰まったときに読み返す価値があります。


まとめ — 理解できたこと

  • 「木」の条件は「親が1つ・子が複数・輪にならない」の3つだけだった。 丸と線の絵は定義ではない。ディレクトリ・DOM・JSON・組織図は全部この形で、身の回りの木はほとんど子の数に上限が無い(N分木)。「最大2つ」は探索を速くするために人間が付けた制約
  • 「輪にならない」は性質の説明ではなく、コードが終わることの保証だった。 参照を1本足すだけで、たどるコードが Maximum call stack size exceeded で止まり、JSON.stringify も TypeError になった。木だと分かっているから、終了条件を書かずに再帰できる
  • 部分木もそれ自体が木なので、同じ関数をそのまま子に投げれば全部たどれる。 JSON をたどるコードは8行だった。これが木を使う一番の理由で、ループを何重にも書く必要が消える
  • 深さは上から数え、高さは下から数える。 height(null) を -1 と決めると「葉の高さは 0」がそのまま成り立ち、場合分けが1つ消える
  • 二分探索木の見返りは「左は小さい・右は大きい」を守ることで得られる。 min() は左に行き続けるだけの3行で、比較も全件走査もしていない。規則を1つ守ると、最小値の取得がタダになる
  • 探索が O(log n) になる中身は「候補が半分ずつ消える」ことだった。 1023 → 511 → 255 → … → 1 の10回で当たった。 512 と比べた瞬間に 512 件を1件も見ずに捨てている。式ではなく、捨てられる件数の話
  • 木は「無いこと」も log n 回で分かる。 配列の includes は無いことを確かめるのに全件見る
  • 削除だけが本当に難しい。 子が0個・1個は3行で終わるのに、子が2個のときだけ「右の部分木の最小値を持ってきて、その元を消し直す」という2段構えになる。値のコピーで終わらせると、同じ値が木に2つ残る(実際にやった)
  • 削除は「消す関数」ではなく「消したあとの部分木の根を返す関数」として書くと、親を持ち歩かずに済む。 t.root = removeValue(t.root, ...) と返り値で受け直すので、根の特別扱いも不要になった
  • 3つの巡回は暗記するものではなかった。 「左を見る・自分を処理する・右を見る」の3行の順番を入れ替えただけで、pre / in / post は visit が子より前か間か後かを言っているだけ。木を文字で描くコードも、すでに巡回そのものだった
  • in-order でソート済みで出てくるのは偶然ではない。 ただし使い分けで覚える価値があるのは post-order の2つ(ディレクトリの合計サイズ・木の解放)で、あれは順番を選べるのではなく、それしか成り立たない。du は帰りがけそのもの
  • 幅優先だけはキューでしか書けず、再帰では書けない。 段の浅い順に出るので、最初に見つかったものが最も浅いと確定する。段の区切りを付けるには、その段に入る前に人数を確定させる1行が必須
  • 山場。並んでいるデータ(1,2,3,…)を順に insert すると、二分探索木は木にならず、右に伸びた連結リストになる。 40000件で高さ 39999、左の子を持つ節点が 0 件。規則を1つも破っていないのにそうなる
  • 同じ40000件で、入れる順番だけ変えたら探索が 53倍 違った(1239.4 ms 対 23.1 ms、1件あたり比較 20000.5 回 対 18.9 回)。コードは1文字も違わない
  • 「二分探索木の探索は O(log n)」は条件付きの文だった。 正確には「バランスが取れていれば O(log n)、最悪は O(n)」。そして最悪ケースは珍しくない。ORDER BY id で取って順に入れたら、それが最悪ケース
  • 「シャッフルして入れる」は答えにならない。 後から来るデータの順番は選べないし、削除でも形は崩れる。必要なのは運のいい入れ方ではなく、どう入れても崩れない仕掛け(バランス木)で、この言葉が覚える用語ではなくなった
  • 一直線の木は再帰の巡回で落ちる。 20000件で Maximum call stack size exceeded、9637件目まで進んで停止。50000件でも同じ 9637件目で落ちた。上限はデータ量ではなくスタックの容量で決まっている
  • ⑥の問題と⑦の問題は、同じ1つの問題だった。 バランスが取れていれば高さは 37 で、37段の再帰は何の問題もない。深さが問題になるのは一直線に潰れたときだけ
  • 明示的なスタックのループ版に書き換えると、50000件でも通った。 積む場所をコールスタックから普通の配列に移しただけで、メモリは節約していない。 それで直るのはコールスタックが数MB固定なのに、配列はヒープでずっと大きくできるから
  • 「再帰は危ないからループ」ではない。 深さが log n に収まるなら再帰のほうが読める。判断するには木の高さを知る必要がある、というのがこの記事の結論だった
  • 測りたい対象が、測定器を壊した。 一直線の木の高さを再帰で測ろうとして落ちた。これがそのまま⑦の予告になっていたので、消さずに残した

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 8 / 25 本目です。

記事
← 前の記事ハッシュテーブル — 10万件のincludesで止まる
→ 次の記事バランス木とB木 — 100万件が3段で届く

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Trees
  • 二分探索木と3つの巡回
  • 並んだデータを入れると一直線になる

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次