使用int數組作爲鍵的二叉樹（歐幾里德距離）？

已經編寫了一個在船上存儲數據的二叉搜索樹，搜索的關鍵是它們的聲學特徵。使用int數組作爲鍵的二叉樹（歐幾里德距離）？

當搜索樹時，我想返回具有正確簽名的船舶或與搜索到的簽名最匹配的船舶。（通過查看哪艘船具有最接近的歐幾里德距離）。

我遇到的問題是如何比較其實際數值以外的簽名。那麼這意味着任何搜索都是順序的而不是二進制的？

任何想法？

2012-05-05 lex

假設您在形成樹時選擇了一些排序方案，並且您最終得到了簽名A作爲節點A的密鑰，並且簽名B用於節點B的密鑰，其中A ely

這就是我遇到的問題，我不能看到一種解決方法，只能在數據上使用二進制搜索/ is /在樹和順序搜索（如果你計算每個歐幾里德距離），如果它不是樹。 – lex

問題是，二叉搜索樹假定節點的排序在創建樹時是固定的，並且稍後將不會在樹中索引/查找內容時更改。如果您希望能夠使用不斷變化的排序搜索元素，那麼這不是您正確的數據結構，並且來自變量查詢簽名的歐幾里得距離將被視爲變化排序。當查詢改變時，存儲數據的順序改變。你需要一個結構來最大限度地減少你爲改變訂單而付出的代價。下面的答案提出了Kd樹，這似乎是合理的。 – ely

你在做什麼可以在多維空間下降到nearest-neighbour search。只有二叉樹纔能有效地解決這個問題;你需要一些空間分區結構。

如果您的數組長度N很小（單個數字），則可以使用2^N元樹（四叉樹，八叉樹...）作爲二叉樹的泛化。

一個流行的選擇，也適用於更高的尺寸是Kd-tree。

來源

2012-05-05 20:48:01 Thomas

使用int數組作爲鍵的二叉樹（歐幾里德距離）？

回答

相關問題