c++ - キーとしてint配列を使用するバイナリツリー(ユークリッド距離)?

Question

船のデータを格納する二分探索木を作成しました。検索の鍵は、船の音響署名です。

ツリーを検索するとき、正しい署名を持つ船、または検索された署名に最も近い船を返したいと思います。(どの船が最もユークリッド距離が近いかを見ることによって)。

私が抱えている問題は、実際の数値以外の署名を比較する方法です。実行される検索は、バイナリではなくシーケンシャルであることを意味しますか?

何か案は？

Answer 1

あなたがしていることは、多次元での最近傍検索に帰着します。二分木だけではこれを効率的に解決することはできません。スペース分割構造が必要になります。

配列の長さ N が小さい (1 桁) 場合、バイナリ ツリーの一般化として 2^N 分木 (quadtree、octree、...) を使用できます。

高次元でもうまく機能する一般的な選択肢はKd-treeです。