• 締切済み

木構造のデータ処理・検索に関する質問

情報処理のデータ構造にツリー構造というものがあります。 １つのノードから複数のノードが派生して出ており、一番最初を親として子・孫という言い方をしたり、根（一番上とか下）から始まって葉に向かう階層構造のようなものですね。情報処理の専門家はおなじみだろうと思います。 そのようなツリー構造の１つの例として四分木構造というものがあり、カーペットを４つ切りにして細かく見ていくような感じです。以下に説明サイトがあります。１つ１つのカーペットをノードと称するようです。 https://ja.wikipedia.org/wiki/%E5%9B%9B%E5%88%86%E6%9C%A8 カーペットという平面を４つ切り（小さなカーペット）にするので階層が深まる（何回も４分の１にする）につれて部分的に分解能が上がるという利点があります。 この四分木構造について以下のような質問があります。 １．添付図なのですが、最終的に使用する格子は葉（これ以上分岐しない）となります。 この場合、その葉格子が別のどの葉格子と境界を接しているか抽出するアルゴリズムとしてどのようなものがあるでしょうか。 ２．分木構造は細分化している処理は足しこんでいくだけなので与しやすしですが、その逆つまり、分木構造をやめて４つ切りから１つに統合する場合、どのようなアルゴリズムになるでしょうか。ノードが消えていくのですが、ノード番号などの割り振りは変えず、全体番号として歯が抜けたようになっていくのでしょうか。 要は分木が増えたり減ったりすることをダイナミックに処理する方法なのですが。 フォートランでできないかなと思っています。Cの再帰呼び出し、ポインタで処理するのが普通らしいですが、ループと配列でフォートランでもできるとのことでした。 よろしくお願いします。

画像を拡大する

みんなの回答

  • chachaboxx
  • ベストアンサー率23% (412/1777)
回答No.1

ご質問にあるリンクページの下方に記載されている『データ構造』テーブルに出典されている、BSP木がアルゴリズムに詳しいかと。 レンダリングのサンプルコードもあります。 https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%A4%E3%83%8A%E3%83%AA%E7%A9%BA%E9%96%93%E5%88%86%E5%89%B2

skmsk1941093
質問者

お礼

回答ありがとうございます。 コンピュータグラフィックスは描画速度の向上が目的でポリゴンに付与された深さ（奥行情報の段階）にはグラデーションになるみたいに細分化されるようです。目に見えるものが精度よくなっていればいいということでしょうか。 私の方は単純で形状が正方形であり、深さ方向には5段階もあれば十分というものです。たいていは3段階ぐらいです。そのかわり隣はどうなっているかということと、その隣との間で物理量のやり取りを考える必要があります。コンピュータグラフィックスでもシューティングゲームのように接触・衝突の判別になると絵を描いてみせる以上の処理が必要のようですが。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 木構造の最底辺にあるノード？

    表題から、 （htmlでの質問ではないのですが…） 例えば「xhtml」文書の中に「<em>強調</em>」とある場合、 ・「em」要素の内容 ・「em」要素の全体 どちらが最底辺（葉ノード）なのでしょうか？ 木構造内の全てのノードは、 そのノードを頂点とする部分木の根ノードと見なすことができる。 http://ja.wikipedia.org/wiki/%E6%9C%A8%E6%A7%8B%E9%80%A0_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0) から引用。 と書いてあるのですが、私には、（上の例えを使うと） 「em」を頂点とする部分木の下方に最底辺「強調」がある。 と読めます（なので、要素の内容が葉ノード？）。 「<p>開始<em>強調</em>終了</p>」とある場合、 開始（葉ノード）と、 「em」要素（部分木の根ノード）は、 兄弟？ …よろしくお願いします…

    • 締切済み
    • XML
  • 木構造（位相構造）を比較するアルゴリズムって？

    木構造（位相構造）を2つ用意し、根からたどって比較してゆき、 差分をとるようなプログラムを書こうと思っています。 しかしアルゴリズムがまったくわからないので質問させていただきます。 子ノードの順番が異なる場合も同じものと見なすような条件で、 末端にノードが追加された程度の差異がわかればよいです。 （鏡に映した構造や、子ノードがABCという順だったのを、ACBにしたような構造は同じものと見なしたいということです。） このようなアルゴリズムというのはあるのでしょうか？

  • 二分探索木のheight(高さ?)を見つけるアルゴリズム

    Binary Search Tree(=二分探索木)のheight(高さ?)を見つけるメソッドを作りたいのですが、 そのアルゴリズムが頭にうまく浮かびません。 まず思いついたのは一つ一つのNode(=ノード)をそれぞれのLeaf(=リーフ、葉?)まで辿っていって それらのheightを全部記憶させておいて後で比較するという…最も原始的な方法です。 しかし、Treeの大きさも未知なので用意する変数の数も未知になって どう考えても不適当でしょう(当たり前か(^^ゞ)。 Recursion(=再帰)を使えばいいのでしょうか? そうだとしてもどうすればいいのか…。 アルゴリズムがパッと浮かぶ方、どうか教えて下さい。

    • ベストアンサー
    • Java
  • excel vbaで木構造データを扱いたい

    excelシートに展開された木構造データのノード数を数える プログラムを造っていますが、実装方法が見えなくなってきました。 □シート構造 　　→列方向　↓行方向と呼ぶ 　　列方向のセル数は固定 　　行方向のセル数は可変 　　いずれもexcelが扱える行列数に収まっている。 □データ構造とデータの特徴 下記のような木構造データです。 　 A 　B C D ---------------------------------- 1 場所1 4 1 1 2 場所1 4 1 2 3 場所1 4 2 1 4 場所1 4 2 2 5 場所1 4 2 4 6 場所2 4 1 1 7 場所2 5 3 1 8 場所2 5 3 2 9 場所2 6 1 2 10 場所7 4 2 1 11 場所7 4 2 2 12 場所7 4 4 3 A列：同じ値が複数存在 B列：任意の整数 C列：1～ 4の任意の整数 D列：1～32の任意の整数 A列からD列ごとに昇順ソート済 　　（A列でソート済みデータを 　　　B列でソート、さらにC列でソート...） C列D列は、1から始まることが多いが、 1が無い可能性もある □やりたいこと 　●A列・B列・C列ごとのD列のエントリ数の計算 　　　計算結果 　　　 場所1-4-1　は、2エントリ（1-2行目） 　　　 場所1-4-2　は、3エントリ（3-5行目） 　　　 場所2-4-1　は、1エントリ（6行目） 　　　 場所2-5-3　は、2エントリ（7-8行目） 　　　 場所2-6-1　は、1エントリ（9行目） 　　　 場所7-4-3　は、3エントリ（10-12行目） ●A列・B列ごとのC列のユニークさの評価 　　計算結果 　　　場所1-4　は、5エントリ（1-5行目）で、C列のユニークな値は1,2 　　　場所2-4　は、1エントリ（6行目）で、C列のユニークな値は1 　　　 場所2-5　は、2エントリ（7-8行目）で、C列のユニークな値は3 　　　 場所2-6　は、1エントリ（9行目）で、C列のユニークな値は1 　　　 場所7-4　は、3エントリ（10-12行目）で、C列のユニークな値は2,4 　木構造を作って、ノードの数を数えればいいのかと思ったのですが、 　結果はexcelのセルに表示する形としたいために、どう作ればいいか 　思いつきませんでした。 アルゴリズムや実装のヒントをいただけないでしょうか よろしくお願いいたします。

  • [データ構造・アルゴリズム] B木について

    B木について分からないことがあるので教えて頂けたらありがたいです． 1. 平均で16個の子ノードのあるBツリーでは，100万件のデータにアクセスするとすると，最大何回のアクセスが必要になるか？また，その時に必要となる時間は何秒か？ハードディスクからのデータの転送時間は無視できるものとし，データはディスクの上にランダムに並んでいるものとする． 2. B木はメモリ上のデータへのアクセスよりは，外部記憶装置へのアクセスに適しているといわれている．その理由を簡潔に述べよ． 3. B木の1つのノードに格納できるキーの数を増やしていけば，データアクセスの効率はどうなっていくか？定性的に結果を推測せよ． 自分で考えた解答は 1. 10回 2. 探索がやりやすくなるから（よく分かりません・・・） 3. 良くなっていく（よく分かりません・・・） なのですがどうでしょうか？真剣に分からないのでアドバイスなど良かったらお願いします！

  • C#のツリービューでツリーノードとデータの関連付け

    こんにちは。 C#でツリービューの操作をしています。 すでに階層構造を持つデータがあります。これをツリービューに表示させようとしています。 TreeNode treeNodeFruits = new TreeNode("果物"); としてツリービューに追加してあげると普通に表示できますが、このままだと独自データと関連付けがされていないため、ノードをクリックした際に何もできません。 C++ではHTREEITEMのlParamにユーザーデータのポインタをセットできますが、C#ではツリーノードに関連付けできそうな項目が見当たりません。 C#ではツリーノードと独自に持つデータとの関連付けをどのようにすればよろしいのでしょうか？

  • データ構造の保存法について

    データ構造のメモリ上の状態、つまりポインターによるノード間のつながりをファイルに保存して、そのファイルを読み込むとコンピュータ上で前回のデータ構造を再現（ポインターによるつながりを再現）できる方法を探しています。 現在バイナリーツリーで上記の保存法を色々探したり考えたりしているのですが、いい方法が見つかりません。 各ノードに番号をふってファイルに保存し、次回読み込んだときに上手く工夫してやればできるかな、といった程度です。 ご存知の方がおられたら教えていただけないでしょうか？ よろしくお願いいたします。

  • 退化木をバランス木にしたい

    二分探索木でアドレス帳を作っています。 二分探索木はノードの削除を繰り返すと退化木になってしまいますが、 これを回避するために二分探索木を再構成して、バランス木に近い形にしたいのです。 この二分探索木を再構成するアルゴリズムが全く思いつかず困っています。 詳しい方、ご教授お願い申し上げます。 ちなみに言語はCです。

  • haskellでの木構造処理でエラー

    「すごいhaskellたのしく学ぼう！」という本でhaskellを勉強している者です。 現在haskellでの木構造の処理について部分を読んでいるんですが、この本のサンプル通りにやってもうまくいきません。 以下がそのサンプルです。 data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show) data Direction = L | R deriving (Show) type Directions = [Direction] freeTree :: Tree Char freeTree = Node 'P' (Node 'O' (Node 'L' (Node 'N' Empty Empty) (Node 'T' Empty Empty) ) (Node 'Y' (Node 'S' Empty Empty) (Node 'A' Empty Empty) ) ) (Node 'L' (Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty) ) (Node 'A' (Node 'A' Empty Empty) (Node 'C' Empty Empty) ) ) changeToP :: Directions -> Tree Char -> Tree Char changeToP (L:ds) (Node x l r) = Node x (changeToP ds l) r changeToP (R:ds) (Node x l r) = Node x l (changeToP ds r) changeTop [] (Node _ l r) = Node 'P' l r 簡単に説明すると、 changeToP Directions (Tree Char) で Directions に従い木を再帰的に処理し、ノードの文字をPに変更した木を返します。 例えば changeToP [R,L] freeTree とすると Node 'P' (Node 'O' (Node 'L' (Node 'N' Empty Empty) (Node 'T' Empty Empty) ) (Node 'Y' (Node 'S' Empty Empty) (Node 'A' Empty Empty) ) ) (Node 'L' (Node 'P'　　　　　　　　　　-- ここが'W'から'P'に変わります (Node 'C' Empty Empty) (Node 'R' Empty Empty) ) (Node 'A' (Node 'A' Empty Empty) (Node 'C' Empty Empty) ) ) となります（'W'が'P'に変わります）。 しかしこれがうまく行きません これをそのまま評価すると Node 'P' (Node 'O' (Node 'L' (Node 'N' Empty Empty) (Node 'T' Empty Empty)) (Node 'Y' (Node 'S' Empty Empty) (Node 'A' Empty Empty))) (Node 'L' *** Exception: /Documents/foo.hs:(25,1)-(26,57): Non-exhaustive patterns in function changeToP といったエラーを吐きます。 「パターンが徹底されていない」といった意味のエラーのようなんですが、パターンマッチは完璧だと思います。 ていうか、そもそも本のサンプル通りに書いてます。 本ではこれでうまくいくようなんですが自分の環境ではこのざまです。 何がいけないでしょうか。 ちなみにOSはmac os x 10.7.5で、haskell処理系はghc 7.4.2です。 よろしくお願いします。

  • データ構造とアルゴリズム

    学校の課題なのですが、試験の得点順（降順）に学生番号と得点を表示することができるシステムを行っています。 仕様は下記の通りです。 外部仕様 １．試験の得点順（降順）に学生番号と得点を表示 ２．機能メニュー（１：追加、２：削除、３：表示、１～３以外：終了）で操作できる ３．機能メニューの１：追加を選択すると、キーボードから学生番号と得点を入力することができる ４．機能メニューの２：削除を選択すると、キーボードから入力した学生番号のデータを削除することができる。 ５．機能メニューの３：表示を選択すると、入力されているデータが、得点順に表示される 内部仕様 １． 使用言語はC言語とする ２． ダミーノードを使わない順方向リスト構造とする ３． リストのノードは構造体を使用する ４． リストのノードが常に得点の降順で並ぶように追加する ５． 入力データ型は、機能メニューを選択するための数字と得点は整数型、学生番号は文字列型とする ６． 先頭のノードのポインタを格納する変数名はheadとする ７． 全体の処理の流れは図１のとおりとし、【テンプレート・プログラム】の必要箇所に必要な機能を追加して完成させるものとする。テンプレート・プログラムで使用されている変数名は、そのまま使用すること。 ８． 機能メニューは、関数名：menu()で表示する。menu()の仮引数は無し、戻り値は、キーボードから入力されたメニュー番号(整数)とする。 ９． 機能メニューの１：追加では、関数名：insert()において先頭ノードから最後尾ノードに向けて順にキーボードから入力した得点と大小関係を比較し、得点の降順で並ぶように挿入位置を決めるためのアルゴリズムを考えて、新たなノードをリストに挿入する。関数名：insert()、仮引数：無し、戻り値：無し。なお、新しく追加するノードのポインタアドレスは変数pを使用する。追加する場所を探すために参照するノードのポインタアドレスは変数p2を使用する。 １０． 機能メニューの２：削除では、関数名：del()においてキーボードから削除する学生番号を入力し、該当するノードを削除する。学生番号が見つからない場合は何もしない。関数名：del()、仮引数：無し、戻り値：無し。なお、文字列の比較には、strcmp()関数を使用する。 １１． 機能メニューの３：表示では、関数名：disp()において先頭のノードから学生番号と得点を表示する。関数名：disp()、仮引数：無し、戻り値：無し。 この、追加機能のinsert、削除機能のdel、dispをどのように記述すればいいのかが分かりません。 分かる方宜しくお願いいたします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する