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

概要 コンピュータサイエンスを学習していると必ず出てくる二分探索木ですが、動きがイメージしにくい内容です。今回JavaScriptで二分探索木の可視化ライブラリーを作ったので、アニメーションを使って二分探索木を解説しました。学習の助けになれば幸いです。 二分探索木 二分木は下図のようにどの親も2つ以下の子を持つデータ構造です。 その二分木の中でも「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」を満たす二分木を二分探索木と呼びます。下図のような左右の部分木の高さのバランスが取れた構造であれば$O(\log n)$程度で探索できます。 ※注意：例えばすべての子が左にあるような偏った二分探索木の場合は、計算量は$O(n)$です。 まずはその探索を見てみましょう。 探索 配列やリストである値を探索する場合、計算量は$O(n)$です。例えば、0~14の数値データが単方向リンクリストで表される場合、検索