全二分木とは？
全二分木は、二分木の一種で、以下の特徴を持っています。
- 根から葉までの距離が全て同じである
- 全ての深さで葉が存在する
- 左右の子供の個数が同じ
全二分木の例を以下に示します。
“`
o
/
o o
“`
このように、全二分木では根から葉までの距離が全て同じであり、全ての深さで葉が存在するため、二分探索などのアルゴリズムに利用されることがあります。
全二分木の基本概念
全二分木には、以下のような基本概念があります。
最大深度
最大深度とは、全二分木の最も深い葉までの距離を表します。全ての葉までの距離が同じであるため、最大深度は全体の深さの半分になります。
ノード数
全二分木のノード数は、以下のように計算できます。
“`
2^(最大深度+1) – 1
“`
葉ノード数
全二分木の葉ノード数は、以下のように計算できます。
“`
2^最大深度
“`
部分木
全二分木の部分木とは、根からあるノードまでの全てのノード、およびそのノードの子孫で構成される二分木のことを指します。
完全二分木との比較
全二分木は、完全二分木と似た構造を持っています。しかし、完全二分木と異なり、全ての深さで葉が存在することが特徴です。また、左右の子供の個数が同じである点も異なります。
まとめ
全二分木は、根から葉までの距離が全て同じで、全ての深さで葉が存在する二分木です。最大深度、ノード数、葉ノード数、部分木など、基本的な概念について解説しました。全二分木は、二分探索などに利用されることがあります。