詳解 LOUDS (6) インデックスでノードを表す

今回から数回にわたって、LOUDS のデータそのままで木構造の操作に扱う方法を解説します。難しくなりますので、文の記述と表と対応させながら読んでください。

元の大きな木に戻ります。ここでは、仮想的な 0番ノードは含めません。

この木に対応する LOUDS のデータは次のようなものでした。

「子」の行に、1 から 11 までのすべてのノード番号が 1回ずつ現れています。

表の中で、それらのノード番号の上の行には "1" というビットが立っています。

"1" というビットは、それぞれあるひとつのノードに対応していることがわかるかと思います。

ここでそれぞれのビットについての左端からのインデックスを表に追加してみます。次のようになります。

これで、それぞれのビットのインデックスがわかりやすくなったことと思います。例えば、8番ノードに対応する "1" のビットは、インデックスは 11 ということがわかります。

以前、「すべてのノードは、対応する "1" のビットをひとつずつ持っている」という話をしたことを覚えているでしょうか。

上の表で、ビットが "1" のところを強調してみます。

「子」の行に注目してください。1〜11 のすべてのノード番号が、それぞれ 1度だけ出現しています。

このことを利用して、子ノードを表すのに、それに対応する "1" のビットのインデックスを使うことを考えます。

例として、8番ノードについて考えます。上の表で、「子」の行が "8" となっているところに注目してください。

"8" の上の上にある "1" が、8番ノードに対応する "1" のビットです。このビットのインデックスは、そのすぐ下の "11" です。つまり、8番ノードを「インデックス」を使って表すと "11" になるということです。このように、すべての子ノードには対応するビットのインデックスがあります。

ここで、元の木構造のそれぞれのノードに対して、対応する "1" のビットのインデックスを、ノード番号の横に書き添えてみます。

例えば、"8/11" というノードに注目してください。このノードは、元の図では "8" とだけ書いてあったノードですが、その横に "11" という、対応する "1" のビットに対するインデックスを書き込んであります。

ここで、インデックスをノード番号に添えるのではなく、元の木のノードにインデックスだけを書き込むと次のようになります。

この木は、書き込んだ数字がノード番号からインデックスになっただけで、元の木とまったく同じものです。元の木と比べてみてください。8番ノードだったところが、インデックス11 となっていることが見て取れると思います。さらに、その 2つの子ノードは、元は 10番・11番でしたが、こちらではインデックス17・インデックス18 になっています。