Здравствуйте, Hоmunculus, Вы писали:


Можно попробовать как-то так. Массив узлов + массив указателей.

struct Node {
    std::vector<size_t> children;
    // ... другие данные узла
};

class Tree {
private:
    std::vector<Node> nodes;           // Все узлы хранятся здесь
    std::vector<size_t> free_ids;      // Список свободных ID
    size_t next_id = 0;
    
public:
    // Создание узла возвращает ID
    size_t createNode() {
        size_t id;
        if (!free_ids.empty()) {
            id = free_ids.back();
            free_ids.pop_back();
        } else {
            id = next_id++;
            if (id >= nodes.size()) {
                nodes.resize(id + 1);
            }
        }
        return id;
    }
    
    // Доступ за O(1)
    Node& getNode(size_t id) {
        return nodes[id];
    }
    
    void deleteNode(size_t id) {
        // Очищаем узел
        nodes[id].children.clear();
        // Добавляем ID в список свободных
        free_ids.push_back(id);
    }