詳解 LOUDS (10) 親ノードから子ノード
さて、今回は逆に「親ノードの番号から、子ノードのインデックスを列挙する」方法を解説します。
例えば、LOUDS の表を使って、4番ノードの子ノードのインデックスを列挙したいとします。
ここで、LOUDS の表で「親」が 4番のブロックで、ビットが "1" となっているところの「index」の行を見てみます。
子のインデックスが9, 10, 11 だということがわかります（インデックス12 の "0" は、ブロックの境界を表しています）。
しかし、実際のデータには「親」という行はないので、ビット列だけを使って、4番ノードの子を知りたいということになります。
ここで、前回と似たような考え方をします。次の図は、左から 4個の "0" を強調したものです。
1個目の "0" は、0番ノードを親とするブロックの終わりを示しています。2個目の "0" は、1番ノードを親とするブロックの終わりを示しています。3個目の "0" は、2番ノードを親とするブロックの終わりを示しています。4個目の "0" は、3番ノードを親とするブロックの終わりを示しています。
知りたいのは、4番ノードを親とするブロックです。ここで、4個目の "0" は 3番ノードを親とするブロックの終わり→4個目の "0" の一個右は、4番ノードを親とするブロックの始まり ということが言えます。
次の図は、4個目の "0" の一個右のビットに注目したところです。
ここが、"4番ノードを親とするブロックの始まり" となります。まず、今注目しているところは、インデックス 9 なので、それが一つ目の子ノードのインデックスとなります。
そこから右に見ていって、"0" にぶつかるまでが "4番ノードを親とするブロック" ということになります。つまり、インデックス 10・11 も、4番ノードの子ノードのインデックスだということがわかります。
これで、「4番ノードの子は、インデックス 9・10・11 のノードである」ということがわかりました。
さてここで、インデックス 9・10・11 のノードが、それぞれ何番ノードかを知ることはできるでしょうか。
前々回の内容を覚えていらっしゃるでしょうか。インデックスからノード番号を得る方法は、そのビットが「左から何番目の "1" のビットか」を数えるということです。
まず、インデックス 9 について見てみましょう。"1" のビットに注目します。
図のように、インデックス 9 のビットは、左から 6番目の "1" のビットです。つまり、6番ノードを表しています。
それがわかると、右隣のビットは 7番ノード、その右隣は 8番ノードだということがわかります。兄弟ノードの番号は連番になっているためです。
これで、ビット列だけから、"4番ノードの子ノードは 6番・7番・8番ノードである" ということがわかったことになります。つまり、親ノードの番号から、それが持つ子ノードの番号を列挙できるということです。
これで、LOUDS のビット列だけで、「子ノードから親ノードをたどる」・「親ノードから子ノードを列挙する」という 2つの操作が行えることになりました。
今回のまとめです。
- ノード番号 x の子ノードのインデックスを列挙するには、x 番目の 0 を探し、そのひとつ右のインデックスから始めて、"0" が見つかるまで（"1" が続く間だけ）インデックスを列挙すればよい。
練習問題です。
1-1. ビット列から、2番ノードが持つ子ノードのインデックスを調べてください。左から 2番目の "0" の、ひとつ右の位置になります。
1-2. その子ノードの「ノード番号」を調べてください。そのインデックスにある "1" が、左から何番目の "1" であるかを調べることでわかります。
2-1. ビット列から、今度は 8番ノードが持つ子ノードのインデックスを列挙してください。
2-2. その子ノードそれぞれの「ノード番号」を調べてください。
前回の答えです。
1. インデックス 18 より左の "0" のビットを数えます。
表の中で、白くなっているところがインデックス 18 より左の "0" のビットです。数えると、8個あることがわかります。このことは、インデックス 18 のノードの親が、8番ノードだということを表しています。
2.インデックス 15・インデックス 6 に対しても、それぞれ左の "0" のビットを数えます。それぞれ 7個・2個ですので、7番ノード・2番ノードが親となります。
インデックスで表した木で、インデックス 18, 15, 6 となっているノード（下の図では 11番、9番、5番ノード）の親が、それぞれ 8番・7番・2番だということを、次の 2つの図で確認してください。
