二分探索木を理解するために

二分探索木とは

探索を目的としたデータ構造である。

各ノード持つデータに制約を持たせる（親子間の大小関係）ことで、平均演算時間が$O(\log n)$となり、線形探索よりも高速な探索が可能となる。

二分木の一種であるため、二分木のデータ構造をもつ。

目的

• 二分探索木を学ぶことで、データ構造とアルゴリズムに対する理解を深めたい。
• 単に二分探索を実装するだけではなく背景になっているデータ構造の考え方を理解する。

内容

• 下記項目について、リンク先の記事で解説する。

  • 二分探索木にとりかかる前に二分木データ構造について学んだ。

  • データ構造の考え方に馴染むために、一般木についても学んだ。

  • 二分探索木を実装し、データ構造と解決できる問題について学んだ。

    • [入門]二分木を理解するために解説しながら自力実装してみた
    • 一般木入門
    • 二分探索木