典型タグ

暗黙・対称な完全二分木の深さ算術

巨大な完全二分木を展開せず、同じ深さの対称性と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\)
求めるもの
  • 子孫数
  • 深さ別集約
  • 距離層の個数
  • 頂点対の個数
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: 木モデルと構造

    関連する典型

      学習成果と学習単位

      代表問題

      この典型の考え方を具体的な問題で確かめるための入口です。

      関連問題

      この典型が主タグまたは補助タグとして付いている問題です。