暗黙・対称な完全二分木の深さ算術
巨大な完全二分木を展開せず、同じ深さの対称性と2冪で集約するか、heap番号の祖先移動と深さdの子孫label区間を使って数える。
この典型を扱う単元: 対称性・深さ・label区間で巨大な完全二分木を数える
検索別名: heap index tree、implicit complete binary tree、symmetric complete binary tree、完全二分木の深さ集約、暗黙の完全二分木
未知問からこの典型を見つける手掛かり
- 扱う対象
- heap番号
- 共通祖先
- 子孫
- 完全二分木
- 深さ
- 使う手掛かり
- 2v
- 2v\+1
- 2倍
- ancestorを上る
- 深さだけで同型
- 頂点数が指数的
- 保つ不変量
- 同じ深さの部分木は同型
- 深さdの子孫は2冪個または連続区間
- 親はfloor\(v/2\)
- 求めるもの
- 子孫数
- 深さ別集約
- 距離層の個数
- 頂点対の個数
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 木モデルと構造
関連する典型
学習成果と学習単位
同じ深さの対称性と2冪で距離splitを集約するか、heap番号の祖先case分解と子孫label区間を使い、巨大な完全二分木を展開せず数えられる。
対称性・深さ・label区間で巨大な完全二分木を数えるで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。