- 締切済み
木について
- みんなの回答 （2）
- 専門家の回答
みんなの回答
奥村晴彦 著「コンピュータアルゴリズム事典」技術評論社より引用 ＊＊＊＊＊＊＊ 木を用いる２分探索は、平均的な性能は非常によいのだが最悪の場合には非常に遅いという点で、クイックソートと似ている。 <中略> ２分木の場合は、もしキーの値の小さい順（または大きい順）に挿入したならば、木のバランスが崩れ、最悪の事態になる。 どのような順序でキーを挿入してもバランスが崩れないような木構造はいろいろ工夫されている。 <以下略>
- ballville
- ベストアンサー率47% (233/487)
オンメモリで処理できないほどの大量データを 外部記憶装置を使って処理するのに有効ではないでしょうか
関連するQ&A
- 退化木をバランス木にしたい
二分探索木でアドレス帳を作っています。 二分探索木はノードの削除を繰り返すと退化木になってしまいますが、 これを回避するために二分探索木を再構成して、バランス木に近い形にしたいのです。 この二分探索木を再構成するアルゴリズムが全く思いつかず困っています。 詳しい方、ご教授お願い申し上げます。 ちなみに言語はCです。
- ベストアンサー
- C・C++・C#
- 探索木の問題について
探索木について。 探索木において、探索効率を高めるため（探索経路を短くするため）、子の数を最大ｍ個までとするｍ分探索木を考える。この木の探索についての計算量は、どのように考えれば良いですか。 説明してください。 という問題なのですが 画像のA,Bのタイプのどちらで考えればいいのかわかりません そこで、どちらのタイプで考えればいいのか あわよくば、問題についても答えを教えてください よろしくおねがいします
- 締切済み
- 情報工学
- Ｂ木とＲ木の違いを教えて下さい
当方、今年情報系の学科に入学しました大学1回生です。 大学のレポートで 問：Ｂ木とＲ木のキー、及び探索方法の違いを調べよ。 という問題が出題されたのですが Ｒ木というものに関する資料が少なくて困っています。 今、自分で調べた結果 探索方法に関しては ・Ｂ木 根から始めて探索キーの値とノードのキーを比較しながら 部分木をたどっていく。 葉に到達したときのに葉のキーの値と探索キーが等しければ成功、 等しくなければ失敗。 ・Ｒ木 点質問で探索キー（？）を含むMBRを探索 範囲質問 というのが違いかなと思うのですが、上手く1つの文章で表現できません。 （Ｒ木の探索方法についてはイマイチ理解できない） またキーに関する違いと言うのもイマイチよく分かりません。 違いを教えていただけると嬉しいです。 また、どなたかＲ木に関する詳しい解説のあるＨＰか書籍をご存知ではないでしょうか？ 宜しく御願い致します。
- 締切済み
- その他([技術者向] コンピューター)
- 二分探索木を用いての探索
Ｃ言語でプログラミングしています。 二分探索木を用いて探索するプログラムなのですが 与えられた値の前後の値（与えられた値より大きく(小さく）てその値 に一番近いもの）を見つけたいのですが分かりません。 いろいろとネット等で調べてみると「挿入してその左右を見る」 となっているのですが…。 普通の二分探索木ではだめなのでしょうか？ よろしくお願いします。
- 締切済み
- C・C++・C#
- schemeで二分探索木の問題について
schemeの問題で，「二分探索木であることを判定する関数を定義せよ」という問題があります。二分探索木とは，左の部分木に含まれる値はノードの値より小さく，右は大きい二分木です。 頑張って考えたのですが，まったくわかりません。 どなたかご回答をしていただけると助かります。 よろしくお願いします。
- 締切済み
- その他（プログラミング・開発）
- 二分探索は木のように例えられる？
二分探索は、「半分にして対象外の値を除去しながら探索する」ということですが、分かりやすい例えで言うと、木の枝が伸びるような感じで探索する感じでしょうか？ 回答のほうよろしくお願いいたします。
- ベストアンサー
- その他（プログラミング・開発）
- 二分探索木と二分探索の違い
高校のときにCOBOLを用いた二分探索を習いました。 今大学でコンピューター科学を勉強しています。予習をしていたら二分探索木が出てきました。 添付画像のような二分木があるとき、a～jの各ノードに１～１０の整数のどの整数が入るか。 という問題ですが、ちんぷんかんぷんです。 二分探索木というのは、検索で用いる二分探索と同じ考えなのでしょうか。 もし、同じなら、１～１０の中央値の５がルートになりますよね。 このような問題の簡単な求め方があれば教えてください。お願いいたします。
- ベストアンサー
- その他([技術者向] コンピューター)
