← Back to Proving ground

2d tree

Click anywhere on the canvas to add a point to the k-d tree, even level nodes are colored with red vertical lines, and odd level nodes are colored with blue horizontal ones. This subdivision of the space allows for O(logN) searches, O(R + √N) range queries (R + logN typically) and typically logN nearest neighbour queries (linear worst case).

Check out the working script.