概要
コンピュータサイエンスを学習していると必ず出てくる二分探索木ですが、動きがイメージしにくい内容です。今回JavaScriptで二分探索木の可視化ライブラリーを作ったので、アニメーションを使って二分探索木を解説しました。学習の助けになれば幸いです。
二分探索木
二分木は下図のようにどの親も2つ以下の子を持つデータ構造です。
その二分木の中でも「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」を満たす二分木を二分探索木と呼びます。下図のような左右の部分木の高さのバランスが取れた構造であれば$O(\log n)$程度で探索できます。
※注意：例えばすべての子が左にあるような偏った二分探索木の場合は、計算量は$O(n)$です。
まずはその探索を見てみましょう。
探索
配列やリストである値を探索する場合、計算量は$O(n)$です。例えば、0~14の数値データが単方向リンクリストで表される場合、検索に最大15Step必要です。
See the Pen
DLL検索 by Nori_CS (@ut3gs)
on CodePen.
一方バランスの取れた二分探索木は計算量は$O(\log n)$です。同じデータ数でアニメーションを見てみましょう。
See the Pen 二分探索木検索 by Nori_CS (@ut3gs) on CodePen.
最大でもたった4Stepだけで検索することができました。データ量が増えるほど$O(\log n)$が効果を発揮します。今回はデータ数15個程度でしたが、もし全人類80億人のデータベースから一人を特定するようなとき、$O(n)$だと80億Step必要ですが、$O(\log n)$だと30Stepで検索できます。
走査
木構造の全てのノードにアクセスする一連の処理を走査といいます。走査は深さ優先走査（前順、間順、後順）、幅優先走査があります。
深さ優先走査
前順
先行順や行きがけ順とも呼ばれています。下図のように、親→左の子孫→右の子孫の順にアクセスしていきます。
See the Pen
前順 by Nori_CS (@ut3gs)
on CodePen.
間順
通りがけ順ともよばれます。下図のように、左の子孫→親→右の子孫の順にアクセスしていきます。
二分探索木だと昇順になります。
See the Pen 中間順 by Nori_CS (@ut3gs) on CodePen.
後順
後行順や帰りがけ順とも呼ばれています。下図のように、左の子孫→右の子孫→親の順にアクセスしてきます。
See the Pen 後順 by Nori_CS (@ut3gs) on CodePen.
幅優先走査
下図のように、浅いほうから順に左側からアクセスしていきます。
See the Pen
幅優先 by Nori_CS (@ut3gs)
on CodePen.
まとめ
今回は、検索と走査を見ていきました。本記事でイメージを理解できたら、その他参考書や記事を参考にして実際にコードを書いてみることをお勧めします。
次回は、二分探索木の削除・挿入を扱います。