ヤマザキの地球偵察記録

ヤマザキさんの個人的な記録・備忘録です。

情報工学レクチャーシリーズ:アルゴリズムとデータ構造 第三章「アルゴリズムにおける基本概念」

  • ”グラフと呼ばれる数学的抽象概念の特殊系” ← 難しいな

  • 木はノード(接点)とそれらを結ぶエッジ(辺)から構成される

  • ノードにはルート(根)と呼ばれる木の起点が一つだけ存在する
  • 子を持たないノードをリーフ(葉)と呼ぶ
  • リーフ以外のノードを内部節点と呼ぶ

k分木

  • 木の中のどのノードも子をk個以下しか持たないとき、その木をk分木と呼ぶ
  • 全てのリーフのレベルが同じで、かつ全ての内部節点にk個の子を持つ場合、この木を完全k分木と呼ぶ

完全2分木

  • レベルがkの節点数は {2^{k}}
  • 高さをhとすると、リーフの数は {2^{h-1}}
  • リーフの数をmとすると、{1+log(m)}
  • 高さをhとすると、ノードの数は {2^{h} - 1}
  • ノードの数をnとすると、{log(n+1)}

再帰