全二分木とは?二分木の一種で、全ての深さで葉が存在する木構造の基本概念について解説する。

Explanation of IT Terms

全二分木とは?

全二分木は、二分木の一種で、以下の特徴を持っています。

  • 根から葉までの距離が全て同じである
  • 全ての深さで葉が存在する
  • 左右の子供の個数が同じ

全二分木の例を以下に示します。

“`
o
/
o o
“`

このように、全二分木では根から葉までの距離が全て同じであり、全ての深さで葉が存在するため、二分探索などのアルゴリズムに利用されることがあります。

全二分木の基本概念

全二分木には、以下のような基本概念があります。

最大深度

最大深度とは、全二分木の最も深い葉までの距離を表します。全ての葉までの距離が同じであるため、最大深度は全体の深さの半分になります。

ノード数

全二分木のノード数は、以下のように計算できます。

“`
2^(最大深度+1) – 1
“`

葉ノード数

全二分木の葉ノード数は、以下のように計算できます。

“`
2^最大深度
“`

部分木

全二分木の部分木とは、根からあるノードまでの全てのノード、およびそのノードの子孫で構成される二分木のことを指します。

完全二分木との比較

全二分木は、完全二分木と似た構造を持っています。しかし、完全二分木と異なり、全ての深さで葉が存在することが特徴です。また、左右の子供の個数が同じである点も異なります。

まとめ

全二分木は、根から葉までの距離が全て同じで、全ての深さで葉が存在する二分木です。最大深度、ノード数、葉ノード数、部分木など、基本的な概念について解説しました。全二分木は、二分探索などに利用されることがあります。

参考記事

参考サイト

合わせて読みたい

【Google Chrome】右クリックで翻訳がでなくなった時の対策方法の決定版