Изменения
очепятки
Поскольку каждая внутренняя вершина имеет четырёх детей, то суммарное число листьев будет <tex>3i + 1</tex>, где <tex>i</tex> {{---}} число внутренних вершин. Поэтому достаточно доказать оценки лишь для внутренних вершин.
Каждая внутренняя вершина содержит хотя бы одну точку в соответствующем ей квадрате. Заметим, что квадраты с одного уровня не пересекаются и полностью покрывают весь исходный квадрат (в котором <tex>n</tex> точек). Значит, число внутренних вершин одного уровня не может первосходить превосходить <tex>n</tex>. Из этого следует, что всего внутренних вершин <tex>O(d \cdot n)</tex>.
При построении квадродерева наиболее длительная операция на каждом шаге {{---}} распределение точек по четвертям текущего квадрата. Таким образом, время, затрачиваемое на одну внутренню внутреннюю вершину, линейно зависит от числа точек в соответствующем ей квадрате. Как отмечалось выше, на одном уровне суммарно во всех внутренних вершинах не больше <tex>n</tex> точек, из чего следует доказываемая оценка.
}}
