A Dynamic, Self-balancing k-d Tree
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918522409451520 |
|---|---|
| author | Brown, Russell A. |
| author_facet | Brown, Russell A. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08148 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Dynamic, Self-balancing k-d Tree Brown, Russell A. Data Structures and Algorithms 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. |
| title | A Dynamic, Self-balancing k-d Tree |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.08148 |