詳解 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番です。
ラベルとしてインデックスを使った木の中で、インデックス 10・6・3 のノードを見て下さい。
それらは、元の木の中ではそれぞれ 7番・5番・3番ノードとなっています。