Как вы можете очистить четырехъядерное дерево без рекурсии (возможно, используя очередь?)

Хорошо, учитывая класс в соответствии с

class quadTree {
 short level;
 Vec2f midpoint;
 quadTree * nodes[4] = { NULL, NULL, NULL, NULL};

public:

void newPartition() {
 float j = fWIDTH  / 2 ^ level;
 float k = fHEIGHT / 2 ^ level;
  nodes[0] = new quadTree(level+1, midpoint[0] - j, midpoint[0] + k);
  nodes[1] = new quadTree(level+1, midpoint[0] + j, midpoint[0] + k);
  nodes[2] = new quadTree(level+1, midpoint[0] - j, midpoint[0] - k);
  nodes[3] = new qaudTree(level+1, midpoint[0] + j, midpoint[0] - k);
 }
}

Как я могу реализовать функцию, которая удаляет все узлы под текущим узлом дерева квадрантов без рекурсии, возможно, с использованием очереди? Как в функции Clear().

Извините за вопрос, я чувствую, что должен это знать, но просто не могу понять. Я посмотрел в Интернете, но ничего не нашел. Есть идеи?

Для любого примера кода, использующего очередь, просто используйте std::queue.

РЕДАКТИРОВАТЬ :: Хорошо, я думаю, что это то, что я собираюсь использовать для справки. Я думаю, что это должно работать, поправьте меня, если я ошибаюсь.

#include <queue>
void helpClear( bool notPassing, queue<quadTree> &q ) {
int count;
for ( int i; i < 4; i++ ) {
 if ( node[i] != NULL){
  q.push ( node[i] );
  count++;
 }
}
quadTree * Point;
if ( notPassing ){
 for ( int i; i < count; i++ ){  
  Point = q.front();
  q.pop();
  Point -> helpClear(0, q);   
}
 for ( int i; i < 4; i ++ )
   delete nodes[i]; 
}
}

void clear () {
  queue <quadTree> q;
  quadTree * Point;
  helpClear(1,q);
  while (!queue.empty() ) {
    quadTree * Point;
    Point = q.front();
    q.pop();
    Point -> helpClear(1,q);
    delete Point;
  }
for ( int i; i < 4; i++ )
    nodes[i] = NULL;
}

helpClear() — это частная функция quadTree, а clear() — это общедоступная функция, которую вы вызываете для удаления всех узлов ниже текущего узла.


c++ queue algorithm tree quadtree
person PhobicHD    schedule 13.06.2013    source источник
comment
Хотя избегать рекурсии, как правило, неплохая идея, я почти уверен, что это хороший случай, но избегать рекурсии - не ВСЕГДА хорошая идея. - в этом случае рекурсия будет НАМНОГО проще, чем складывание объектов для удаления в очередь и последующее удаление очереди.   -  person Mats Petersson    schedule 13.06.2013
comment
Я имею дело с массивными четырехъядерными деревьями и большим объемом данных, которые могут создавать различные нагрузки на стек. Я говорю о размере, что, если я просто рекурсивно вызову их деконструкторы, я могу вызвать ошибку seg. Вы знаете, как я могу это сделать?   -  person PhobicHD    schedule 13.06.2013
comment
Это кажется странным, поскольку вся суть дерева квадрантов в том, что уровней не так много, что делает рекурсию довольно поверхностной.   -  person Mats Petersson    schedule 13.06.2013
comment
Point = q.front(); q.pop(); может быть просто Point = q.pop();. И вообще предпочтительным способом сделать это было бы засунуть его в деструктор (который все еще рекурсивен, но это вряд ли будет проблемой — глубина 10000 не должна быть проблемой для рекурсии, а значит, для несколько сбалансированного дерева, больше узлов, чем может когда-либо уместиться в памяти (мои расчеты показывают 5*10^3624 узлов)). А имена классов вообще начинаются с заглавной буквы - QuadTree.   -  person Bernhard Barker    schedule 13.06.2013
comment
Вы делаете предположение, что единственное, что есть в стеке этой программы, — это дерево квадрантов, что не соответствует действительности. Также вы не можете заменить Point = q.front(); q.поп(); только с Point = q.pop(); cplusplus.com/reference/queue/queue/pop не со стандартным: :очередь. И да, я знаю, что они это делают, но я всегда заканчиваю тем, что даю им первые слова в нижнем регистре, а затем слова в верхнем регистре. Это привычка.   -  person PhobicHD    schedule 13.06.2013
comment
Пожалуйста, не редактируйте (отвечено) или (альтернативные методы приветствуются) в своем заголовке; название не для этого.   -  person George Stocker    schedule 14.06.2013
comment
@PhobicHD - Вы стремитесь к быстрому удалению структуры или низкому потреблению памяти?   -  person Nick    schedule 05.04.2014

Ответы (3)


arrow_upward
0
arrow_downward

Есть две идеи (подхода):

1) Если вы можете контролировать все newPartition()-действия в одной точке (например, на верхнем уровне), то можно реализовать специальный буфер quadTree указателей и собрать в него все узлы (любые из std list, vector, queue, .. .).

В этом случае, когда вам нужно очистить все узлы, вы можете просто очистить все дочерние узлы по указателям в этом буфере, не используя стек.

2) Если в вашем QuadTree используется строгий порядок узлов (в пространственном смысле), вы можете организовать все свои указатели в одном контейнере. Например:

Уровень 0 (1 указатель):

1111
1111
1111
1111

Уровень 1 (4 указателя)

2233
2233
4455
4455

Уровень 2 (16 баллов)

ABEF
CDGH
IJMN
KLOP

В контейнере порядок будет таким:

12345ABCDEFGHIJKLOP

Отношения между уровнями могут быть решены с помощью математических вычислений, поскольку для каждого уровня требуется ровно 2 ^ N элементов.

Это решение не требует дополнительных указателей (и вообще 0 указателей) и решает вашу проблему со стеком. Однако для перехода от родителя к дочернему и от дочернего к родительскому требуется больше времени, и он может потреблять больше памяти, если ваши уровни в QuadTree отличаются (по количеству элементов в одном из, например, менее 2 ^ N).

Примечание: это очень редкий тип решения, и в большинстве случаев рекурсивное лучше.

person Boris    schedule 13.06.2013
comment
Еще одно хорошее решение, но я хотел бы сделать это как можно более легким в памяти. Спасибо, я действительно думал об этом и, вероятно, прибегну к этому, если сдамся. - person PhobicHD; 13.06.2013
comment
Ок, так намного понятнее, спасибо. Я думал, вы хотели иметь двойную ссылку: одну в дереве квадрантов, а другую в этой таблице. - person PhobicHD; 13.06.2013
comment
это индекс Мортона, также называемый индексом z-порядка, см. мой ответ. базы данных используют этот трюк. - person AlexWien; 14.06.2013

arrow_upward
0
arrow_downward

Некоторые приложения могут использовать дерево квадрантов, которое преобразуется в массив с ключом «Индекс Мортона». Такое квадродерево представляет собой огромный массив без каких-либо дочерних указателей. Вы можете удалить это так же просто, как удалить массив.

Однако не все приложения могут использовать этот MortonIndexed Quadtree.

Но рекурсия не должна быть проблемой, потому что дерево квадрантов не должно иметь глубину более 16. Если намного глубже, то вы используете неправильный тип дерева квадрантов.

person AlexWien    schedule 13.06.2013

arrow_upward
-1
arrow_downward

Я использую собственную реализацию дерева, чтобы избежать рекурсии. В моей реализации узел содержит указатель на родительский узел, дочерний узел и узел Next Plain (глубина одного уровня). Используя эти данные, легко реализовать нерекурсивную итерацию дерева.

person YurG    schedule 13.06.2013
comment
Это жизнеспособное решение, но почему тогда я просто не выделяю огромную очередь из кучи и не помещаю каждый узел в очередь? Это, вероятно, было бы более эффективным, чем сохранение до 17 дополнительных указателей узлов на узел (если я понимаю, что вы подразумеваете под следующей равниной). Тем не менее, я мог бы сократить это до одного узла для родителя и использовать то, что я уже написал. Однако все это интенсивно использует память, и у меня нет свободной памяти, вот в чем проблема. - person PhobicHD; 13.06.2013