Search code examples
data-structureskdtreer-tree

What is the difference between a KD-tree and a R-tree?

I looked at the definition of KD-tree and R-tree. It seems to me that they are almost the same.

What's the difference between a KD-tree and an R-tree?

Solution

  • R-trees and kd-trees are based on similar ideas (space partitioning based on axis-aligned regions), but the key differences are:

    • Nodes in kd-trees represent separating planes, whereas nodes in R-trees represent bounding boxes.
    • kd-trees partition the whole of space into regions whereas R-trees only partition the subset of space containing the points of interest.
    • kd-trees represent a disjoint partition (points belong to only one region) whereas the regions in an R-tree may overlap.

    (There are lots of similar kinds of tree structures for partitioning space: quadtrees, BSP-trees, R*-trees, etc. etc.)