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