詳解 LOUDS (9) 子ノードから親ノード


これまで何回かにわたって、「ノード番号」と「インデックス」の関係を解説してきました。

次の 2点について、だいたいわかっていただけたことと思います。

  • 木のノードは、「ノード番号」の他に、それに対応するビットの「インデックス」を使っても表せる。
  • LOUDS のビット列があれば、「ノード番号」から「インデックス」を求めること、またその逆ができる。

今回からは、LOUDS のビット列を使って「子ノードから、その親ノードを得る」、またその逆の「親ノードから、それが持つ子ノードの一覧を得る」という操作をする方法について解説します。


まず今回は、LOUDS のビット列を使って、「子ノードのインデックスから、親ノードのノード番号を得る」という方法について解説します。

「子のノード番号から親のノード番号」や、「子のインデックスから親のインデックス」ではありません。「子のインデックスから親のノード番号」という、回りくどいことになっています。LOUDS というデータ構造の特性上、このような求め方になります。

これを行う具体的な方法は、子ノードのインデックスが与えられた時、「そのビットの左に、いくつ "0" のビットがあるか」を調べるというものです。それによって、親ノードの番号がわかります。


具体例を見てみます。

まず、インデックスで表した木の、インデックス 11 のノードに注目します。

このノードのノード番号はいくつでしょうか。対応する元の図を見るとわかります。

対応するノード番号は「8番」です。

そして、その親は4番ノードです。

つまり、

  • インデックス 11 に対応するノードは 8番ノードである。
  • 8番ノードの親は 4番ノードである。

ということですので、まとめると

  • インデックス 11 に対応するノードの親ノードは 4番ノードである。

ということです。

このことが、LOUDS のビット列を使って求められることです。


それでは、LOUDS のビット列に、「親」と「子」の行を付け加えたものを見てみます。

インデックスが 11 のところに色をつけてありますので、そこを見て下さい。

下の「子」は 8、上の「親」は 4 になっています。

これは、インデックス 11 に対応するノードが 8番で、親が 4番だということを示しています。

ただ、「親」・「子」の行は実際にデータとして持っているわけではないので、ここではビット列だけから親ノードの番号を知る必要があります。

ここで注目するのが、それぞれの「親」が作るブロックです。

例えば、親が「1」のところには、"1 1 1 0" という 4つのビットがあります。これが、「親を 1番ノードとするブロック」です。

親が「2」のところは、"1 0" という 2つのビットがあり、これが「親を 2番ノードとするブロック」です。

ここで、それぞれのブロックには、最後に "0" がひとつずつあります。

このことを利用すると、インデックスから親ノードを求めることができます。上で述べた、「そのビットの左に、いくつ "0" のビットがあるか」を調べるというものです。

例えば、インデックス 11 の左にある "0" のビットは、次のようになります。

左に 4つの "0" があります。これらはそれぞれ、「親を 0番ノードとするブロック」「親を 1番ノードとするブロック」「親を 2番ノードとするブロック」「親を 3番ノードとするブロック」の終端です。

ということは、インデックス 11 のビットが属するブロックは、「親を 4番ノードとするブロック」だということです。これで、インデックスが 11 のノードの親が 4番ノードだということ、ビット列だけからわかったことになります。



今回のまとめです。

  • 「子のインデックス」から「親のノード番号」を調べることは、子のインデックスの左にいくつ "0" のビットがあるかを数えることによってできる。



今回の問題です。

1. 上と同じビット列を使って、インデックス 18 のノードに対する親ノードのノード番号を調べてください。インデックス 18 より左の "0" のビットを数えることでわかります。

2. 同様にして、インデックス 15・インデックス 6 に対応する親ノードのノード番号を調べてください。



前回の答えです。

1. インデックス 10 のビットが、左から何番目の "1" であるかを数えます。

図のように、7番目だということがわかります。

つまり、インデックス 10 に対応する元のノード番号は 7 だということです。

2. 同じようにして、インデックス 6・インデックス 3 に対応する元のノード番号は、それぞれ 5番・3番です。

ラベルとしてインデックスを使った木の中で、インデックス 1063 のノードを見て下さい。

それらは、元の木の中ではそれぞれ 7番・5番・3番ノードとなっています。