Изменения

Назовём квадрат '''интересным''', если соответствующая ему вершина дерева имеет хотя бы 2 непустых ребёнка (то есть таких, что в их квадратах содержится хотя бы одна точка) или является корнем. Понятно, что любой квадрат <tex>p</tex>, содержащий хотя бы две точки, содержит единственный наибольший интересный квадрат. [[Файл:Compressed Quadtree.png | 500px | thumb | Пример сжатого квадродерева (справа сжатая версия левого)]] Сжатое квадродерево получается сжатием обычного таким образом, чтобы остались только интересные квадраты. Неинтересные квадраты расщепляются, и их пустые дети удаляются. Для каждого интересного квадрата <tex>p</tex> будем хранить 4 указателя для каждой четверти этого квадрата. Если четверть содержит две или более точки, то указатель ссылается на наибольший интересный квадрат в этой четверти. Если четверть содержит одну точку, то указатель ссылается на эту точку. Наконец, если четверть не содержит точек, то указатель сделаем нулевым. == О размерах сжатого квадродерева =={{Лемма|statement=Сжатое квадродерево для <tex>n</tex> точек имеет <tex>O(n)</tex> вершин и глубину <tex>O(n)</tex>.|proof=Как отмечалось в представленной выше теореме, достаточно доказать оценку <tex>O(n)</tex> для числа внутренних вершин, каждая из которых является интересным квадратом (Кэп: то есть для числа интересных квадратов это надо доказать). Докажем по индукции, что в квадродереве для <tex>n</tex> точек количество интересных квадратов меньше <tex>n</tex>:* для <tex>n = 1</tex> это очевидно;* пусть в квадродереве <tex>n > 1</tex> точек. Рассмотрим корень, у него обязательно должно быть хотя бы 2 непустых ребёнка. Если хотя бы один из детей является точкой, то остальные непустые дети являются деревьями, в которых суммарно меньше <tex>n - 1</tex> точек. Значит, в них суммарно меньше <tex>n - 1</tex> интересных квадратов (по индукционному предположению). Следовательно, во всём квадродереве меньше <tex>n</tex> интересных квадратов. Если же все непустые дети корня являются интересными квадратами, то мы всё ранво можем применить индукционное предположение ко всем детям и получить то же самое, поскольку во всех поддеревьях будет меньше <tex>n</tex> точек (ибо их суммарно <tex>n</tex> и везде есть хотя бы одна, так как дети непустые).Таким образом, квадродерево для <tex>n</tex> точек имеет <tex>O(n)</tex> вершин. Глубина, очевидно, тоже <tex>O(n)</tex>, поскольку на каждом уровне есть хотя бы одна вершина (Кэп). При этом лучшей оценки нет (то есть глубина <tex>\theta(n)</tex>). На картинке в правом дереве можно на место левого нижнего красного кружка поставить опять такое дерево и так делать сколь угодно долго, получим высоту <tex>\theta(n)</tex>.}}