Kd-Tree Median Insertion

kd-Tree Insertion | | Kd-Tree Deletion

Assumption of evenly distributed points does not hold all the time.

  • if all points are available upfont as a list
    • a balanced tree can be enforced by
      • inserting the median point along the according axis.
      • and repeat the insertion recursively for the left and right remainders of the list.

Example of median insertion of German PLZs:

  • maximum tree depth: 29
  • average path length: 16.0333

Compared to unbalanced insertion of German PLZs:

  • maximum tree depth: 76
  • average path length: 43.85

performance increase: balanced version about 3 times faster

kd-Tree Insertion | | Kd-Tree Deletion