詳解 LOUDS (3) 0番ノード

今回は、LOUDS のビット列が意味するところについて解説します。

最初の大きな木を再掲します。

まず、木構造の特徴として、すべてのノード（根を除く）は、自分の親をひとつだけ持つというものがあります。

ここに挙げた木構造でも、例えば 2番は 1番という親を持ち、他に親はありません。ひとつだけ親を持つという性質が、1番以外の他のノードすべてに共通していることを確認してください。

LOUDS は、この性質を利用しているところがあります。ですので、できれば 1番もどこかの子であってくれたほうが都合がいいのです。

そこで、LOUDS では、仮想的に 0番ノードというものがあり、それが 1番の親になっていると考えます。そうすると、この例では次のような木構造になります。

LOUDS のデータを作るときに、まず無条件に 1 0 を置いていましたが、0番ノードを考えることで、この意味がわかりやすくなります。

LOUDS のデータの作り方は、ノードごとに、そのノードが持つ子の数だけ "1" を置き、それに続けてひとつの "0" を置くというものでした。0番ノードについてこれを適用すると、子は 1番ひとつだけなので、ひとつの "1" とひとつの "0" 、つまり 1 0 を置くことになります。

これが、LOUDS を作る時に無条件で初めに置く 1 0 の意味です。

さて、ここで表に新しい行を加えます。「親」という行です。

LOUDS を作る時に置く最初の 2つのビットに対して、「親」という行に 0 という数字を入れています。これは何を表しているのでしょうか。

この 2つのビットは、「ノードごとに、そのノードが持つ子の数だけ "1" を置き、それに続けてひとつの "0" を置く」というルールを、0番ノードに適用してできたものですので、そのことを表しています。

次に、1番ノードにこのルールを適用すると 1 1 1 0 を加えることになりますので、それらに対応する「親」の行には 1 を入れます。

すべてのビット列について「親」の行を付け加えると、次のようになります。

こうすると、どこのビットがどのノードに注目して置いたものかわかりやすいかと思います。この「親」の行は、わかりやすくするために加えたもので、実際にデータとして持っているわけではありません。

ここで、「親」の行が 0 の列を「親が 0番のブロック」、「親」の行が 1 の列を「親が 1番のブロック」のように呼ぶことにします。

ビット列は、「どのノードを（親ノードとして）注目して作ったか」という「ブロック」に分けられるということになります。

今回のまとめです。

ビット列は、「どのノードに注目してビットを置いたか」によって「ブロック」に分けられる。

次回は、それぞれの "1" のビットの意味について考えます。

今回の問題です。

前回の問題では次の木構造に対して LOUDS のビット列を作りましたが、それに「親」の行を追加して、ブロックに分けてください。

仮想的な「0番ノード」を考えるとわかりやすいかと思います。

前回の答えです。

「この木構造に対応する LOUDS のデータを紙に書いてください」というものでした。

答えは、次のようになります。

作り方を復習してみましょう。

まず最初は、無条件に置く 1 0 です。

次は 1番ノードですが、子は 2番ひとつなので、"1" ひとつと "0" ひとつの 1 0 になります。

2番ノードは、子が 3番と 4番の 2つなので、"1" 2つと "0" ひとつの 1 1 0 です。

3番ノードは、子がないので "1" はなく、0 だけです。

これを最後まで続けることで、上のデータになります。