kd-tree
| This article is a stub. You can help RoboWiki by expanding it. |
In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbour searches). kd-trees are a special case of BSP trees.
In Robocode, a kd-tree is a data structure use for k-nearest neighbours searching in Dynamic Clustering data logging algorithms. Currently, the most popular type of kd-tree in Robocode is the Bucket PR kd-tree.
How it works?
Please complete this section if you can (about real kd-tree, not bucket PR kd-tree)
Bucket PR kd-tree
Bucket PR kd-trees have two characteristics:
- Bucket means points are collected in leaves until they overflow. Only then are they split. This makes the tree more likely to be balanced since we can choose a smarter splitting point than whatever we receive first.
- PR stands for Point-Region. The tree recursively splits its region into two equally-sized areas, regardless of the position of the actual data, until buckets no longer overflow. This is more likely to retain balance if the data is evenly distributed since the final tree does not depend on the order of the data. If the data is closely clustered, however, this can result in an excessively deep tree.
For an applet demo, see Spatial Index Demos. The example there cycles partitioning axes in a fixed order, while most authors use a more intelligent algorithm. Rednaxela's kd-tree, for example, splits on the widest dimension.
Implementations
There are several implementation of kd-tree around today, and most if not all of them are bucket PR kd-trees:
- Rednaxela's kd-tree: The fastest and most efficient kd-tree around today.
- Voidious's kd-tree: The second-to-top tree.
- Chase's KD-TreeC: A fair tree and the only one that includes range searching.
- Simonton's kd-tree: The first bucket PR kd-tree in Robocode community.
