【初心者】アニメーションで理解する二分探索木（検索・走査編）

#概要
コンピュータサイエンスを学習していると必ず出てくる二分探索木ですが、動きがイメージしにくい内容です。今回JavaScriptで二分探索木の[可視化ライブラリー](https://github.com/nori-ut3g/tree-visualizer)を作ったので、アニメーションを使って二分探索木を解説しました。学習の助けになれば幸いです。

#二分探索木
二分木は下図のようにどの親も2つ以下の子を持つデータ構造です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1750709/91330156-194f-6561-4d0b-b3f38a461f06.png)
その二分木の中でも「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」を満たす二分木を二分探索木と呼びます。下図のような左右の部分木の高さのバランスが取れた構造であれば$O(\log n)$程度で探索できます。
※注意：例えばすべての子が左にあるような偏った二分探索木の場合は、計算量は$O(n)$です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1750709/7c76b626-6513-9cf1-e394-32ddd2e3204e.png)
まずはその探索を見てみましょう。

#探索
配列やリストである値を探索する場合、計算量は$O(n)$です。例えば、0~14の数値データが単方向リンクリストで表される場合、検索に最大15Step必要です。
<p class="codepen" data-height="300" data-default-tab="result" data-slug-hash="BaRVzKZ" data-preview="true" data-user="ut3gs" style="height: 300px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/ut3gs/pen/BaRVzKZ">
  DLL検索</a> by Nori_CS (<a href="https://codepen.io/ut3gs">@ut3gs</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>
一方バランスの取れた二分探索木は計算量は$O(\log n)$です。同じデータ数でアニメーションを見てみましょう。

<p class="codepen" data-height="400" data-default-tab="result" data-slug-hash="BaRxjrX" data-preview="true" data-user="ut3gs" style="height: 300px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/ut3gs/pen/BaRxjrX">
  二分探索木検索</a> by Nori_CS (<a href="https://codepen.io/ut3gs">@ut3gs</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>
最大でもたった4Stepだけで検索することができました。データ量が増えるほど$O(\log n)$が効果を発揮します。今回はデータ数15個程度でしたが、もし全人類80億人のデータベースから一人を特定するようなとき、$O(n)$だと80億Step必要ですが、$O(\log n)$だと30Stepで検索できます。



#走査
木構造の全てのノードにアクセスする一連の処理を走査といいます。走査は深さ優先走査（前順、間順、後順）、幅優先走査があります。
##深さ優先走査
###前順
先行順や行きがけ順とも呼ばれています。下図のように、親→左の子孫→右の子孫の順にアクセスしていきます。
<p class="codepen" data-height="400" data-default-tab="result" data-slug-hash="YzVergZ" data-preview="true" data-user="ut3gs" style="height: 300px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/ut3gs/pen/YzVergZ">
  前順</a> by Nori_CS (<a href="https://codepen.io/ut3gs">@ut3gs</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>

###間順
通りがけ順ともよばれます。下図のように、左の子孫→親→右の子孫の順にアクセスしていきます。
二分探索木だと昇順になります。

<p class="codepen" data-height="400" data-default-tab="result" data-slug-hash="KKmoXBe" data-user="ut3gs" style="height: 400px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/ut3gs/pen/KKmoXBe">
  中間順</a> by Nori_CS (<a href="https://codepen.io/ut3gs">@ut3gs</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>


###後順
後行順や帰りがけ順とも呼ばれています。下図のように、左の子孫→右の子孫→親の順にアクセスしてきます。

<p class="codepen" data-height="400" data-default-tab="result" data-slug-hash="XWREexQ" data-user="ut3gs" style="height: 400px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/ut3gs/pen/XWREexQ">
  後順</a> by Nori_CS (<a href="https://codepen.io/ut3gs">@ut3gs</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>
##幅優先走査
下図のように、浅いほうから順に左側からアクセスしていきます。
<p class="codepen" data-height="400" data-default-tab="result" data-slug-hash="VwbXryz" data-preview="true" data-user="ut3gs" style="height: 300px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/ut3gs/pen/VwbXryz">
  幅優先</a> by Nori_CS (<a href="https://codepen.io/ut3gs">@ut3gs</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>
#まとめ
今回は、検索と走査を見ていきました。本記事でイメージを理解できたら、その他参考書や記事を参考にして実際にコードを書いてみることをお勧めします。
次回は、二分探索木の削除・挿入を扱います。