Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

入れ子集合モデル

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

自分のテーブルへのリレーションを持った、使いやすくないテーブルの例
ID 名前 上司ID
1 佐藤 NULL
2 鈴木 1
3 高橋 2
4 田中 2
5 伊藤 1
6 渡辺 5
入れ子集合モデルの考え方

作りたい木構造
2019110815024620.png

入れ子構造だとみなす
2019110815080772.png

入れ子集合モデルのテーブルの例
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は入れ子集合モデルを表すために、LeftRightを持つ。
    • データベースに格納するモデルクラスにでも実装してください。
  • ITreeNodeは木構造を表すために、ParentChildrenを持つ。
    • ビューモデルとかに実装したらいいと思います。

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

使い方

// 木構造の構築
// 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

ShTair
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away