A Dynamic, Self-balancing k-d Tree
For developers of spatial data structures, this provides a practical solution for dynamic k-d tree maintenance, though it is an incremental improvement over static approaches.
The paper presents insertion, deletion, and rebalancing algorithms for a dynamic, self-balancing k-d tree, addressing the challenge that standard rebalancing techniques violate k-d tree invariants. Performance measurements show the algorithms are effective.
The original description of the k-d tree recognized that rebalancing techniques, used for building an AVL or red-black tree, are not applicable to a k-d tree, because these techniques involve cyclic exchange of tree nodes that violates the invariant of the k-d tree. For this reason, a static, balanced k-d tree is often built from all of the k-dimensional data en masse. However, it is possible to build a dynamic k-d tree that self-balances when necessary after insertion or deletion of each k-dimensional datum. This article describes insertion, deletion, and rebalancing algorithms for a dynamic, self-balancing k-d tree, and measures their performance.