ここまで、LOUDS のビット列を使って木構造をたどる方法を見てきました。今回は、LOUDS のデータを使って trie を実現する方法を考えます。（trie を知らない方は、情報系修士にもわかるダブル配列をご参照ください） まず、辞書には次の単語が入っていると…

今回は、これまでのまとめとして、子ノードを連続してたどっていく手続きについて見てみます。例として、「根（1番ノード）から、左から 3つ目の子ノードを探す。さらにそのノードの 3つ目の子ノードを探す。さらにそのノードの 1つ目の子ノードを探す」とい…

さて、今回は逆に「親ノードの番号から、子ノードのインデックスを列挙する」方法を解説します。例えば、LOUDS の表を使って、4番ノードの子ノードのインデックスを列挙したいとします。 ここで、LOUDS の表で「親」が 4番のブロックで、ビットが "1" となっ…

これまで何回かにわたって、「ノード番号」と「インデックス」の関係を解説してきました。次の 2点について、だいたいわかっていただけたことと思います。 木のノードは、「ノード番号」の他に、それに対応するビットの「インデックス」を使っても表せる。 L…

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

今回から、「ノード番号」と、それに対応するビットの「インデックス」との関係について解説します。まずは、ノード番号からインデックスへの変換方法について解説します。これまで例として使ってきた木を再掲します。 ここで色をつけて示した、8番のノード…

今回から数回にわたって、LOUDS のデータそのままで木構造の操作に扱う方法を解説します。難しくなりますので、文の記述と表と対応させながら読んでください。元の大きな木に戻ります。ここでは、仮想的な 0番ノードは含めません。 この木に対応する LOUDS …

今回は、LOUDS のデータから木構造が復元できることを示します。次のような手順により実現できます。 まず、木構造の深さ 0 に、根（0番ノード）がひとつある状態から始め、0番ノードを「今見ている親ノード」、LOUDS データの最初のビットを「今見ているビ…

今回は、LOUDS のそれぞれのビットが意味するところについて書きます。最初の大きな木に、仮想的な 0番ノードを加えたものを再掲します。 これに対して LOUDS のデータを作る途中で、1番ノードに対応するブロックまで作り終わったところを考えます。 ここで…

今回は、LOUDS のビット列が意味するところについて解説します。最初の大きな木を再掲します。 まず、木構造の特徴として、すべてのノード（根を除く）は、自分の親をひとつだけ持つというものがあります。ここに挙げた木構造でも、例えば 2番は 1番という親…

今回は、前回紹介した LOUDS のデータをどのように作るかについて説明します。 まず、対象とする木構造を再掲します。 この木構造に対応するデータが、次のようなビット列になるということを前回お話しました。 このビット列の作り方は、次のようになります…

以前、「情報系修士にもわかるダブル配列」が好評だったので、続けて「情報系修士にもわかるLOUDS」を書きました。しかし、残念なことにあまり多くの人にわかってもらえてはいないようです。それで書き直すことにしました。今回は全12回に分けて解説します。…