# R-Tree

## Intro

Similar to B-Tree, R-Tree is also a balanced search tree.

Search algorithms such at intersection, containment, nearest neighbor are still similar to other tree structures.

The major difficulty is how to build a balanced R-Tree. We definitely want the tree to be balanced but each node (rectangle) should not cover too much empty space and rectangles within it should not overlap too much.

## Insertion

Recursively search to the root level, insert, if full, split, then recursively insert & split to the root level.

## Reference

Wikipedia [R-tree](https://en.wikipedia.org/wiki/R-tree)