Stefan Röttger

← 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 →