Quad Trees

This is Tree-Based Multi-Dimensional Index Structure

Idea:

  • for $k$-dimensional space
  • each node corresponds to a $k$-dimensional cube
  • for 2D it's a square region


Building

quad-tree-1.png

Algorithm

  • if a number of points in a cube is larger that can fit in a block
  • then we create an interior node
  • and divide the cube recursively (i.e. we create 4 children for each quadrant)
  • otherwise we create a leaf block

quad-tree-repr.png


Operations

Lookups, Insertions and Deletions are very similar to kd-Trees


See also

Sources

Machine Learning Bookcamp: Learn machine learning by doing projects. Get 40% off with code "grigorevpc".

Share your opinion