解決済み

二分探索は木のように例えられる?

  • すぐに回答を!
  • 質問No.9598528
  • 閲覧数94
  • ありがとう数0
  • 気になる数0
  • 回答数4
  • コメント数0

お礼率 3% (48/1285)

二分探索は、「半分にして対象外の値を除去しながら探索する」ということですが、分かりやすい例えで言うと、木の枝が伸びるような感じで探索する感じでしょうか?

回答のほうよろしくお願いいたします。

質問者が選んだベストアンサー

  • 回答No.3

ベストアンサー率 44% (188/423)

 「木の枝」は前の方が書かれているように、データ全体の論理構造を図示した時の形からくるものです。

 検索アルゴリズムを「分かりやすい例え」で理解するなら、辞書を引くことだと考えるといいでしょう。二分探索はデータが整列していることが前提なので、文字通り「辞書順」で項目が並んでいる辞書はうってつけです。

 「コンピュータ用語辞典」(そんな辞書があるかどうか知りませんが)で「二分探索(ニブンタンサク)」を調べるときのことを考えます。実際の辞書は1ページに複数の項目があったりしますが、話を簡単にするため見開き2ページで1項目が載っているとします。

1)辞書を真ん中で開く。
2)そのページの項目語と「ニブンタンサク」を辞書順で比較(後ろが大)する。
項目語=「ニブンタンサク」 ->発見 ループ終了
項目語>「ニブンタンサク」 ->そのページより前の部分を全体の辞書だとみなして1へ
項目語<「ニブンタンサク」 ->そのページより後ろを全体の辞書だとみなして1へ

※今、辞書に載っていなかったときのことは考えていません。

このような手順でループを回すと、
毎回データを二つに分けている=探すべきデータが半分に減る
ことで高速に検索できることがわかります。

その他の回答 (全3件)

  • 回答No.4

ベストアンサー率 66% (380/572)

二分探索(バイナリサーチ)は ソート済の配列から特定の値の場所を取り出す手法
(半分にして対象外の値を除去しながら探索するので総当りしなくてすむ)

二分探索木(バイナリサーチツリー)は、各ノードから別のノードへの枝が2本生えている木構造のリスト構造体からノード位置を取り出す手法
(値の大小でノードの方向が決まるので 総当りしなくてすむ)

で別ものですが、これを混同してないでしょか。
  • 回答No.2

ベストアンサー率 45% (410/905)

図を描くと木のように見える事があるってだけでは。

> 木の枝が伸びるような感じで探索する感じでしょうか?

生物の成長をシミュレーションとかしたものではないし。
木の枝が必ず全部の探索空間を網羅するものでもないし。
  • 回答No.1

ベストアンサー率 20% (950/4547)

Q、二分探索とは、木の枝が伸びるような感じで探索する感じでしょうか?
A、否。

二分木探索は、木の枝に例えられてもバイナリーサーチのイメージと木は結びつかない。
結果を報告する
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。
関連するQ&A
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する

ピックアップ

ページ先頭へ