• 締切済み

Ｂ木とＲ木の違いを教えて下さい

当方、今年情報系の学科に入学しました大学1回生です。 大学のレポートで 問：Ｂ木とＲ木のキー、及び探索方法の違いを調べよ。 という問題が出題されたのですが Ｒ木というものに関する資料が少なくて困っています。 今、自分で調べた結果 探索方法に関しては ・Ｂ木 根から始めて探索キーの値とノードのキーを比較しながら 部分木をたどっていく。 葉に到達したときのに葉のキーの値と探索キーが等しければ成功、 等しくなければ失敗。 ・Ｒ木 点質問で探索キー（？）を含むMBRを探索 範囲質問 というのが違いかなと思うのですが、上手く1つの文章で表現できません。 （Ｒ木の探索方法についてはイマイチ理解できない）　 またキーに関する違いと言うのもイマイチよく分かりません。 違いを教えていただけると嬉しいです。 また、どなたかＲ木に関する詳しい解説のあるＨＰか書籍をご存知ではないでしょうか？ 宜しく御願い致します。

みんなの回答

  • sakusaker7
  • ベストアンサー率62% (800/1280)
回答No.1

> 違いを教えていただけると嬉しいです。 そこがレポートのキモなんだから、それ訊いちゃダメでしょう。 R-tree - Wikipedia, the free encyclopedia http://en.wikipedia.org/wiki/R-tree とか R-tree Portal - Home http://www.rtreeportal.org/ にある情報では不足ですか? ところで > ・Ｂ木 > 根から始めて探索キーの値とノードのキーを比較しながら > 部分木をたどっていく。 > 葉に到達したときのに葉のキーの値と探索キーが等しければ成功、 > 等しくなければ失敗。 これはB+木では?

mkt0509
質問者

お礼

＞そこがレポートのキモなんだから、それ訊いちゃダメでしょう。 回答ありがとうございます。 すみません。どうしても調べられなかったので・・。 英語のページ、参考になりました。 結局、 各ノードが子ノードへのポインタの他に, そのノード中のデータを空間的に全て含む直方体の範囲情報を検索のための索引として持ってるってことでいいんでしょうか？ >これはB+木では? ノードのキーという表現が適切ではありませんでした。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. その他([技術者向] コンピューター)

関連するQ&A

  • schemeで二分探索木の問題について

    schemeの問題で，「二分探索木であることを判定する関数を定義せよ」という問題があります。二分探索木とは，左の部分木に含まれる値はノードの値より小さく，右は大きい二分木です。 頑張って考えたのですが，まったくわかりません。 どなたかご回答をしていただけると助かります。 よろしくお願いします。

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

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

  • 二分探索木と二分探索の違い

    高校のときにCOBOLを用いた二分探索を習いました。 今大学でコンピューター科学を勉強しています。予習をしていたら二分探索木が出てきました。 添付画像のような二分木があるとき、a～jの各ノードに１～１０の整数のどの整数が入るか。 という問題ですが、ちんぷんかんぷんです。 二分探索木というのは、検索で用いる二分探索と同じ考えなのでしょうか。 もし、同じなら、１～１０の中央値の５がルートになりますよね。 このような問題の簡単な求め方があれば教えてください。お願いいたします。

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

    表題から、 （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
  • B+木　逆順に効率よく取り出すには？

    http://en.wikipedia.org/wiki/B+_tree にあるとおり，B+木のリーフ部分を昇順で連続アクセスするのは容易ですが，降順に順次アクセスしたい場合はB木のように枝を探索しながらでないと無理ですよね。 これは隣接するリーフ同士を単方向ではなく双方向リンクでつなげればよい事になりますが，そうすると保持するべきポインタが１つ増え，枝ブロックとリーフブロックサイズが変わってしまうのも何となくいい気がしません。 しかし、昇順降順でソートされた２つの木を用意する・・というのも領域の無駄遣いですし。やはり、B+木で降順でキーを順次取り出したい場合はリーフ部分に双方向リンクを持たせてやるのが普通でしょうか。

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

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

    • ベストアンサー
    • Java
  • 木構造のデータ処理・検索に関する質問

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

  • 木構造を描写すると重なる

    vectorに入った要素をある順序で木構造で表現しようとしてます。 まず bbについてですがi=0から増えていくごとに0,-1,1,-2,2というようになります。これにより一つ目の子ノードは親ノードのy座標と同じ位置で次はposY（親ノードのY座標）-1*y1*2となり次は反対側にという風に下上下上という風に描写していきます。それを再起呼び出しで繰り返すことで全ての文字を木構造表現しています。 木構造の表現は出来ているのですが問題があります。子ノード同士が同じ座標に描かれます。どういうことかというと同じ親ノードを持つ複数の子ノード（子2、子3とします）同士がさらに複数の子ノード（子4）を持つ時に、子4は子4の子3ノードと重なってしまいます。y座標の決定がbbによって同じ振幅になるからだと思います。 しかし打開策が思いつかないので考えられる方法を教えていただきませんか？ 下のプログラム自体はそれほど必要でないと思いますので細かい説明は辞めておきます。 class drawpair{ int bb=0;//子ノードのy座標を決める値 int x1; public drawpair(Graphics g,Vector x,int posX,int posY,Vector causal1){ for(int i=0;i<x.size();++i){ if(i==0){ //親ノードの描写.DrawWordで文字を描写します。 new DrawWord(g,(String)x.elementAt(i),posX,posY); }else{ //y座標を決めるbbの値の設定。 bb +=(int) Math.pow(-1,i)*(i-1); new DrawWord(g,(String)x.elementAt(i),getFontMetrics(f1).stringWidth((String)x.elementAt(0))+posX+50,posY+bb*2*y1); PairNode tes = new PairNode(); x1=tes.nextNode((String)x.elementAt(i),causal1); if(x1!=-1){ new drawpair(g,(Vector) causal.elementAt(x1),getFontMetrics(f1).stringWidth((String)x.elementAt(0))+posX+50,posY+bb*2*y1,causal); } } samplevec.removeAllElements(); } } }

    • ベストアンサー
    • Java
  • c 言語　B tree

    C言語で B-treeを実装するプログラムを書きました。 まだtreeに挿入する関数しか書いておりませんが。。 まず空の根を作ってからそこにどんどん要素を挿入していくのですが、どうも要素が 挿入されていないように思えます。 どこがいけないのか分かる方いらっしゃいませんか？ よろしくお願いします。 #include <stdio.h> #define T 10 struct b_tree{ int key[2*T-1]; struct b_tree *node[2*T]; int size; int leaf;//この節点が葉であったら1とする }; void BTreeCreate(void); void BTreeSplitChild(struct b_tree x,int i,struct b_tree y); void BTreeInsert(struct b_tree t,int k); void BTreeInsertNonfull(struct b_tree x,int k); void PrintBtree(struct b_tree x); struct b_tree root; int main (int argc, const char * argv[]) { // insert code here... /*int t;*/ char command; int key; BTreeCreate(); /*scanf("%d",&t);*/ while (1) { scanf("%c %d",&command,&key); if (command=='E') break; if(command=='I') BTreeInsert(root,key);//木にkeyを挿入 } PrintBtree(root); //木を表示 return 0; } void BTreeCreate(void){//空のB-木の生成 struct b_tree x; x.leaf=1; x.size=0; root=x; } void BTreeSplitChild(struct b_tree x,int i,struct b_tree y){ /*B-木における節点の分割をする節点xのi番目の枝の先にある節点yが飽和であった 場合にyをyの中央値で分ける。yの中央値はxの新たなkeyとなりxの枝数は１つ増える*/ int j; struct b_tree z; z.leaf=y.leaf; //zが葉であるかどうかはyが葉であるかどうかに依る z.size=T-1; //また新しくできるxの子zは最小数のkey(T-1)を持たせる for (j=1; j<= T-1; j++) { z.key[j]=y.key[j+1]; //yの中央値よりおおきい値(T-1個)をzに渡す } if(y.leaf==0){ //またyが個をもつ場合は枝もzに渡す for (j=1; j<=T; j++) z.node[j]=y.node[T+j]; } y.size=T-1; //そしてyのサイズも中央値とzに渡した分小さくなる for (j= x.size+1; j>=i+1; j--) { //xにyの中央値を渡すのでx枝の右半分を1つずつ右へずらす x.node[j+1]=x.node[j]; } x.node[i+1]=&z; //i+1番目の枝に新たな子zのポインタを与える for (j=x.size; j>=i; j--) { //値も右へずらす x.key[j+1]=x.key[j]; } x.key[i]=y.key[T]; //xのi番目の値をyの中央値とする。 x.size=x.size+1; //xは1サイズup } void BTreeInsert(struct b_tree t,int k){ int Tsub=T; //条件部にTが使えなかったのでTsubに退避 struct b_tree r,s; r=t; if (r.size == Tsub) { /*根が飽和だった場合を考える新たな親を必要とするため それをsとする。するとsは葉ではなく、sizeは0, そして元々の根rのポインタを与える*/ s.leaf=0; s.size=0; s.node[1]=&r; root=s; BTreeSplitChild(s,1,r); BTreeInsertNonfull(r,k); } else { BTreeInsertNonfull(r,k); } } void BTreeInsertNonfull(struct b_tree x,int k){ /*未飽和の節点xにkを挿入しようと考える。*/ int i; int Tsub=T; if (x.leaf==1) { /*もし、xが葉であれば大小関係を考えて挿入。その際他のkey を右へ1つずつずらす。またxのサイズを1up*/ while (i>=1 && k<x.key[i]) { x.key[i+1]=x.key[i]; i--; } x.key[i+1]=k; x.size++; } else { /*もしxが葉でなければどこの枝をたどればいいのか考える*/ while (i>=1 && k<x.key[i]) { i--; } i++; if ((*x.node[i]).size == 2*Tsub-1) { /*たどる枝の先が飽和であった場合分割する*/ BTreeSplitChild(x, i, *x.node[i]); if (k > x.key[i]) { i++; } } BTreeInsertNonfull(*x.node[i],k);//枝をたどる } } void PrintBtree(struct b_tree x){ printf("abc"); printf("%d",x.leaf);//実行するとleafが1のままなので、数が挿入されていない？ int i,l;　　　　　　　 if(x.leaf==1){ for (i=1; i<=x.size; i++) { printf("%d def",x.key[i]); } if(l==0)printf("\n"); }else { for (i=1; i<=x.size; i++) { printf("%d ghi",x.key[i]); } if(l==0)printf("\n"); l++; printf(" jkl"); for (i=1; i <= x.size+1; i++) { PrintBtree(*x.node[i]); } } printf("\n"); }

  • 探索アルゴリズムの名称について

    以下の探索もしくは組み合わせのアルゴリズムに名称があるのかを教えていただければ幸いです． ある変数a1,a2,a3・・・，b1,b2,b3・・・があり（それぞれ小さい順にソートされている）， このaとbにより影響する評価関数が最小となる最適な組を探索するアルゴリズムです． (1)まずa1・b1のペアを用いた時の値を算出する． (2)次にa2・b1のペアとa1・b2のペアでの値をそれぞれ算出し，小さい方を見つける． （今回はa1・b2のペアの方が小さかったとします．） (3)次にa2・b2のペアとa1・b3のペアでの値をそれぞれ算出し，小さい方を見つける． (2)，(3)の様な処理を繰り返し行い，最小となるa・bの組を探索する． 以上の様なアルゴリズムなのですが，名称があるのかをお聞きしたいと思います． 言葉で書くとイメージしづらいですが，小学・中学ぐらいで勉強した最短経路問題のように 格子状の図を書くと分かりやすいと思います． 二方向のみをみて探索していきます． 個人的には，二分木探索に近いと思うのですがどうでしょうか？ ただ，進み方によっては，同じ組み合わせを探索する事も出来るので， 完全な二分木探索ではないような気がします． 皆様のお力をお貸しいただければありがたいです． お願いいたします．

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する