「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。 とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。 まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。 親 → 子 (1) → (2, 3) (2) → (4) (3) → (5)この木構造は以下の重複あり集合によって表現することができる。 { 2, 4, 5, 5, 5 }これだけ書くとなんのこと？と思われるかもしれない。そこでこれから2つのことを説明する。ひとつは「何故、木構造が自然数の重複あり集合で表現できるか」、もうひとつは「重複あり集合で表現することに何の意味があるか」ということ。 何故、木構造が自然数の重複あり集合で表現
