データ構造_バイナリツリーとは　#440

前回からアルゴリズムとデータ構造について書き始めました。

今回はデータ構造の一種であるバイナリツリーの概要についてまとめます。

バイナリツリー（二分木）とは

バイナリツリーは、各ノードが最大で二つの子ノードを持つことができるデータ構造です。

GURU99

バイナリツリーの特徴

• ノードベース

  • それぞれの要素がツリーのノードに格納される

• 順序性

  • 例えばバイナリサーチツリー（二分探索木）では、左の子ノードが親より小さく、右の子ノードが親より大きい（左＜親＜右）

  • このように特定のルールでデータが並ぶため、検索・挿入・削除に効率的

• 検索効率

  • バランスが取れている場合、検索、挿入、削除の平均時間複雑度は O(log n) 

  • つまり入力サイズが大きくなっても実行時間は比較的遅く増加する

バイナリツリーの欠点

ツリーが不均衡になると操作の効率が低下します。最悪でO(n)、つまり入力サイズが大きくなるほど、探索にかかる時間も長くなることになります。

バイナリツリーの走査方法

このデータ構造を走査する方法は主に４つあります。

• Pre-order Traversal

• In-order Traversal

• Post-order Traversal

• Level-order Traversal

これらの詳細は後日まとめます。

バイナリツリーの利用シーン

高速なデータ処理が要求される、様々なアプリケーションで利用されています。例えば以下です。

データベース管理システム（DBMS）
コンパイラやインタプリタ
グラフィックス
機械学習

データ構造入門：二分木の仕組みと実装

奥深くて面白いですね。
どんどん学んでいきたいと思います。

参考

データ構造の二分木 (例)

26. バイナリーツリー

データ構造入門：二分木の仕組みと実装