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

今回から、「ノード番号」と、それに対応するビットの「インデックス」との関係について解説します。

まずは、ノード番号からインデックスへの変換方法について解説します。

これまで例として使ってきた木を再掲します。

ここで色をつけて示した、8番のノードに対応するビットのインデックスを知りたいとします。

ノード番号を LOUDS ビット列上でのインデックスで置き換えた木は次のようなものなので、同じ位置のノードに書いている数字を見ます。"11" と書いてあるので、答えはインデックス 11 です。

LOUDS のデータで見てみます。

この中で、「子」の行で 8番となっているところで「index」の行を見ると 11 となっているということが、その対応を表しています。

しかし、実際にデータとして持っているのは、「LBS」と書かれた行の「ビット列」だけです。ビット列だけを頼りに、8番ノードに対応するビットのインデックスが 11 だということを知るにはどうすればいいのでしょうか。

ここで、表の中で、LBS が "1" の列だけに注目します。

LBS が "1" のところには、必ず「子」のところにノード番号が順番に入り、また LBS が "0" のところにはノード番号がありません。あるノード番号に対応するビットを知りたければ、左から（ノード番号）個目の "1" を探せばいいということです。例えば、8番ノードに対応するビットは、左から 8個目の "1" ということです。