概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

二分探索木

• 各ノードが多くとも2つまでのノードしか持たない二分木の一種で、左の子ノード ≤ 親 ≤ 右の子ノードという制約を持った構造の木
  • 最も左にあるノードが最小ノードで、最も右にあるノードが最大ノードとなる
• 二分探索木に限った話ではないが、木構造の走査（traverse）方法についてかいておく
  • 深さ優先探索（depth-first search）
    • 前順（行きがけ順、前置順、preorder）
    • 中順（通りがけ順、中置順、inorder）
    • 後順（帰りがけ順、postorder）
  • 幅優先探索（breadth-first search）
    • レベル順（level-order）

計算時間

• 挿入・削除
  • 平均するとO(log n)だが、最悪計算量はO(n)。
• 探索
  • 平衡二分探索木であれば、O(log n)で済む。最悪計算量はO(n)。

実装

• 挿入、探索は比較的容易だが、削除は複雑。

参考

• アルゴリズムとデータ構造