質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

4回答

6230閲覧

ツリー構造のコンテナ

can110

総合スコア38234

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2017/03/31 09:31

編集2022/12/27 12:52

前提・実現したいこと

以下のような要件を満たすコンテナがほしいです。
ざっくりいえば、ファイルシステムのようなツリー構造のコンテナです。

要素の要件

  • 0個以上の下位階層の要素を持てる。階層数の上限なし。
  • 以下のような、先頭からの順序関係(位置)を持つ。ルート要素からの深さ優先で振られる。
位置データ
1家康
2----長男:信康(子供なし)
3----次男:秀康(子供なし)
4----三男:秀忠
5--------家光
6--------忠長
7--------和子
8--------正之
9----四男:忠輝
  • 階層の展開(開いている/閉じている)状態と要素自体の有効(有効/無効)属性を持ち、外部からの操作によって切り替えることができる。
  • 要素の挿入/削除、展開/有効の切替の処理時間は、速いにこしたことはない。がO(n)は勘弁。

見える、見えないという状態

  • 閉じている要素は、自身だけが見える。下位の要素は見えない。
  • 無効の要素は、自身も下位の要素も見えない。

走査(イテレータ)の要件

  • 見える要素のみまたは展開、有効に関係なく全要素の2種類の状態を対象とした走査ができる。
  • vecorのように先頭からの任意の位置指定で要素を参照できる。走査時間は速いにこしたことはない。
  • 順方向(先頭→末尾)の次の要素への移動は定数時間でできる。

以上の走査の各要件は、個別に満たせればよい(異なるイテレータでよい)
展開の切替や要素の挿入など操作された時点で、現イテレータは無効になってもよい。

要件のまとめ

  • 展開状態と有効属性から発生する「見えない」状態(要素)がある。
  • (見えない要素は飛ばしつつ)先頭からの順序位置で走査できる。

という要件が、独自に実装するとなるとややこしいものになりそうですので、すでに実装されたライブラリなどご存じであれば教えてください。そのものズバリはないと思いますので、類似ライブラリの情報でもありがたいです。
また、C++(STL)での実装系が理想ですが、他言語でもかまいません。

補足

こんなコンテナいいな♪あったらいいな♪なノリの質問です。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2017/03/31 10:40

木構造の幅優先探索ではダメなんでしょうか?
can110

2017/04/01 02:53

すみません。誤解を与える例示でした。順序は深さ優先となります。
guest

回答4

0

ベストアンサー

多分Java(swing/JavaFX)でいえばTreeModel/TreeNode/TreeItemのようなものがそれに該当すると思います。他のGUIシステムにも似たようなものがありそうに感じます。

イテレーターについては、

という要件が、独自に実装するとなるとややこしいものになりそう

確かに幅優先探索をしたいなんて場面を想像すると「ちょっと考え込んでしまう」かも知れません。それでもキューを使えば(本質的には)数行の論理だとも言えます。また深さ優先探索なら再帰によりかなり素直な実装ができますね。

ところで開いたノードあるいは見えているノードという要件があることよりこれはGUI目的で用いる機能だと思います。だとすると探索はGUIノードにそれほど必要だろうかと感じました。そもそもGUI目的で使うノードの場合は幅優先、深さ優先、探索なのか、全走査なのかといった様々なバリエーションの走査機能よりは個々のノードに対するイベント駆動のメカニズムなど表示内容とその制御にかかわる機能が最優先だと思います。もし自分ならそうした機能があるクラスを使いそこに走査機能がなくても気にしないと思います。

一方、もし走査が主目的なら「表示を想定した機能」はあまり必要性を感じません。それよりはむしろDOMに対するxpathのように「狙った条件で任意の深さから検索してくれる」といったより高度な探索機能があるかどうかの方に興味を持つと思います。

もちろんこれら様々な機能を併せ持つクラスを設計することもできるとは思います。ただ個人的には何でも屋の太ったインターフェースであるものより、それぞれの目的に応じて機能的に絞られたシンプルなものが使いやすく感じます。高機能なものはよくないとまでは思いませんが、そうでなくてもかまわない…くらいの感覚でしょうか…

とりとめなく書いてしまいましたが、要するに「表示用」と「高度な走査用」の機能は一緒である必然性はそれほどないのではいか・・・そんなことを感じました。

投稿2017/03/31 11:52

KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

can110

2017/04/01 03:26

まず不適切な例示をお詫びします。順序は深さ優先になります。 基本的に回答いただいたTreeModel~で、プラス展開+有効状態により見た目の位置番号が変わるものになります。 求めるものは純粋なデータ保持・集計のためのコンテナですが、ご推察の通りGUIとも紐づきます。 GUIから要素の追加など+ツリーの展開+有効の切り替えなど編集操作され、行位置番号での要素データ照会があるものになります。 「表示を想定した機能」がそもそもコンテナに必要なのかというご意見。確かに。 質問で提示したイテレータ(またはサブ機能)において、表示用と走査用に特化した異なるモノを用意するということになるかと思います。参考になりました。回答ありがとうございます。
KSwordOfHaste

2017/04/01 04:18

pythonに暗くあまり役に立つ情報がなくてスミマセン。 tell_kさんが提示しておられるtreelibを拝見して思いましたが、javaのTreeItemといったものと考え方は似ているように見えました。つまり「ノードを表すモデル」と「それをGUI上での木構造のノードとして表現するためのクラス」は別物となっていて木構造のノードにはGUIとして必要な機能がありノードを表すモデルはGUIのための機能を直接は持たなくてよいという考え方のようです。 > 表示用と走査用に特化した異なるモノを用意する そういう考え方が多いのかもしれませんね。
can110

2017/04/01 05:07

「ノードを表すモデル」はデータ、展開状態+有効属性のみを保持。 - setData,expand,setEnableなりのデータ操作+状態操作関数を持つ。 「木構造のノードとして表現するためのクラス」は、 - getCurrentParent、getCurrentNext、getAt(行位置)なりの走査関数 - insert,removeなりの要素操作関数 を持つ。また走査(イテレート)に必要な補助データも適切に持つ。 をうまく実装すれば、コンテナ自体のデータ構造はあまり気にしなくてよさそうですね。 考えが整理できてきました。
can110

2017/04/01 05:30

ベストアンサー大変迷ったのですが、機能(役割)をベースに考え実装する方向性を示してくださったという観点から選択しました。 回答くださった皆様、ありがとうございました。
guest

0

python の treelib というライブラリを使えば、ある程度要件をみたすようなものが実装できるかもしれません。

http://treelib.readthedocs.io/en/latest/index.html

python

1from treelib import Node, Tree 2 3def myfilter(tree): 4 def _(node): 5 if not node.data.enabled: 6 return False 7 if node.bpointer and not tree[node.bpointer].data.opened: 8 return False 9 return True 10 return _ 11 12class Data(object): 13 14 def __init__(self, enabled=True, opened=True): 15 self.enabled = enabled 16 self.opened = opened 17 18tree = Tree() 19tree.create_node('家康', 1, data=Data()) # root node 20tree.create_node('信康', 2, parent=1, data=Data()) 21tree.create_node('秀康', 3, parent=1, data=Data()) 22tree.create_node('秀忠', 4, parent=1, data=Data()) 23tree.create_node('家光', 5, parent=4, data=Data()) 24tree.create_node('忠長', 6, parent=4, data=Data()) 25tree.create_node('和子', 7, parent=4, data=Data()) 26tree.create_node('正之', 8, parent=4, data=Data()) 27tree.create_node('忠耀', 9, parent=1, data=Data()) 28 29print('<全ノードの取得>深さ優先') 30for nid in tree.expand_tree(mode=Tree.DEPTH, key=lambda x: x.identifier): 31 print(tree.level(nid) * ' ' + str(nid), tree[nid].tag) 32 33print('\n<閉じてる/無効のノードを非表示>') 34tree[4].data.opened = False 35tree[2].data.enabled = False 36for nid in tree.expand_tree(mode=Tree.DEPTH, key=lambda x: x.identifier, filter=myfilter(tree)): 37 print(tree.level(nid) * ' ' + str(nid), tree[nid].tag)

実行結果

<全ノードの取得(深さ優先)> 1 家康 --2 信康 --3 秀康 --4 秀忠 ----5 家光 ----6 忠長 ----7 和子 ----8 正之 --9 忠耀 <閉じてる/無効のノードを非表示> 1 家康 --3 秀康 --4 秀忠 --9 忠耀

投稿2017/04/01 02:05

tell_k

総合スコア2120

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

can110

2017/04/01 03:56

シンプルで分かりやすそうなライブラリですね。 「見えている」順序位置での要素参照などは自前実装が必要なようですが、参考になります。 回答ありがとうございます。
guest

0

こんにちは。

という要件が、独自に実装するとなるとややこしいものになりそうです

幅優先探索ですね。下記でいけそうな気がします。

1)閉じているノードはその子どもをエンキューしない
2)無効なノードはエンキューしない

問題はイテレータで処理することですが、幅優先探索用のキューをイテレータ内部に保持すれば可能でしょう。

ところで、任意枝数のツリー構造に対応したSTLはありませんので、ほぼ自力開発になるだろうと思います。キューと子どもリストにはSTLが使えると思います。

lispならツリー処理が得意っぽいイメージがあるので、何か使えるものがあるかも。(私はlispを知らないので、単なる想像です。すいません。)


【追記】
ああ、忠輝を見落としてました。よく見ると深さ優先探索ですね。
でも、キューの代わりにスタックを使えば深さ優先探索になりますので、考え方は同じです。

投稿2017/03/31 16:59

編集2017/03/31 17:04
Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

can110

2017/04/01 03:36

分かりにくい例示、失礼しました。推察の通り順序位置は深さ優先で振られます。 イテレータ保持データとしては、(同一階層内での要素位置+アルファ)×現在の階層深さ 程度でおさまりそうですね。 すでにそのようなコンテナ実装ないかと思ったんですが、探しても意外とないです。 実装したほうが早いからかもしれませんね。
Chironian

2017/04/01 03:48

> 実装したほうが早いからかもしれませんね。 そんな気がします。 ところで、普通はイテレータのコピーは軽いけど、このイテレータのコピーはそこそこ重いことが結構大きな欠点になりそうです。 各ノードにparentとnextを記録しておけばスタックなしでも深さ優先探索はできそうな気もします。
can110

2017/04/01 04:53

そうですね。ただ、このイテレータは走査のための補助クラス的なもので、実体としてのイテレータのインスタンスをコピーするケースは少ないと考えています。 また、ノード自体に走査用の補助データを持たせるのは、メモリ無駄に使う気がして躊躇してしまいます。ノートのメンバとしてgetParentを実装するなら必要ですしノード間のアクセスは楽ですが、これは割り切ってイテレータに持たせる方向で考えていました。
Chironian

2017/04/01 05:21

スタックで実装した方が素直に作れるので、開発期間も短くて済むと思いますし、もとのツリー構造の変更にも対応しやすいでしょう。 イテレータのコピーが本質的には不要ならば、スタックを使った方が良さそうですね。
can110

2017/04/01 05:27

やはり自分で実装する方向になっちゃいますね。 求めているものズバリの既存ライブラリはありませんでしたが、方向性ははっきりしてきたので質問して良かったです。 回答ありがとうございます。
guest

0

非表示フラグと閉鎖フラグをノードにつけておいて幅優先探索し、非表示のものはイテレートしない、閉じているものはイテレートして閉鎖キューに放り込む、探索中のノードの親が閉鎖キューにあれば閉じているとみなしてイテレートせず放り込む、幅優先なので一列終わったら閉鎖キューの前回のノードはキューから削除、とこれでできるような気がしますが、外していますか?

投稿2017/03/31 12:36

編集2017/03/31 12:37
Zuishin

総合スコア28656

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

can110

2017/04/01 03:12 編集

まず不適切な例示をお詫びします。順序は深さ優先になります。 回答いただいたいたイテレートの基本的な考えをもとに、幅優先→深さ優先へのロジック修正の一般解としてキュー→スタック利用でいけそうです。 回答ありがとうございます。
Zuishin

2017/04/01 03:21

こちらこそちゃんと見てなくてすみませんでした。木構造の探索でいけるなら具体的な方法は色々ありそうですね。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問