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