誰能告訴我KD-tree和R-tree有什麼區別

Question

我看KD-tree和R-tree的定義，看起來它們差不多。

誰能告訴我KD-tree和R-tree有什麼區別？感謝

Answer 1

R-trees和kd-trees基於類似想法（基於軸對齊區域空間分割），但是關鍵的差異是：

• 節點在ķ d樹表示分離平面，而節點在R樹中表示邊界框。
• k d-trees將整個空間劃分爲區域，而R-樹只劃分包含感興趣點的空間子集。
• k d-trees表示不相交的分區（點只屬於一個區域），而R樹中的區域可能重疊。

（有很多相似種的樹結構的用於劃分空間：四叉樹，BSP樹，R * - 樹，等等，等等）

Answer 2

兩者之間的主要區別不被提及加雷里斯是Kd樹只在批量加載情況下才有效。一旦構建，修改或重新平衡Kd樹是非平凡的。 R樹不會因此受到影響。

Answer 3

它們實際上完全不同。它們的用途相似（對空間數據的區域查詢），它們都是樹木，但這是關於它們所有的共同點。

• R-樹木是均衡，KD-樹不是（除非批量加載）。這就是爲什麼R樹可以用來改變數據的原因，因爲kd樹可能需要重建以重新優化。
• R-Trees是面向磁盤。他們實際上將數據組織在直接映射到磁盤表示的區域中。這使它們在真實數據庫和內存不足操作中更有用。 kd-trees是面向內存的並且是不平凡的放入磁盤頁面
• R樹不覆蓋整個數據空間。空的區域可能被揭露。 kd-trees總是覆蓋整個空間。
• kd-trees 二進制拆分數據空間，r-trees將數據分區爲矩形。二元分裂顯然是不相交的;雖然r-tree的矩形可能會重疊（實際上有時很好，儘管試圖使重疊最小化）
• kd-trees在內存中實現起來要容易得多，這實際上是它們的關鍵優點
• R-樹可以存儲矩形和多邊形，kd-trees只存儲點向量（因爲多邊形需要重疊）
• R樹帶有各種優化策略，不同的分割，批量加載器，插入和重新插入策略等。