詳解 LOUDS (11) 木の検索

今回は、これまでのまとめとして、子ノードを連続してたどっていく手続きについて見てみます。

例として、「根（1番ノード）から、左から 3つ目の子ノードを探す。さらにそのノードの 3つ目の子ノードを探す。さらにそのノードの 1つ目の子ノードを探す」という操作を考えます。

対象とするビット列は、これまでと同じものです。

1. まず、1番ノードの子ノードのインデックスを知るため、ビット列を見て、「左から 1個目の "0" の、ひとつ右の位置」のインデックスを調べます。インデックスは 2 です。1番ノードの 1つ目の子ノードのインデックスが 2 だということがわかります。

2. その子ノードのノード番号を知るために、ビット列を見て、インデックス 2 の位置にある "1" のビットが、左から何個目の "1" であるかを調べます。2個目なので、左から 1つ目の子ノードのノード番号が 2番だということがわかります。

3. 左から3つ目の子ノードを探すことが目的なので、3つ目になるまで "1" のビットを右に見ていきます。1つ目の子ノードのノード番号は 2番なので、ひとつ右（2つ目）は、それに 1 を足した 3番ノードだということがわかります。そのひとつ右が 3つ目で、4番ノードです。つまり、左から 3つ目の子ノードが 4番ノードだということがわかります。

4. 今度は、4番ノードの子ノードのインデックスを調べます。「左から 4個目の "0" の、ひとつ右の位置」のインデックスを調べます。インデックスは 9 です。4番ノードの 1つ目の子ノードのインデックスが 9 だということがわかります。

5. その子ノードのノード番号を知るために、インデックス 9 の位置にある "1" のビットが、左から何個目の "1" であるかを調べます。6個目なので、左から 1つ目の子ノードのノード番号が 6番だということがわかります。

6. 左から3つ目の子ノードを探すということをします。3つ目になるまで、"1" のビットを右に見ていきます。1つ目の子ノードのノード番号は 6番なので、ひとつ右（2つ目）が、それに 1 を足した 7番ノードだということがわかります。そのひとつ右が 3つ目で、8番ノードです。つまり、左から 3つ目の子ノードが 8番ノードだということがわかります。

7. 今度は、8番ノードの子ノードのインデックスを調べます。「左から 8個目の "0" の、ひとつ右の位置」のインデックスを調べます。インデックスは 17 です。4番ノードの 1つ目の子ノードのインデックスが 17 だということがわかります。

8. その子ノードのノード番号を知るために、インデックス 17 の位置にある "1" のビットが、左から何個目の "1" であるかを調べます。10個目なので、左から 1つ目の子ノードのノード番号が 10番だということがわかります。

9. 今回は、1つ目の子ノードを探すことが目的なので、前の手順で覚えた「10番」がそのまま答えになります。

このようにして、「根（1番ノード）から、左から 3つ目の子ノードを探す。さらにそのノードの 3つ目の子ノードを探す。さらにそのノードの 1つ目の子ノードを探す」という操作が行えました。その答えが「10番ノード」になるということを、木を見て確認してください。

今回のまとめです。

LOUDS のビット列のみを使って、ある木の根から子ノードをたどっていくことができる。

今回の問題です。

ビット列を使って、「根（1番ノード）から、左から 3つ目の子ノードを探す。さらにそのノードの 2つ目の子ノードを探す。さらにそのノードの 1つ目の子ノードを探す」という検索を行ってください。

前回の答えです。

1-1. 左から 2個目の "0" のひとつ右の位置は、インデックスが 6 です。ですので、2番ノードの子ノードが持つインデックスは 6 です。

1-2. インデックスが 6 の位置にある "1" のビットが、左から何個目の "1" かを数えます。5個目ですので、答えは 5番ノードです。つまり、2番ノードの子ノードが 5番ノードだということがわかったことになります。

2-1. 左から 8個目の "0" のひとつ右の位置は、インデックスが 17 です。ですので、8番ノードの最初の子ノードが持つインデックスは 17 です。また、その右にも "1" のビットがあるので、インデックス 18 の子ノードも持っています。そこで "1" は終わりなので、8番ノードは 2つの子ノードを持ち、インデックスはそれぞれ 17・18 ということになります。

2-2. まず、インデックス 17 の位置にある "1" のビットが、左から何個目の "1" かを数えます。10個目ですので、答えは 10番ノードです。また、その右にも "1" のビットのノード番号は、10番の次の 11番です。そこで "1" は終わりなので、子ノードのノード番号は 10番・11番ということになります。

図で、8番ノードの子ノードが 10番・11番ノードだということを確認してください。