Removing element from balanced KD-Tree of two dimensions

Question

I want to remove a element from balanced KD-Tree and Tree remain balance without rebuilding the whole tree. is this possible to balance tree without rebuilding the whole tree ? if yes then how?

Answer 1

For the standard k-d tree, you can remove items but there is no re-balancing, so if you remove almost all the items you might just end up with a long thin unbalanced tree. Do you care? The tree doesn't actually get any deeper: it is unbalanced, but because it was balanced when it was created it should never be outrageously deep.

If deleting is all you care about, you could rebuild the tree from scratch when you have deleted half the items - this will mean that it never gets outrageously out of balance. Also, you could consider marking items as deleted instead of actually removing them, this can make some things easier.

This is a special case of making data structures dynamic, or dynamization. At the cost of a factor of log n you can make data structures that you know how to rebuild, but not balance, dynamic, to cope with inserts as well as deletes. The basic idea is to build the dynamic data-structure as a collection of non-dynamic structures with wildly varying sizes, such as powers of two: most changes lead you to rebuild only one or two of the smaller non-dynamic structures, but at longer intervals you will have to take time out to rebuild the larger ones. A very loose example of this would be keeping daily records in a loose leaf notebook and using them to update a filing cabinet overnight. See for example http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2009/GDS/slides/S12.pdf or http://www.mpi-inf.mpg.de/~mehlhorn/ftp/mehlhorn27.pdf.