Эффективное удаление древовидной структуры данных

Question

У меня есть древовидная структура данных:

• Корень дерева не имеет родителей и предыдущих братьев и сестер (может есть следующие братья и сестры).
• Каждый узел имеет уникального родителя.
• У каждого узла есть указатель на своих следующих и предыдущих братьев и сестер, детей и родителей.

Эта древовидная структура данных заполняется миллионами узлов. Когда я удаляю дерево, имеющее огромное количество узлов, возникает исключение переполнения стека. Структура данных работает хорошо, когда число узлов относительно мало или когда я строю в режиме выпуска.

Это деструктор узла:

    Entity::~Entity(void)
    {
        Entity* child = NULL;

        if (firstChild != NULL)
            child = firstChild->getNextSibling();

        while(child != NULL)
        {
            delete child->getPreviousSibling();
            child->setPreviousSibling(NULL);

            child = child->getNextSibling();
        }

        if (lastChild != NULL)
            delete lastChild;

        if (isRoot())
        {
            if (nextSibling != NULL)
            {
                nextSibling->setPreviousSibling(NULL);
                delete nextSibling;
            }
        }
    }

Можно реализовать нерекурсивный алгоритм для обхода дерева и удаления всех его узлов.

Не могли бы вы предложить эффективный алгоритм обхода после заказа для удаления недвоичного дерева?

Answer 1

РЕДАКТИРОВАТЬ: Пропущен бит о обратных указателей на родительский узел. Это означает, что нам не нужно вести историю пути для возврата, и мы можем покончить со стеком.

node = root;
while (node)
{
    if (node->firstChild)
    {
        next = node->firstChild;
        node->firstChild = null;
    }
    else 
    {
        next = node->nextSibling ? node->nextSibling : node->parent;
        delete node;
    }
    node = next;
}

---

Оригинальный ответ:

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

s.push(root);
while (!s.empty())
{
     node = s.pop();
     if (node->nextSibling) s.push(node->nextSibling);
     if (node->firstChild) s.push(node->firstChild);
     delete node;
}

Answer 2

Или вы можете просто увеличить размер стека.

В Windows и Visual C ++ значением по умолчанию является ничтожный 1 МБ - просто увеличьте его до 10 МБ или даже до 100 МБ - эта память на самом деле не будет выделена до тех пор, пока она вам не понадобится вы бы просто забронировали сразу (см. опцию / STACK ). Вы даже можете сделать это выборочно только для конфигурации Debug, чтобы учесть там «более толстый» стек.

Answer 3

Вот эскиз нерекурсивного решения:

• инициализировать указатель на узел корневым указателем;
• повтор
  • если у текущего узла есть сын, переходите к этому сыну;
  • else, удалить текущий узел и вернуться к его родителю, если есть;
• до тех пор, пока у текущего узла нет родителя.

Answer 4

Я бы попробовал что-то гораздо более простое, и пусть рекурсивные деструкторы выполняют свои обязанности:

Entity::~Entity(void)
{
    Entity* child = firstChild;
    while (child) {
      Entity *succ = child->getNextSibling();
      delete child;
      child = succ;
    }
}

Answer 5

Подумайте, действительно ли вам нужно ходить по дереву и обрабатывать каждый узел.

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

Answer 6

Вы можете попробовать создать статическую функцию для удаления. В предыдущих приложениях я обнаружил, что запрос большого дерева объектов для выполнения задачи может быть значительно медленнее, чем выполнение независимой функции над деревом. Статическая функция по сути глобальная, поэтому рекурсивный вызов точно знает, куда идти. Использование рекурсивного «метода» требует просмотра функции через каждый объект, что может добавить дополнительные издержки, особенно для таких операций, не связанных с кэшем. В том же духе вы, вероятно, получите лучшую производительность, если нарушите интерфейс, чтобы избежать вызова getNextSibling () для каждого объекта и полностью сохранить поток программ в одной глобальной рекурсивной функции.

Это не сама рекурсия, а то, что ваш конвейер инструкций продолжает останавливаться при доступе к данным, когда вы проходите через это дерево.