For my current algorithms class I am working on a program that demonstrates the power of k-D trees, but before I implement any new data structure or algorithm I have to completely understand how it works. So, I created an animation that shows how a k-D tree is constructed. Later I will create an animation explaining the nearest neighbor search of a k-D tree.

A k-D tree is similar to a binary tree except that it can be used to search over k dimensions. Each level of the tree represents an alternating dimension, when traversing the tree the portion of the point represented by by the levels dimension is evaluated.

To keep things simple the example below only shows two dimensions; it is easier to expand the data structure, once you understand it, than it is to expand the example.

Comments (newest first)

Nice animation. It helps a lot in understanding kd-Tree behavior.

Tags: Blogger Data Structures Animation

Published: 2011-09-25