なぜバイナリ検索ツリー？

Question

私はバイナリ検索ツリーを読んでいて、なぜBSTが必要なのかと考えていました。私が知っている限りのすべてのことは、シンプルなソートアレイを使用して達成することもできます。たとえば、n要素を持つBSTを構築するためには、必要です n*O(log n) 時間IE O(nlog n) そして、ルックアップ時間はです O(log n). 。しかし、このことはアレイを使用して達成することもできます。ソートされた配列を使用できます（必要です O(nlog n) 時間）、およびその中のルックアップ時間も O(log n) IEバイナリ検索アルゴ。では、なぜ別のデータ構造が必要なのですか？ BSTのその他の使用/アプリケーションは、それらをとても特別なものにしていますか？

- ラヴィ

Answer 1

一度書くことについて話しているなら、配列は素晴らしいです、何度もタイプの相互作用を読んでください。それは、あなたがアレイと比較してBSTが本当に輝き始める挿入、スワッピング、削除に降りるときです。それらは、連続したメモリの塊に基づいているのではなく、ノードベースであるため、コレクションのソートされた性質を維持しながら、コレクションに要素をコレクションに移動するかコレクションから外すコストが高速です。

リンクされたリストと配列間の挿入の違いを考えてください。これは単純化しすぎですが、上記で述べた利点の側面を強調しています。

Answer 2

100万の要素を持つ配列があると想像してください。

場所5に要素を挿入する必要があります。

したがって、配列の最後に挿入してからソートします。

アレイがいっぱいだとしましょう。それはO（nlog n）で、1,000,000 * 6 = 6,000,000の操作です。

バランスの取れた木があると想像してみてください。

それはo（log n）に加えて、バランスをとるために少し= 6 + a bit a bit a call it could operationsです。

そのため、アレイをソートするのは6,000,000個のOPSを費やしました。それからあなたはしたいです 探す その要素。職業はなんですか？バイナリ検索-O（log n） - まさに ツリーで検索するときにやろうとしていることと同じです！

次に、他の要素を割り当てたいと想像してください。

あなたの配列はいっぱいです！職業はなんですか？ Arrayをn extrace要素で再割り当てし、ロットをmemcpyしますか？あなたは本当に4mbytesをmemcpyしたいですか？

木には、別の要素を追加するだけです...

Answer 3

並べ替えられた挿入時間はどうですか？

Answer 4

グラフィックプログラミングでは、拡張オブジェクト（つまり、ポイントだけでなく各ディメンションの間隔を表す）がある場合、それらは完全に収まるバイナリツリー（通常はオクトリー）の最小レベルに追加できます。

また、ツリー/sortedListを事前に計算しないと、リスト内のO（n）ランダム挿入時間は非常に遅くなる可能性があります。一方、ツリーの挿入時間はo（log（n））のみです。