Изменения
→О размерах сжатого квадродерева
Как отмечалось в представленной выше теореме, достаточно доказать оценку <tex>O(n)</tex> для числа интересных квадратов. Докажем по индукции, что в квадродереве для <tex>n</tex> точек количество интересных квадратов меньше либо равно <tex>n</tex>:
* для <tex>n = 1</tex> это очевидно;
* пусть в квадродереве доказано для квадродерева для <tex>n > - 1</tex> точек. Рассмотрим кореньДобавим новую точку <tex>x</tex>: сначала найдём наименьший интересный квадрат <tex>p(x)</tex>, у него обязательно должно быть хотя бы 2 непустых ребёнкакоторый её содержит. Если хотя бы один из детей является точкой<tex>x</tex> находится в его пустой четверти, то остальные непустые дети являются деревьямипросто добавляем <tex>x</tex> как лист, в которых суммарно не больше изменив число интересных квадратов. Если же четверть <tex>n - 1p(x)</tex> точек (и в каждом их меньше которую необходимо вставить <tex>nx</tex>). Значит, в них суммарно не больше уже содержит точку <tex>n - 1y</tex> интересных квадратов (по индукционному предположению). Следовательно, во всём квадродереве не больше или интересный квадрат <tex>nr</tex> интересных квадратов. Если же все непустые дети корня являются интересными квадратами), то мы всё равно можем применить индукционное предположение ко всем детям и получить то же самоедобавить в дерево интересный квадрат, поскольку во всех поддеревьях который будет меньше содержать <tex>nx</tex> точек (ибо их суммарно и <tex>ny</tex> и везде есть хотя бы одна, так как дети непустые)в разных четвертях. На самом делеТаким образом, как оказалосьпри добавлении точки мы увеличиваем количество интересных квадратов не более, у корня необязательно хотя бы 2 непустых ребёнка, но для детей корня это уже верно (что у поддеревьев корень имеет хотя бы 2 непустых ребёнка), так что доказательство не портитсячем на один.
Таким образом, квадродерево для <tex>n</tex> точек имеет <tex>O(n)</tex> вершин. Глубина, очевидно, тоже <tex>O(n)</tex>, поскольку на каждом уровне есть хотя бы одна вершина (здесь под вершинами имеются в виду узлы в дереве). При этом оценки получше нет (то есть глубина <tex>\Theta(n)</tex>). На картинке в правом дереве можно на место левого нижнего красного кружка поставить опять такое дерево и так делать сколь угодно долго, получим глубину <tex>\Theta(n)</tex>.
