У меня проблемы с пониманием операции разделения дерева квадрантов. Скажем, максимальное количество элементов, которые может содержать узел, равно 2; когда мы добавляем третий элемент, мы создаем четыре подузла. Вопрос в том, сохраняет ли родительский узел свои 2 элемента, а тот, который вызвал переполнение, вставляется в дочерний узел или все три узла вставляются в подузлы?
Операция разделения дерева квадрантов
Ответы (1)
Все три узла вставляются в дочерний узел. Только узел листьев может содержать некоторые данные в дереве.
Это может иметь значение, например, для kd-tree, где пространственный раздел больше ориентирован на данные, а не на фиксированные разделы пространства, что позволяет экономить память. С другой стороны, разделы с фиксированным пространством проще в обращении и даже могут быть предварительно вычислены для еще более быстрого доступа.
person
sansuiso
schedule
25.10.2013
Спасибо! Но что содержит родительский узел, если все три вставлены вниз по дереву?
- person mrk; 26.10.2013
Родительский узел (как и любой промежуточный узел) содержит указатели (или эквивалент) на своих 4 дочерних элементах. Вы знаете, что можете получить доступ к данным, когда узел больше не является дочерним.
- person sansuiso; 26.10.2013
Фактически, в статье Википедии о деревьях квадрантов есть псевдокод, который использует внутренние узлы для хранения. Когда узел переполняется, элемент переполнения вставляется в подузел.
- person mrk; 26.10.2013
Что произойдет, если есть узел, содержащий 2 больших круга, и я добавлю 3-й большой? Узел разбивается на 4 дочерних элемента, и все теперь 3 круга могут пересекаться с дочерними элементами, поэтому все они добавляются к каждому дочернему элементу. Но каждый ребенок должен разделиться, так как они могут удерживать только 2 круга, и цикл продолжается до бесконечности. Что не так с моим пониманием?
- person ColOfAbRiX; 09.07.2015
