Kd樹：只存儲在樹葉中的數據vs存儲在樹葉和節點中

Question

我想實現一個Kd樹來執行C++中最近鄰和近似最近鄰搜索。到目前爲止，我遇到了最基本的Kd樹的兩個版本。

1. 的一個，其中數據存儲在節點和枝葉，如here
2. 的一個，其中的數據只存儲在葉子，如here

他們似乎根本相同，具有相同的漸近性質。

我的問題是：有一些理由相互選擇一個嗎？

我想有兩個原因至今：

1. 存儲在節點的數據也爲1級淺的樹。
2. 僅在樹葉中存儲數據的樹有更容易實現 功能delete data

我還應該考慮一些其他的原因，決定讓哪一個過嗎？

Answer 1

您可以將標記節點刪除，並推遲對下一次樹重建的任何結構更改。 k-d-trees會隨着時間的推移而降低，因此您需要頻繁進行樹重建。 k-d-trees非常適合不變的低維數據集，或者可以輕鬆負擔重建（近似）最優樹的地方。

至於樹的實現，我推薦使用簡約結構。我通常做而不是使用節點。我使用數據對象引用的數組。軸由當前搜索深度定義，無需將其存儲在任何地方。左和右鄰居由數組的二叉查找樹給出。 （否則，只需添加一個byte的數組，其大小爲數據集的一半，用於存儲您使用的軸）。加載樹是由專門的QuickSort完成的。理論上它最壞的情況是O(n^2)，但如果啓發式很好，例如5位數的中位數，那麼您可以非常可靠地獲得O(n log n)，並且具有最小的持續開銷。

儘管它對C/C++沒有太多的支持，但在許多其他語言中，您將爲管理很多對象付出相當大的代價。 A type*[]是您可以找到的最便宜的數據結構，尤其是它不需要很多管理工作。要將某個元素標記爲已刪除，您可以使用它null，並在遇到null時搜索雙方。對於插入，我首先將它們收集在緩衝區中。當修改計數器達到閾值時，重建。

而這就是它的重點：如果你的樹的重建非常便宜（就像求助一個幾乎預排序的數組一樣便宜！），那麼它不會經常重建樹。 通過簡短的「插入列表」進行線性掃描非常適合CPU緩存。跳過null s也很便宜。

如果你想要一個更加動態的結構，我推薦看看R * - 樹。實際上，它們希望能夠平衡插入和刪除，並將數據組織在面向磁盤的塊結構中。但是即使對於R樹，也有報道說保持插入緩衝區等來推遲結構改變會提高性能。而且在許多情況下批量加載也有很大幫助！