Kd ツリーを実装して、C++ で最近傍検索と近似最近傍検索を実行しようとしています。これまでのところ、最も基本的な Kd ツリーの 2 つのバージョンに遭遇しました。
それらは基本的に同じように見え、同じ漸近特性を持っています。
私の質問は次のとおりです。どちらかを選択する理由はありますか?
これまでのところ、2つの理由を考えました。
delete data葉だけにデータを格納するツリーは機能を実装しやすいどちらを作成するかを決定する前に、考慮すべき他の理由はありますか?
ノードを削除済みとしてマークし、構造上の変更を次のツリー再構築に延期することができます。kd-treesは時間の経過とともに劣化するため、ツリーを頻繁に再構築する必要があります。kd-treesは、変更されない低次元のデータセット、または（ほぼ）最適なツリーを簡単に再構築できる場所に最適です。
ツリーの実装に関しては、最小限の構造を使用することをお勧めします。私は通常ノードを使用しません。データオブジェクト参照の配列を使用します。軸は現在の検索深度によって定義され、どこにも保存する必要はありません。左隣と右隣は、配列の二分探索木によって与えられます。byte（それ以外の場合は、使用した軸を格納するために、データセットの半分のサイズの配列を追加するだけです）。ツリーのロードは、専用のクイックソートによって行われます。理論的にはO(n^2)最悪のケースですが、中央値5などの優れたヒューリスティックを使用するO(n log n)と、非常に確実に、最小限の一定のオーバーヘッドで取得できます。
C / C ++にはそれほど当てはまりませんが、他の多くの言語では、多くのオブジェクトを管理するためにかなりの代償を払うことになります。Atype*[]は、最も安価なデータ構造であり、特に多くの管理作業を必要としません。要素を削除済みとしてマークするには、nullそれを実行し、に遭遇したときに両側を検索することができますnull。挿入の場合、最初にそれらをバッファーに収集します。そして、変更カウンターがしきい値に達したら、再構築します。
そして、それが全体のポイントです。ツリーの再構築が本当に安価である場合（ほぼ事前にソートされた配列を使用するのと同じくらい安価です！）、ツリーを頻繁に再構築しても害はありません。短い「挿入リスト」の線形スキャンは、CPUキャッシュに非常に適しています。sをスキップnullすることも非常に安いです。
より動的な構造が必要な場合は、R*ツリーを確認することをお勧めします。実際には、挿入と削除のバランスを取り、データをディスク指向のブロック構造に編成するように設計されています。しかし、Rツリーの場合でも、構造変更を延期するために挿入バッファーなどを保持することでパフォーマンスが向上するという報告があります。また、多くの状況での一括読み込みも大いに役立ちます。