Comparison of Different Data Structures

• k-d trees are very easy to implement. However, in general a k-d tree containing k nodes may have height k, which causes the complexity of both insertion and search in k-d trees to be high. In practice, path lengths(root to leaf) in k-d trees tend to be longer than those in point quadtree because these trees are binary trees(as opposite to potentially having four children, as in case of point quadtree)
• R-trees have large number of rectangles potentially stored in each node, they are appropriate for disk access by reducing the height of the tree, thus leading to fewer disk access.
• One disadvantage of R-trees is that the bounding rectangle associated with different nodes may overlap. Thus when searching an R-tree, instead of following one path(as in case of quadtree), we might follow multiple path down the tree. This distinction grows even more acute when range search and neighbor searches are considered.
• In case of point quadtrees, while performing search/insertion each comparison requires comparisons on two coordinates, not just one. Deletion in point quadtree is difficult because finding a candidate replacement node for the node being deleted is often difficult.