- 締切済み
二分探索木を用いての探索
- みんなの回答 (8)
- 専門家の回答
みんなの回答
- επιστημη(@episteme)
- ベストアンサー率46% (546/1184)
> ただ、C++はまったくわからない… 僕はC++/JavaなどのOO-languageじゃないと めんどくさくて書く気になりません。 # てか、Cにこだわる理由もメリットもないので。 お役に立てずにごめんなさい。 # どなたかのフォローを希望します。
- επιστημη(@episteme)
- ベストアンサー率46% (546/1184)
> 反則なのは百も承知で、C++なら数行で書けます。 ...やっちまいました^^; 仕切り直し: #include <iostream> #include <set> int main() { std::set<int> tree; for ( int i = 0; i < 10; i += 2) tree.insert(i); std::set<int>::iterator hi = tree.lower_bound(5); std::set<int>::iterator lo = hi; --lo; std::cout << "5 は " << *lo << "と" << *hi << "の間" << std::endl; return 0; } --- 実行結果 --- 5 は 4と6の間
補足
回答ありがとうございます。 私のやりたいことは伝わったようですね。 ただ、C++はまったくわからない… ほんと何回もありがとうございます。
- επιστημη(@episteme)
- ベストアンサー率46% (546/1184)
反則なのは百も承知で、C++なら数行で書けます。 # '枝をたどれ'と答えてはみたものの、Cで実装するのは # ひょいひょいとできることではないので...^^; #include <iostream> #include <set> int main() { typedef std::set<int> tree; // 偶数で木を作る for ( int i = 0; i < 10; i += 2) tree.insert(i); // 5 の前後を見つける std::set<int>::iterator lo = tree.lower_bound(5); std::set<int>::iterator hi = lo; ++hi; std::cout << "5 は " << *lo << "と" << *hi << "の間" << std::endl; return 0; } --- 実行結果 --- 5 は 6と8の間
- επιστημη(@episteme)
- ベストアンサー率46% (546/1184)
> その値は木の中には存在しません。だからその値に近い値を探し出したい > のです。(その値に対して ’<’’>’の両方向で2つ) 木の中になくても同じことです。 検索の過程で辿った枝をスタックに保存し、 それをたどることでその前後が見つかります。 あるnodeに達した時点で存在しないことが明らかに なったとき、そのnodeが持つ値はその値の両側の どちらか一方であるはずです。他方はスタックを 逆に辿り、必要に応じてさらに枝をたどれば見つ かります。 # O(logN)で見つけることを望んでいないなら、 # 深さ優先で列挙すれば小さい順に並ぶので # それが最も簡単です。 時間計算量はO(N)ですが。
補足
何度もありがとうございます。 >O(logN)で見つけることを望んでいないなら 残念ながら望んでいるのです… ニ分木を使おうとしたのはこのためです。 ソートすれば簡単なんですがね~ >検索の過程で辿った枝をスタックに保存し、 >それをたどることでその前後が見つかります。 その保存とその利用方法が難しいんですよ…
- επιστημη(@episteme)
- ベストアンサー率46% (546/1184)
> ある瞬間に値を渡すとその値の両隣?の値が分かるようにしたいのです。 その値を持つnodeが木の中に存在するなら、その両側の値は木の構造より明らかではないでしょうか。 # ごめんなさい、質問の意図がさっぱりわからんのです。
補足
補足説明ありがとうございます。 私の説明不足というか、言葉たらずというか… 分かりにくくて申し訳ありません。 >その値を持つnodeが木の中に存在するなら、 >その両側の値は木の構造より明らかではないでしょうか。 その値は木の中には存在しません。だからその値に近い値を探し出したい のです。(その値に対して ’<’’>’の両方向で2つ) 今回もわかりにくいですね。 どう書けば分かりやすくなるんだろ(笑
- επιστημη(@episteme)
- ベストアンサー率46% (546/1184)
>>両者は'おなじもの'ではないかと > 両者とは何を指しているのですか? 1. 挿入してその左右を見る 2. 普通の二分探索木ではだめなのでしょうか? > ある瞬間に値を渡すとその値の両隣?の値が分かるようにしたいのです。 おっしゃることがわかりません。 '特定の値を持つnodeを二進木の中から探しだす'んじゃないんですか? だったらアルゴリズムは'明らか'だと思いますが。
- επιστημη(@episteme)
- ベストアンサー率46% (546/1184)
あれ? ソートされたデータ列に対する二分検索(binary-search) のことでしょうか? それとも #1 のような二分木(binary-tree)の検索でしょうか?
補足
解答ありがとうございます 二分木による検索です。 二分木にある時点まで挿入を続け… ある瞬間に値を渡すとその値の両隣?の値が分かるようにしたいのです。
- επιστημη(@episteme)
- ベストアンサー率46% (546/1184)
'普通の二分探索木'とは? struct node { int data; struct node* left; // 左の枝 struct ndoe* right; // 右の枝 }; こんな奴? だったら両者は'おなじもの'ではないかと。
補足
解答ありがとうございます。 >こんな奴? そうですこんな奴です で >両者は'おなじもの'ではないかと 両者とは何を指しているのですか?
関連するQ&A
- 二分探索は木のように例えられる?
二分探索は、「半分にして対象外の値を除去しながら探索する」ということですが、分かりやすい例えで言うと、木の枝が伸びるような感じで探索する感じでしょうか? 回答のほうよろしくお願いいたします。
- ベストアンサー
- その他(プログラミング・開発)
- 二分探索木のパターン数
二分探索木のパターン数 二分探索木とは、上の値より大きければ右に、小さければ左に子を作っていくツリー状のものです。 例えば 6 / \ 4 9 /\ / 2 5 8 / 7 こんな感じです。 http://ja.wikipedia.org/wiki/%e4%ba%8c%e5%88%86%e6%9c%a8 で、問題なのですが、[1,2,3,4,5,6,7,8,9]といった9つの数値がある時、二分探索木は何通りできるか。 というものです。図を書いて色々考えてみたのですが求め方が分かりません。 全パターン書き出すのは量的に辛すぎますし、CやPで計算するのでしょうが、どのような式になるのでしょうか?
- ベストアンサー
- 数学・算数
- schemeで二分探索木の問題について
schemeの問題で,「二分探索木であることを判定する関数を定義せよ」という問題があります。二分探索木とは,左の部分木に含まれる値はノードの値より小さく,右は大きい二分木です。 頑張って考えたのですが,まったくわかりません。 どなたかご回答をしていただけると助かります。 よろしくお願いします。
- 締切済み
- その他(プログラミング・開発)
- 探索二分木をバランス化する。
書き込みや削除を繰り返して深さに差の出た探索二分木をバランス化する手続きを作りたいのですが、どのようなアルゴリズムで組めばよいでしょうか。 使用言語はPascalです。 よろしくお願いします。
- 締切済み
- その他(プログラミング・開発)
- 二分探索木の深さについてです。
二分探索木の深さについてです。 この画像の式4.1から4.2への変換の解説・手順。また、式4.2から4.3への変換の解説・手順。最後に4.4への変換の説明をお願いします。 できるだけ詳しく書いていただけると助かります iD(i-1)をD(n-1)を用いて表そうとかんがえたのですが、出来ません。 http://34vv.net/drg/ できないです(T_T)
- 締切済み
- 数学・算数
- 4分木の探索プログラミングについて
全零で初期化した二次元配列の要素の値を ある条件を満たすまで再帰的に処理して値を返していくような プログラムを書いています そこで4分木を使わなければならなくなりました。 4分木の参考サイトが少ないのでアルゴリズムがわからないのですが 二分木の拡張版のようなもので複雑な再帰処理が必要になるでしょうか。
- 締切済み
- C・C++・C#
- 二分探索で方程式の解を求める方法
C言語で二分探索を利用して、以下の方程式を解くように言われたのですが、 本やインターネットで調べましたが、見当がつかず困っています。 2(1-2x)/(33*(1-2x)-x(2x)^5) = 1-(1-x)^(1/4) 上記の式に限らず、複雑な方程式を二分探索で解を求めるようなときのプログラミングについてご指導いただければと思います。 プログラミングは初心者です。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 退化木をバランス木にしたい
二分探索木でアドレス帳を作っています。 二分探索木はノードの削除を繰り返すと退化木になってしまいますが、 これを回避するために二分探索木を再構成して、バランス木に近い形にしたいのです。 この二分探索木を再構成するアルゴリズムが全く思いつかず困っています。 詳しい方、ご教授お願い申し上げます。 ちなみに言語はCです。
- ベストアンサー
- C・C++・C#
- pascalでの二分探索(バイナリサーチ)
ファイルからデータを読み込み,それを整列し,入力された値をデータの中から二分探索によって探索することを繰り返すプログラムが作りたいのですが,どのように記述すればよいのか分かりません。教えてください。
- ベストアンサー
- その他(プログラミング・開発)
- 二分探索木の行きがけ順走査
二分探索木の行きがけ順走査は、普通再起を使うと思います。 再起を使わず、しかも木以外のデータ構造を一切使わないでやることもできる聞いたのですが、具体的にはどうすればいいのでしょう。 木以外に何か使ってもいいのなら、 http://www.psg.cs.titech.ac.jp/pro1/11.pdf の『再起を使わないアルゴリズム』みたいにすれば良いことは調べてわかりました。 再起も使わないで出来るのであれば、自分でもJavaを使って書いてみようかと思っているのでカテゴリはJavaにしました。よろしくお願いします。
- ベストアンサー
- Java
お礼
ありがとうございます。 私も出来ることならC++を使いたいのですが… CとJAVAしかわからないですよ 少し勉強すればC++もいけると思うんですが、 そんな余裕はないし… ># どなたかのフォローを希望します。 どなたかよろしくお願いします。