Is kd-tree always balanced?

Question

I have used kd-tree algoritham and make tree.

But i found that tree is not balanced so my question is if we used kd-tree algoritham then that tree is always balanced if not then how can we make it balance ?.

We can use another algoritham likes AVL or Red-Black for balancing kd tree ?

I have some sample data for that i used kd-tree algoritham but that tree is not balanced.

 (14,31), (15,32), (17,42), (16,44), (18,52), (16,62)

Answer 1

This is a fairly broad topic and the questions themselves are kind of general. Hopefully this will give you some useful insights and material to work with:

• Kd tree is not always balanced.
• AVL and Red-Black will not work with K-D Trees, you will have either construct some balanced variant such as K-D-B-tree or use other balancing techniques.
• K-d Tree are commonly used to store GeoSpatial data because they let you search over more then one key, contrary to 'traditional' tree which lets you do single dimensional search. GeoSpatial data certainly cannot be represented in single dimension.

Note that there are also specialized databases working with GeoSpatial data so it might be worth checking if the overhead could be shifted to them instead of making your own solution: Although i don't have much experience with this, maybe it is worth checking the postgis.

postgis

Here are some useful links showing how to build balanced K-D tree variant and usage of K-D trees with Spatial data:

balancing K-D-Tree

K-D-B-tree

spatial data k-d-trees