木にしたのに一直線になることがあります。二分探索木と3つの巡回を実装して、形が崩れる条件を見ます。
これは【深掘り】の記事です。本線の順路ではありません。 本線のデータ構造を自作する回で「配列は先頭への挿入が遅い」「リストは途中を探すのが遅い」ところまでやった人が、「では、探すのが速い入れ物はどういう形をしているのか」を確かめるための記事です。飛ばしても本線は進みます。
この記事のコマンドは、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 件でも通ります
この記事でやること
~/cslab/tree/を作り、まず自分のフォルダをfindで表示して、それが木であることを確かめる。JSON も同じ形であることをコードで出し、輪を1本足して壊す- 用語(根・葉・深さ・高さ・部分木)を、コードの出力と文字で描いた図で片づける。二分木・完全二分木・全二分木の違いもここで
- 二分探索木を書く(
insert/search/min/max/delete)。探索の経路を表示して「半分ずつ捨てる」ところを見る。削除の3パターンは、消した後の木を毎回描いて確かめる - 3つの巡回を書いて、同じ木を3通りで出力して並べる。post-order でディレクトリの合計サイズを出し、pre-order で木をコピーする
- 幅優先(レベル順)を、前回のキューで書く
- 山場。並んだデータを入れて木を一直線にし、高さと探索時間を10000/20000/40000件で実測して表にする
- 再帰版の巡回をわざと落とし、明示的なスタックのループ版に書き換えて、
~/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種類ある |
① 木は覚えるものではなく、すでに使っているもの
まず作業場所を作ります。
v22.14.0
v20 以上なら大丈夫です。 出ない場合は本線のnpmの回に戻ってください。
この記事では npm install を1回もしません。ライブラリは使いません。 使うと、正体を確かめるという目的が消えます。
package.json だけ置きます。import を使うためです。
"type": "module"の意味は「このフォルダの.jsは ESM(import/exportが使える形式)として読む」です。これが無いとimportが構文エラーになります。
自分のフォルダを表示してみる
木の絵を見る前に、すでに手元にあるものを見ます。
練習用に、少し階層のあるフォルダを作ります。
木の形で見たいので tree コマンドを打ちます。
Command 'tree' not found, but can be installed with:
sudo apt install tree
素の Ubuntu Server には tree は入っていません。 私の手元でも入っていませんでした。
この記事では入れません。 find で代用します。find は最初から入っています(本線の基本コマンドの回で使いました。組み立て方はfindの深掘りにあります)。
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 を作ります。
(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行しかありません。
これが木の一番大事な性質です。 部分木もそれ自体が木なので、同じ関数をそのまま子に投げれば、勝手に全部たどれます。 ループを何重にも書く必要がありません。
「輪にならない」を破ってみる
用語の説明でよく出てくる「輪にならない(非巡回)」は、読んでも意味が分かりません。 破ってみます。
RangeError: Maximum call stack size exceeded
5695 歩で止まりました。木ではないので、終わりが来ません
JSON.stringify も無理: TypeError
c.children.push(a) の1行を足しただけで、たどるコードが終わらなくなりました。
そして 前回の記事で出したのとまったく同じエラーが出ました。コールスタックが溢れています。
「輪にならない」は、性質の説明ではなく、コードが終わることの保証です。 木だと分かっているから、終了条件を書かずに再帰できるのです。
JSON.stringify が TypeError になるのも同じ理由です。輪があるものは、木の形の文字列にできません。
スクリーンショットを撮ってください:
01_cycle_overflow.pngnode cycle.jsを実行して、Maximum call stack size exceededと歩数が出ている画面。1行足すだけで壊れることが、この記事の残り全部の前提になります。
② 用語を、図と表で1回だけ片づける
言葉は6つだけです。文字で描いた図で確かめます。
これから作る木を、先に図で出します。
50 ← 根(親がいない)
/ \
30 70
/ \ / \
20 40 60 80 ← 20, 60, 80 は葉(子がいない)
/
35 ← 35 も葉
この木について、深さと高さを出すコードを書きます。
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
読み方はこれだけです。
| 数え方 | この木での例 | |
|---|---|---|
| 深さ | 根から下へ数える。根は 0 | 35 の深さは 3 |
| 高さ | その節点から、いちばん遠い葉まで。葉は 0 | 40 の高さは 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 を作ります。
規則は1つだけです。
入れる値が、いまいる節点より小さければ左へ、大きければ右へ。空いていたらそこに置く。
min と max を見てください。
min(node = this.root) {
while (node.left !== null) node = node.left; // 左に行き続ける
return node.value;
}
これで最小値です。 全件を見ていません。比較もしていません。「左は小さい」という規則が守られているなら、いちばん左が最小だからです。
規則を1つ守るだけで、最小値の取得がタダになりました。 ここがデータ構造の見返りです。
動かす
件数: 8
最小: 20 / 最大: 80
高さ: 3
35 を探す → 見つかった : 50 → 30 → 40 → 35 (4回比較)
60 を探す → 見つかった : 50 → 70 → 60 (3回比較)
55 を探す → 無い : 50 → 70 → 60 (3回比較)
②で書いた depth.js も、これで動きます。
55 を探したときを見てください。 木の中に 55 はありません。それでも3回で「無い」と分かっています。
配列で includes を使ったら、無いことを確かめるには全件見るしかありません(本線の計算量の回でやった O(n) です)。木は、無いことも log n 回で分かります。
木を文字で描く
これから削除をやります。消したあとの形を毎回確認したいので、描くコードを先に作ります。
/-- 80
/-- 70
\-- 60
50
/-- 40
\-- 35
\-- 30
\-- 20
横倒しです。 右の部分木が上、左が下に出ます。首を左に90度傾けると、②で書いた図になります。
draw の中身は「右を描く・自分を出す・左を描く」の3行です。 これは④でやる巡回の1つ(順番を逆にした in-order)そのものです。描画のために書いたコードが、すでに巡回でした。
探索が「半分ずつ捨てる」ところを見る
「O(log n)」は式で見ても何も分かりません。捨てている候補の数を表示します。
件数: 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.pngnode 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 を作ります。削除だけ別ファイルにします。 長いからではなく、ここだけ読み返すことになるからです。
書き方のコツが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パターン全部、消したあとの形を見る
--- 子が無い(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行の順番の話です。
3つの関数を並べて見てください。 違いはvisit(node.value) が何行目にあるか、だけです。
| 名前 | 日本語 | visit の位置 | 覚え方 |
|---|---|---|---|
| pre-order | 行きがけ | 左右を見る前 | 降りる途中で処理する |
| in-order | 通りがけ | 左のあと、右の前 | 左を全部片づけてから処理する |
| post-order | 帰りがけ | 左右を見た後 | 子を全部片づけてから処理する |
「pre / in / post」は、visit が「子より前か・間か・後か」を言っているだけです。 それ以上の意味はありません。
同じ木を3通りで出す
行きがけ 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.pngnode 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/ の合計サイズを出します。帰りがけです。
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 し直すと、同じ形になるはずです。
行きがけの順で作り直した木(高さ 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つの巡回は、全部深さ優先です。行けるところまで潜ってから戻ります。
段ごとに見たいときは、別の道具が要ります。
深さ優先は再帰(=スタック)で書けますが、幅優先はキューでしか書けません。 前回の記事で書いたキューを、そのまま持ってきます。
幅優先(レベル順): 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件で見る
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 段になります)。自分でスタックを持つループ版で測ります。
--- 並んでいる順 (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 回
--- 並んでいる順 (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 回
--- 並んでいる順 (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 | 並んでいる | 9999 | 13 | 132.2 ms | 150.2 ms | 5000.5 回 |
| 10000 | ばらばら | 31 | 13 | 4.1 ms | 5.6 ms | 17.4 回 |
| 20000 | 並んでいる | 19999 | 14 | 502.5 ms | 558.2 ms | 10000.5 回 |
| 20000 | ばらばら | 36 | 14 | 8.1 ms | 16.7 ms | 17.6 回 |
| 40000 | 並んでいる | 39999 | 15 | 1433.8 ms | 1239.4 ms | 20000.5 回 |
| 40000 | ばらばら | 37 | 15 | 13.0 ms | 23.1 ms | 18.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行が落ちます。
5000件を並んだ順に insert しました
再帰版の通りがけ: 成功。5000 件
5000件は通ります。 増やします。
20000件を並んだ順に insert しました
再帰版の通りがけ: RangeError: Maximum call stack size exceeded
9637 件目まで進んで落ちました
Maximum call stack size exceeded。 ①の「輪を作ったとき」と同じエラーです。でも今度は、コードは正しく、輪もありません。
木が深すぎるだけです。
inOrder は、左に降りるたびに1段積みます。一直線の木では、高さがそのまま再帰の段数になります。私の環境では 9637段 で溢れました。
50000件を並んだ順に insert しました
再帰版の通りがけ: RangeError: Maximum call stack size exceeded
9637 件目まで進んで落ちました
50000件でも「9637件目」で落ちています。 件数を増やしても、溢れる段数は変わりません。 上限はデータ量ではなくスタックの容量で決まっているからです(前回で --stack-size を触ったのと同じ話です)。
バランスが取れていれば、この問題は起きません。 40000件でも高さは 37 でした。37段の再帰は何の問題もありません。 深さが問題になるのは、一直線に潰れたときだけです。⑥の話と⑦の話は、同じ1つの問題でした。
明示的なスタックで書き換える
再帰をやめます。 「積む場所を、コールスタックから自分の配列に移す」だけです。
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 になります。
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²) になります。 そしてソートしたいデータは、部分的に並んでいることがよくあります。
「できる」と「使うべき」は別でした。 木ソートは、木が既にある場合に、並んだ結果もタダで取れるという話であって、ソートのために木を作る理由にはなりません。
後片づけ
この記事で作ったものを、全部消します。
まず、何があるか確認します。
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/ だけです。
消す前に、場所を確かめます。
/home/user/cslab/tree
pwd で必ず確認してください。 これから rm -rf を打ちます。別の場所で打つと、消してはいけないものが消えます。 rm で消したものは戻りません(本線の基本コマンドの回で扱いました)。
cslab が消えていれば終わりです。
何も入れていないので、これで完全に元通りです。 apt で tree を入れなかったので、システムには一切触っていません。
残しておきたい場合は、
bst.jsdelete.jstraverse.jsiterative.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 に収まるなら再帰のほうが読める。判断するには木の高さを知る必要がある、というのがこの記事の結論だった
- 測りたい対象が、測定器を壊した。 一直線の木の高さを再帰で測ろうとして落ちた。これがそのまま⑦の予告になっていたので、消さずに残した
参考リンク
- roadmap.sh — Computer Science — このコースがどの項目を扱っているかの地図
- MDN — 再帰 — ①と④で使った、自分を呼ぶ関数の説明
- MDN — RangeError: too much recursion / Maximum call stack size exceeded — ①と⑦で出したエラーの公式の説明
- MDN — JSON.stringify — ①で輪のあるオブジェクトが
TypeErrorになった理由 - MDN — Node.parentNode — DOM に親が1つしか無いのは、DOM が木だから
- MDN — Array.prototype.sort — ④で in-order の結果と突き合わせた相手
- Node.js 公式 — fs.readdirSync — ④の
dirsize.jsでディレクトリの子を取るのに使った関数 - Node.js 公式 — Performance measurement APIs — ⑥の測定に使った
performance.now() - Node.js 公式 — コマンドラインオプション — ⑦で触れたスタック容量の指定(
--stack-size)
次に読む
この記事は 【深掘り】コンピュータ科学 の 8 / 25 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | ハッシュテーブル — 10万件のincludesで止まる |
| → 次の記事 | バランス木とB木 — 100万件が3段で届く |
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- 二分探索木と3つの巡回
- 並んだデータを入れると一直線になる
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント