Работа с четырьмя квадрантами

Question

У меня проблемы с пониманием операции разделения квадрантов. Скажем, максимальное количество элементов, которые может удерживать узел, равно 2; когда мы добавляем третий элемент, мы создаем четыре под-узла. Вопрос в том, содержит ли родительский узел свои 2 элемента, а тот, кто вызвал переполнение, вставлен в дочерний узел или все три узла вставлены в под-узлы?

Answer 1

Все три узла вставлены в дочерний узел. Только узел листьев может хранить некоторые данные в дереве.

Это может изменить ситуацию, например, скажем, kd-tree, где пространственный раздел больше ориентирован на данные вместо фиксированного разделения пространства, что позволяет сэкономить память. С другой стороны, разделы с фиксированным пространством легче обрабатывать и даже могут быть предварительно вычислены для еще более быстрого доступа.