#概要
コンピュータサイエンスを学習していると必ず出てくる二分探索木ですが、動きがイメージしにくい内容です。今回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.
###後順
後行順や帰りがけ順とも呼ばれています。下図のように、左の子孫→右の子孫→親の順にアクセスしてきます。