入れ子集合モデルから木構造を作る

入れ子集合モデルについて、簡単にしか説明しません。詳しくは、ぐぐってください。
すでに詳しく知ってる人は、飛ばして 作ったもの までどうぞ。

入れ子集合モデル

木構造（階層構造）をデータベースに格納しようと思ったとき、自分のテーブルへのリレーションを作るのが、単純だしわかりやすい。しかし、SQLで木の一部を取得するのが面倒だったりして、使いやすくはない。
そこで、入れ子集合モデルという考え方で木構造を保存する場合がある。階層構造を、入れ子の集合構造と見なして保存するわけである。

自分のテーブルへのリレーションを持った、使いやすくないテーブルの例

ID	名前	上司ID
1	佐藤	NULL
2	鈴木	1
3	高橋	2
4	田中	2
5	伊藤	1
6	渡辺	5

入れ子集合モデルの考え方

作りたい木構造

入れ子構造だとみなす

入れ子集合モデルのテーブルの例

ID	名前	Left	Right
1	佐藤	1	12
2	鈴木	2	7
3	高橋	3	4
4	田中	5	6
5	伊藤	8	11
6	渡辺	9	10

入れ子集合モデルを使うと、木の一部を取り出すのが簡単。
例えば鈴木さんの部下が誰か知りたければ、Leftが2以上、Rightが7以下の行を取り出せば、どれだけ階層が深かろうとごっそり全員取り出せる。逆にLeftが2未満でRightが7を超える行は鈴木さんの上司であり、その中でLeftが最も小さい人が鈴木さんの直属の上司となる。

作ったもの

プログラム全体はこちら→ https://github.com/ShTair/TreeBuilder/tree/master/TreeBuilder

プログラムの役割としては、入れ子集合モデルのリストから、木構造を生成すること。
そして、木構造から入れ子集合モデルのLeftとRightを更新すること。

2つのインタフェースがある。

• ITreeItemは入れ子集合モデルを表すために、LeftとRightを持つ。
  • データベースに格納するモデルクラスにでも実装してください。
• ITreeNodeは木構造を表すために、ParentとChildrenを持つ。
  • ビューモデルとかに実装したらいいと思います。

もしデータベースのモデルクラスを木のノードとしても使える場合は、一つのクラスにITreeItemとITreeNodeを両方実装することもできます。

使い方

// 木構造の構築
// ITreeItem を実装するクラスのリストと、 ITreeItem から ITreeNode を生成するメソッドを渡す。
// 渡す ITreeItem のリストは、Left順にソートしてある必要がある。
// 木構造が構築されて、ルートノードのリストが返ってくる。
var roots = TreeBuilder.Rebuild(items, item => new Node(item));

// 木構造を表示したり、何らかの操作を加える

// Left、Rightの更新
// ルートノードのリストと、ITreeNode から ITreeItem を取得するメソッドを渡す。
// ITreeItem はnodeの中に持っておくと便利。もしくはディクショナリにでもしておく。
TreeBuilder.Update(roots, node => node.Item);

テスト用のプロジェクトがリポジトリの中にあるので、そっちも参照のこと。
https://github.com/ShTair/TreeBuilder