二分探索木を読んでいて、なぜBSTが必要なのかと考えていました。私の知る限り、すべてのことは、単純なソートされた配列を使用して実現することもできます。たとえば-n個の要素を持つBSTを構築するには、n*O(log n)時間が必要です。つまりO(nlog n)、ルックアップ時間はO(log n)です。しかし、これは配列を使用して実現することもできます。ソートされた配列（O(nlog n)時間が必要）を持つことができ、その中でのルックアップ時間も、O(log n)つまり二分探索アルゴリズムです。では、なぜ別のデータ構造が必要なのですか？それらを特別なものにするBSTの他の使用/アプリケーションはありますか？
-ラヴィ
配列は、一度書き込み、何度も読み取るタイプの相互作用について話している場合に最適です。配列と比較して BST が本当に輝き始めるのは、挿入、交換、および削除に取りかかるときです。それらはメモリの連続したチャンクに基づくのではなく、ノード ベースであるため、要素をコレクション内またはコレクション外に移動するコストは、コレクションのソートされた性質を維持しながら高速です。
リンクされたリストと配列の間の挿入の違いと同じように考えてください。これは単純化しすぎていますが、上で述べた利点の側面を強調しています。
100 万個の要素を持つ配列があるとします。
5 番目の位置に要素を挿入します。
したがって、配列の最後に挿入してからソートします。
配列がいっぱいだとしましょう。これは O(nlog n) で、1,000,000 * 6 = 6,000,000 操作です。
バランスの取れた木があると想像してください。
これは、O(log n) に、バランスをとるためのビットを加えたもの = 6 + ビットです。これを 10 回の操作と呼びます。
つまり、配列のソートに 6,000,000 オペレーションを費やしたことになります。次に、その要素を見つけます。職業はなんですか？二分探索 - O(log n) - これは、ツリーを探索するときにやろうとしていることとまったく同じです!
ここで、別の要素を割り当てたいとします。
配列がいっぱいです! 職業はなんですか？n 個の余分な要素で配列を再割り当てし、ロットを memcpy しますか? あなたは本当に4mbytesをmemcpyしたいですか？
ツリーでは、別の要素を追加するだけです...
ソートされた挿入時間はどうですか?
グラフィックプログラミングでは、オブジェクトを拡張した場合（つまり、点だけでなく各次元の間隔を表す）、完全に収まる二分木（通常は八分木）の最小レベルにそれらを追加できます。
また、ツリー/ソートリストを事前に計算しないと、リストへの O(n) ランダム挿入時間が非常に遅くなる可能性があります。一方、ツリーへの挿入時間は O(log(n)) のみです。