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

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

ただいまの
回答率

90.51%

  • Python

    7974questions

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

  • C++

    3450questions

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

  • データ構造

    47questions

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

ツリー構造のコンテナ

解決済

回答 4

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,662

can110

score 10320

前提・実現したいこと

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

要素の要件

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

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

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

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

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

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

要件のまとめ

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

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

補足

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • Zuishin

    2017/03/31 19:40

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

    キャンセル

  • can110

    2017/04/01 11:53

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

    キャンセル

回答 4

checkベストアンサー

+2

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

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

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

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

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/04/01 12:26

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

    キャンセル

  • 2017/04/01 13:18

    pythonに暗くあまり役に立つ情報がなくてスミマセン。

    tell_kさんが提示しておられるtreelibを拝見して思いましたが、javaのTreeItemといったものと考え方は似ているように見えました。つまり「ノードを表すモデル」と「それをGUI上での木構造のノードとして表現するためのクラス」は別物となっていて木構造のノードにはGUIとして必要な機能がありノードを表すモデルはGUIのための機能を直接は持たなくてよいという考え方のようです。

    > 表示用と走査用に特化した異なるモノを用意する

    そういう考え方が多いのかもしれませんね。

    キャンセル

  • 2017/04/01 14:07

    「ノードを表すモデル」はデータ、展開状態+有効属性のみを保持。
    - setData,expand,setEnableなりのデータ操作+状態操作関数を持つ。

    「木構造のノードとして表現するためのクラス」は、
    - getCurrentParent、getCurrentNext、getAt(行位置)なりの走査関数
    - insert,removeなりの要素操作関数
    を持つ。また走査(イテレート)に必要な補助データも適切に持つ。

    をうまく実装すれば、コンテナ自体のデータ構造はあまり気にしなくてよさそうですね。
    考えが整理できてきました。

    キャンセル

  • 2017/04/01 14:30

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

    キャンセル

+1

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/04/01 12:11 編集

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

    キャンセル

  • 2017/04/01 12:21

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

    キャンセル

+1

こんにちは。

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

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

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

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

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

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


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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/04/01 12:36

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

    キャンセル

  • 2017/04/01 12:48

    > 実装したほうが早いからかもしれませんね。

    そんな気がします。

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

    キャンセル

  • 2017/04/01 13:53

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

    キャンセル

  • 2017/04/01 14:21

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

    キャンセル

  • 2017/04/01 14:27

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

    キャンセル

+1

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

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

from treelib import Node, Tree

def myfilter(tree):
    def _(node):
        if not node.data.enabled:
            return False
        if node.bpointer and not tree[node.bpointer].data.opened:
            return False
        return True
    return _

class Data(object):

    def __init__(self, enabled=True, opened=True):
        self.enabled = enabled
        self.opened = opened

tree = Tree()
tree.create_node('家康', 1, data=Data())  # root node
tree.create_node('信康', 2, parent=1, data=Data())
tree.create_node('秀康', 3, parent=1, data=Data())
tree.create_node('秀忠', 4, parent=1, data=Data())
tree.create_node('家光', 5, parent=4, data=Data())
tree.create_node('忠長', 6, parent=4, data=Data())
tree.create_node('和子', 7, parent=4, data=Data())
tree.create_node('正之', 8, parent=4, data=Data())
tree.create_node('忠耀', 9, parent=1, data=Data())

print('<全ノードの取得>深さ優先')
for nid in tree.expand_tree(mode=Tree.DEPTH, key=lambda x: x.identifier):
    print(tree.level(nid) * ' ' + str(nid), tree[nid].tag)

print('\n<閉じてる/無効のノードを非表示>')
tree[4].data.opened = False
tree[2].data.enabled = False
for nid in tree.expand_tree(mode=Tree.DEPTH, key=lambda x: x.identifier, filter=myfilter(tree)):
    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 12:56

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

    キャンセル

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

  • ただいまの回答率 90.51%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • Python

    7974questions

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

  • C++

    3450questions

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

  • データ構造

    47questions

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