けけずんセルフハッキング

忘れそうなことをメモる。

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

  • ”グラフと呼ばれる数学的抽象概念の特殊系” ← 難しいな
  • 木はノード(接点)とそれらを結ぶエッジ(辺)から構成される
  • ノードにはルート(根)と呼ばれる木の起点が一つだけ存在する
  • 子を持たないノードを リーフ(葉) と呼ぶ
  • リーフ以外のノードを内部節点と呼ぶ

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)

再帰