人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

2分探索木って、どんなところで活用されてますか?
データ構造の中でも、ただの配列やリストなんかはJavaプログラミングでよく見かけますが、2分探索木をプログラムの中で活用しているのを見たことがありません。言語実装とか、そういうところでしょうか?データ構造として、探索が速くなりそうだし、なんとなく使う機会はあるのかなと想像はできるのですが...。


●質問者: 匿名質問者
●カテゴリ:コンピュータ
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● 匿名回答1号

データベースのインデックス。
B-Tree というのが2分探索木。


匿名回答2号さんのコメント
厳密に言えば、B-Tree自体は一般に多分岐 (>2)ですね。オーダーが大きい場合、一つのノードの中のキーを探すのに2分探索を使うことはありますが。 http://ja.wikipedia.org/wiki/B%E6%9C%A8

匿名回答1号さんのコメント
枝葉末節。 木なだけに。

匿名回答3号さんのコメント
>枝葉末節。 だれうまw

2 ● 匿名回答2号

C++ STLのstd::mapなどの実装には平衡2分木が使われていることがあります。JavaのTreeMapも赤黒木ですから2分木の一種ですね。これに限らず、知らないうちに使っていることは多いんじゃないかと思います。

配列やリストに比べてあまり表に出ないのは、色々なバリエーションがあってチューニングの勘どころも多いので、実装の詳細はカプセル化しておく方が何かと便利だからかなあ、という気がします。それと、バランシング操作などは結構ややこしくなることがあり、必要以上に中身を見せるメリットも少ないかと (途中のノードへのポインタを公開していたとしても、バランシングが起きると親や子の関係が変わるので、ライブラリユーザから見たら使いにくい。)

関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ