詳解 LOUDS (8) インデックスからノード番号を得る


前回は、「ノード番号からインデックスを取得する」方法について解説しましたが、今回は、逆に「インデックスからノード番号を取得する」方法について見ていきます。前回と似ていますが、逆の手順になります。

大きな木で、ノード番号の代わりにインデックスを使ったものを再掲します。

色をつけて示したインデックス 15のノードが何番ノードかを知りたいとします。

これは、ビット列の中で「インデックス 15 の "1" のビットが、左から何番目の "1" か」を調べることでわかります。


実際に見てみましょう。

木に対応するビット列と、そのインデックスは次のようなものです。矢印で示したところが、インデックス 15 のビットです。

このビットが、左から何番目のビットなのかを数えます。

数えてみると 9番目であるため、インデックス 15 は 9番ノードに対応するということがわかります。

インデックス 15 に対応するノード番号が 9番であることを図で確認してください。



今回のまとめです。

  • あるインデックスからノード番号を復元するには、そのインデックスにある "1" のビットが左から何番目の "1" であるかを調べればよい。



今回の問題です。

1. 上と同じ LOUDS データを使って、インデックス 10 に対応するノード番号を調べてください。インデックスが 10 のところの "1" のビットが左から何番目の "1" なのかを調べることでわかります。

2. 同じように、インデックス 6・インデックス 3 に対応するノード番号を調べてください。


前回の答えです。

1. 左端から "1" を数えると、6番目の "1" のビットのところのインデックスを見ると、9 となっています。答えは、9 です。

2. 同様に、10番目の "1" のビットに対応するインデックスは 17 です。

6番・10番ノードに対応するインデックスが 917 であることを木構造で確認してください。