Day 146-Q5 | van Emde Boas Layout

問題

高さ$h$の完全二分木（頂点数$2^h-1$、根=1、左の子=$2i$、右の子=$2i+1$）を考える。van Emde Boasレイアウトは次の再帰規則で配列への並び順を定める。

高さ$1$の木: その頂点1個をそのまま出力。
高さ$h>1$の木（根$r$）: $h_1=\lceil h/2\rceil$，$h_2=h-h_1$とし、
1. 根$r$の高さ$h_1$の上部分木を再帰的にレイアウトし先に出力。
2. 上部分木の葉（深さ$h_1-1$、$2^{h_1-1}$個、左から右）それぞれについて、その左の子・右の子を根とする高さ$h_2$の下部分木を、葉の順・各葉内は左→右の順に再帰的にレイアウトし出力。

高さ$h$が与えられるので、根1の完全二分木のvan Emde Boasレイアウト順の頂点インデックス列を出力せよ。

入力形式

制約

$1 \le h \le 6$（最大63頂点）

入出力例

入力例1

出力例1

1 2 3 4 8 9 5 10 11 6 12 13 7 14 15

h1=2,h2=2。上部分木[1,2,3]の後、葉2の子(4,5)の部分木[4,8,9,5,10,11]、葉3の子(6,7)の部分木[6,12,13,7,14,15]が続く。

概念図：上下分割による連続領域配置

ヒント（段階的開示）

ヒント1（方向性）

素朴なレベル順配置は根から葉までのパスでインデックスが飛び飛びになり、キャッシュに乗った近傍データをほとんど再利用できない。「同じ部分木に属する頂点はメモリ上でも近くに置く」という発想を活かしたい。

ヒント2（アプローチ）

高さ$h$の木をちょうど半分の高さ（切り上げ）で上下分割すると、上部分木は$2^{h_1}-1$頂点というまとまった塊になる。同じ塊に属する頂点を連続領域に固めて配置することを、上部分木・各下部分木それぞれに再帰的に適用すればよい。

ヒント3（誘導）

def get_leaves(root, height):
    if height == 1:
        return [root]
    return get_leaves(2 * root, height - 1) + get_leaves(2 * root + 1, height - 1)

def veb_layout(root, height):
    if height == 1:
        return [root]
    h1 = (height + 1) // 2
    h2 = height - h1
    result = veb_layout(root, h1)
    leaves = get_leaves(root, h1)
    for leaf in leaves:
        result += veb_layout(2 * leaf, h2)
        result += veb_layout(2 * leaf + 1, h2)
    return result

下部分木は葉ノード自身ではなく葉の左右の子を根とする点に注意（葉ノード自身は上部分木側のレイアウトに既に含まれているため）。

模範解答 (Python)

import sys

def get_leaves(root, height):
    if height == 1:
        return [root]
    return get_leaves(2 * root, height - 1) + get_leaves(2 * root + 1, height - 1)

def veb_layout(root, height):
    if height == 1:
        return [root]
    h1 = (height + 1) // 2
    h2 = height - h1
    result = veb_layout(root, h1)
    leaves = get_leaves(root, h1)
    for leaf in leaves:
        result += veb_layout(2 * leaf, h2)
        result += veb_layout(2 * leaf + 1, h2)
    return result

def main():
    data = sys.stdin.buffer.read().split()
    h = int(data[0])
    layout = veb_layout(1, h)
    print(' '.join(map(str, layout)))

main()

Step-by-Step 解説

1高さの分割
$h_1=\lceil h/2\rceil$，$h_2=h-h_1$（$h_1\ge h_2$）に分割する。

2上部分木の再帰レイアウト
根$r$、高さ$h_1$の上部分木を同じ規則で再帰的にレイアウトし結果の先頭に置く。

3上部分木の葉の列挙
深さ$h_1-1$の頂点$2^{h_1-1}$個を、左の子=$2i$・右の子=$2i+1$の規則で$h_1-1$回辿り左から右の順に列挙する。

4下部分木群の連結
各葉の左右の子をそれぞれ根とする高さ$h_2$の部分木を再帰レイアウトし連結する。頂点数は$2^{h_1}-1+2^{h_1}(2^{h_2}-1)=2^h-1$と一致する。

5計算量とキャッシュ効率（発展）
任意の部分木（$2^k-1$頂点）が連続領域を占めるため、ブロックサイズ$B$を知らなくても$O(\log_B N)$回のメモリ転送で探索できる（cache-oblivious）。

6入力例の検証（h=4）
上部分木$[1,2,3]$の後、葉2の子(4,5)から$[4,8,9,5,10,11]$、葉3の子(6,7)から$[6,12,13,7,14,15]$が続き、$[1,2,3,4,8,9,5,10,11,6,12,13,7,14,15]$。

よくあるミス

ミス	原因	正しい書き方
$h_1,h_2$の切り上げ・切り下げを逆にする	`h1 = h // 2`としてしまう	`h1 = (height + 1) // 2`（切り上げ）
`get_leaves`の再帰終了条件がずれる	`height == 0`にしてしまう	終了条件は`height == 1`
下部分木を葉ノード自身を根として呼び出し重複する	`veb_layout(leaf, h2)`としてしまう	葉の子(`2leaf`と`2leaf+1`)をそれぞれ根とする
再帰関数のリスト結合で非効率になる	計算量を意識せず素直に実装	$h\le6$では問題ないが大きい$h$では`append`方式に書き換える
出力の区切りをカンマにする	他言語の配列出力の習慣	AtCoder形式に合わせ半角スペース区切り

次のステップ

発展: $h$の大きい木を生成し、素朴なレベル順配置とvEB配置で根から葉までの経路上のインデックスの「メモリ上の広がり幅」を比較し局所性の違いを定量的に確認せよ。
次回予告: Reeds-Sloaneアルゴリズム（p進数列に対するBerlekamp-Masseyの一般化）

自己評価

完全理解おおむね理解要復習

Day 146-Q5 — van Emde Boas Layout（キャッシュオブリビアスな二分木レイアウト）

問題