二分探索木を用いての探索

質問

Ｃ言語でプログラミングしています。

二分探索木を用いて探索するプログラムなのですが
与えられた値の前後の値（与えられた値より大きく(小さく）てその値
に一番近いもの）を見つけたいのですが分かりません。

いろいろとネット等で調べてみると「挿入してその左右を見る」
となっているのですが…。
普通の二分探索木ではだめなのでしょうか？

よろしくお願いします。

回答No.8

επιστημη（@episteme）

> ただ、Ｃ＋＋はまったくわからない…

僕はC++/JavaなどのOO-languageじゃないと
めんどくさくて書く気になりません。
# てか、Cにこだわる理由もメリットもないので。
お役に立てずにごめんなさい。

# どなたかのフォローを希望します。

お礼

ありがとうございます。

私も出来ることならＣ＋＋を使いたいのですが…
ＣとＪＡＶＡしかわからないですよ
少し勉強すればＣ＋＋もいけると思うんですが、
そんな余裕はないし…

＞# どなたかのフォローを希望します。

どなたかよろしくお願いします。

回答No.7

επιστημη（@episteme）

> 反則なのは百も承知で、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の間

補足

回答ありがとうございます。
私のやりたいことは伝わったようですね。

ただ、Ｃ＋＋はまったくわからない…

ほんと何回もありがとうございます。

回答No.6

επιστημη（@episteme）

反則なのは百も承知で、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の間

回答No.5

επιστημη（@episteme）

> その値は木の中には存在しません。だからその値に近い値を探し出したい
> のです。（その値に対して　’＜’’＞’の両方向で２つ）

木の中になくても同じことです。
検索の過程で辿った枝をスタックに保存し、
それをたどることでその前後が見つかります。

あるnodeに達した時点で存在しないことが明らかに
なったとき、そのnodeが持つ値はその値の両側の
どちらか一方であるはずです。他方はスタックを
逆に辿り、必要に応じてさらに枝をたどれば見つ
かります。

# O(logN)で見つけることを望んでいないなら、
# 深さ優先で列挙すれば小さい順に並ぶので
# それが最も簡単です。 時間計算量はO(N)ですが。

補足

何度もありがとうございます。

＞O(logN)で見つけることを望んでいないなら
残念ながら望んでいるのです…
ニ分木を使おうとしたのはこのためです。
ソートすれば簡単なんですがね～

＞検索の過程で辿った枝をスタックに保存し、
＞それをたどることでその前後が見つかります。
その保存とその利用方法が難しいんですよ…

回答No.4

επιστημη（@episteme）

> ある瞬間に値を渡すとその値の両隣？の値が分かるようにしたいのです。

その値を持つnodeが木の中に存在するなら、その両側の値は木の構造より明らかではないでしょうか。

# ごめんなさい、質問の意図がさっぱりわからんのです。

補足

補足説明ありがとうございます。
私の説明不足というか、言葉たらずというか…
分かりにくくて申し訳ありません。

＞その値を持つnodeが木の中に存在するなら、
＞その両側の値は木の構造より明らかではないでしょうか。

その値は木の中には存在しません。だからその値に近い値を探し出したい
のです。（その値に対して　’＜’’＞’の両方向で２つ）

今回もわかりにくいですね。
どう書けば分かりやすくなるんだろ(笑

回答No.3

επιστημη（@episteme）

>＞両者は'おなじもの'ではないかと
> 両者とは何を指しているのですか？

1. 挿入してその左右を見る
2. 普通の二分探索木ではだめなのでしょうか？

> ある瞬間に値を渡すとその値の両隣？の値が分かるようにしたいのです。

おっしゃることがわかりません。
'特定の値を持つnodeを二進木の中から探しだす'んじゃないんですか?
だったらアルゴリズムは'明らか'だと思いますが。

回答No.2

επιστημη（@episteme）

あれ?

ソートされたデータ列に対する二分検索(binary-search) のことでしょうか?

それとも #1 のような二分木(binary-tree)の検索でしょうか?

補足

解答ありがとうございます

二分木による検索です。

二分木にある時点まで挿入を続け…
ある瞬間に値を渡すとその値の両隣？の値が分かるようにしたいのです。

回答No.1

επιστημη（@episteme）

'普通の二分探索木'とは?

struct node {
int data;
struct node* left; // 左の枝
struct ndoe* right; // 右の枝
};

こんな奴? だったら両者は'おなじもの'ではないかと。

補足

解答ありがとうございます。

＞こんな奴?
そうですこんな奴です

で
＞両者は'おなじもの'ではないかと
両者とは何を指しているのですか？