algorithm - 実世界のプログラムで二分探索木を使用しますか？

Question

重複の可能性：
実際には二分探索はどこで使用されますか？
二分木の用途は何ですか？

追加、削除、注文など、さまざまな演習を行いました。

しかし、私は実際のプログラムでの二分探索木の使用を視覚化するのに苦労しています。私はそれが検索のための他のアルゴリズムのいくつかよりもはるかに速いことを意味します。しかし、これはその唯一の用途ですか？

このアルゴリズムを実際のソフトウェアで使用する例をいくつか教えてください。

Answer 1

マップ（または辞書）を使用するときは常に、二分探索木を使用しています。これは、次のような配列を格納する必要がある場合を意味します

myArray["not_an_integer"] = 42;

おそらく二分探索木を使用しています。

たとえば、C ++では、std::mapとstd::hash_map型があります。O(log(n))最初のものは挿入とルックアップを備えたバイナリツリーとしてコード化され、 2番目のものはハッシュマップ（O(1)ルックアップ時間付き）としてコード化されます。

編集：私はちょうどこの答えを見つけました。あなたはそれを見てみるべきです。

Answer 2

コンピュータ グラフィックスでは Binary Space Partition が必要です。これはバイナリ検索を使用します。詳細については、http: //en.wikipedia.org/wiki/Binary_space_partitioningをご覧ください。