Изменения

Обычное квадродерево может иметь слишком большую глубину независимо от количества точек. Сжатое дерево лишено данного недостатка, имеет глубину <tex>O(n)</tex>, и на его основе строится [[Skip quadtree: определение, время работы | Skip Quadtree]].

Назовём квадрат '''интересным''', если соответствующая ему вершина дерева имеет хотя бы 2 непустых ребёнка (то есть таких, что в их квадратах содержится хотя бы одна точка) или является корнем. Понятно, что любой квадрат <tex>p</tex>, содержащий хотя бы две точки, содержит единственный наибольший интересный квадрат.

[[Файл:Compressed Quadtree.png | 500px | thumb | Пример сжатого квадродерева (справа сжатая версия левого)]]