プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

データ構造における検索ツリーの比較

ここでは、いくつかの検索ツリーとその違いを確認します。多くの異なる探索木があります。それらは性質が異なります。基本的な検索ツリーは、バイナリ検索ツリー（BST）です。他の検索ツリーには、AVLツリー、Bツリー、赤黒木、スプレーツリーなどがあります。

これらのツリーは、操作に基づいて比較できます。これらの木の時間計算量がわかります

検索ツリー 平均的なケース

挿入 削除 検索
二分探索木 O（log n） O（log n） O（log n）
AVLツリー O（log 2 n） O（log 2 n） O（log 2 n）
Bツリー O（log n） O（log n） O（log n）
赤黒木 O（log n） O（log n） O（log n）
スプレーツリー O（log 2 n） O（log 2 n） O（log 2 n）



検索ツリー 最悪の場合

挿入 削除 検索
二分探索木 O（n） O（n） O（n）
AVLツリー O（log 2 n） O（log 2 n） O（log 2 n）
Bツリー O（log n） O（log n） O（log n）
赤黒木 O（log n） O（log n） O（log n）
スプレーツリー O（log 2 n） O（log 2 n） O（log 2 n）

  1. データ構造のBSPツリー

    コンピュータサイエンスでは、超平面をパーティションとして実装することにより、空間を2つの凸集合に再帰的に分割するために、バイナリ空間分割（BSP）と呼ばれる方法が実装されています。この細分化のプロセスにより、BSPツリーと呼ばれるツリーデータ構造の形式で領域内のオブジェクトが表現されます。 バイナリ空間分割は、1969年に3Dコンピュータグラフィックスのコンテキストで発明されました。BSPツリーの構造により、レンダリングに役立つシーン内のオブジェクトに関する空間情報が可能になります。たとえば、オブジェクトは前から後ろに並べられます。すばやくアクセスできるように、特定の場所にいる視聴者を尊重し

  2. データ構造の範囲ツリー

    範囲ツリーは、ポイントのリストを保持するための順序付けられたツリーデータ構造として定義されます。これにより、特定の範囲内のすべてのポイントを効率的に取得でき、通常は2次元以上で実装されます。 O（log d のクエリ時間が速いことを除いて、kdツリーと同じです。 n + k）が、O（n log d-1 のストレージが悪い n）、dはスペースの次元を示し、nはツリー内のポイントの数を示し、kは特定のクエリで取得されたポイントの数を示します。範囲ツリーは、間隔ツリーで区別できます。ポイントを格納して特定の範囲内のポイントを効率的に取得できるようにする代わりに、間隔ツリーは間隔を保存し、特定のポ