二分探索木を理解するために
二分探索木とは
探索を目的としたデータ構造である。
各ノード持つデータに制約を持たせる（親子間の大小関係）ことで、平均演算時間が$O(\log n)$となり、線形探索よりも高速な探索が可能となる。
二分木の一種であるため、二分木のデータ構造をもつ。
目的
- 二分探索木を学ぶことで、データ構造とアルゴリズムに対する理解を深めたい。
- 単に二分探索を実装するだけではなく背景になっているデータ構造の考え方を理解する。
内容
-
下記項目について、リンク先の記事で解説する。
- 二分探索木にとりかかる前に二分木データ構造について学んだ。
- データ構造の考え方に馴染むために、一般木についても学んだ。
- 二分探索木を実装し、データ構造と解決できる問題について学んだ。