Использование сырых указателей в узлах и unique_ptr в деревьях - PullRequest
Новая
       18

Использование сырых указателей в узлах и unique_ptr в деревьях

0 голосов
/ 19 марта 2019

Я программист-любитель, пытаюсь найти подходящее место, чтобы поместить unique_ptr в мое двоичное дерево.Первоначально я использовал unique_ptr для левого и правого потомков, но это «означало», что каждый узел «владел» каждым последующим узлом.Мне было сказано в предыдущем посте , что дерево должно владеть своими узлами.Это мое решение проблемы: все узлы деревьев хранятся в векторе уникальных указателей, а unique_ptr::get используется для извлечения необработанных указателей, которые используются обычным образом (пример добавления). 

#include "pch.h"
#include <iostream>
#include <sstream>
#include <string>
#include <memory>
#include <vector>
#include <unordered_map>

class Node
{
public:
    Node(int data = 0) : data_(data), left_child(nullptr), 
        right_child(nullptr) {}

    int data_;
    Node *left_child;
    Node *right_child;
};

class Tree
{
public:
    Tree(int data = 0) {
        store.emplace_back(std::make_unique<Node>(data));
        root = store.at(0).get();
    }
    void add(int data) {
        Node *index = root;
        while (true) {
            if (data == index->data_) {
                std::stringstream ss;
                ss << data << " already exists\n";
                throw std::invalid_argument(ss.str());
            }
            if (data < index->data_) {
                if (index->left_child != nullptr) {
                    index = index->left_child;
                    continue;
                }
                std::unique_ptr<Node> temp = std::make_unique<Node>(data);
                index->left_child = temp.get();
                store.push_back(std::move(temp));
                return;
            }
            if (index->right_child != nullptr) {
                index = index->right_child;
                continue;
            }
            std::unique_ptr<Node> temp = std::make_unique<Node>(data);
            index->right_child = temp.get();
            store.push_back(std::move(temp));
            return;
        }
    }
private:
    std::vector<std::unique_ptr<Node>> store;
    Node* root;
};

Удаление узла кажется болезненно медленным.Найдите значение в дереве (быстро), найдите указатель в std::vector (медленно), удалите запись из вектора и, наконец, обрежьте указатель от родителя.Я на правильном пути?Если нет, подсказки будут приветствоваться.

Ответы [ 2 ]

1 голос
/ 19 марта 2019

Использование std :: unique_ptr для детей - это быстрое и грязное решение, но оно не соответствует требованию вопроса.Помещать указатели в вектор - плохая идея из-за сложного кода и сложности времени.

Быстрое и грязное решение - написать функцию в дереве, которая будет рекурсивно удалять узлы.Недостатком является потенциальное переполнение стека, если дерево не сбалансировано (как и в случае с std::unique_ptr для дочерних элементов).Существует несколько способов борьбы с потенциальным переполнением стека:

Эффективное решение, которое не имеет переполнения стека и не может исключить std::bad_alloc.Это алгоритм DFS, использующий в качестве стека освобожденные узлы дерева.Запись Node :: left будет указывать на полезную нагрузку (поддерево, которое нужно освободить), а Node :: right будет играть роль next в стеке DFS (связанный список). 

static Node * & nextNode(Node & node)
{ return node.right_child; }
static Node * & payload(Node & node)
{ return node.left_child; } 

Tree::~Tree()
{
    Node temp;
    Node *stack = & temp;
    payload(*stack) = root;
    nextNode(*stack) = nullptr;
    constexpr bool TRACE = false;

    while (stack) {
        Node * treeNode = payload(*stack);
        Node * toPush1 = treeNode->left_child;
        Node * toPush2 = treeNode->right_child;
        if (toPush1) {
            payload(*stack) = toPush1;
            if (toPush2) {
                payload(*treeNode) = toPush2;
                nextNode(*treeNode) = stack;
                stack = treeNode;
            } else {
                if (TRACE) std::cout << treeNode->data_ << " ";
                delete treeNode;
            }
        }
        else if (toPush2) {
            payload(*stack) = toPush2;
            if (TRACE) std::cout << treeNode->data_ << " ";
            delete treeNode;
        }
        else { // nothing to push 
            Node *nextStack = nextNode(*stack);
            if (TRACE) std::cout << treeNode->data_ << " ";
            delete treeNode;
            if (stack != &temp) {
                if (TRACE) std::cout << stack->data_ << " ";
                delete stack;
            }
            stack = nextStack;
        }
    }
    // free the stack.
    while (stack) {
        Node *nextStack = nextNode(*stack);
        if (stack != &temp) {
            if (TRACE) std::cout << stack->data_ << " ";
            delete stack;
        }
        stack = nextStack;
    }
    if (TRACE) std::cout << '\n';
}

Это позволит вам эффективно использовать память, с O (1) дополнительной памятью, и экономить время, с O (N) сложностью по времени.

Для полноты, вот остаток класса Tree: 

class Tree
{
public:
    Tree(int data = 0) {
        root = new Node(data);
    }
    ~Tree();
    Copy ctor, assignment, move ctor, move assignment

    void add(int data) {
        Node *index = root;
        while (true) {
            if (data == index->data_) {
                std::stringstream ss;
                ss << data << " already exists\n";
                throw std::invalid_argument(ss.str());
            }
            if (data < index->data_) {
                if (index->left_child != nullptr) {
                    index = index->left_child;
                    continue;
                }
                std::unique_ptr<Node> temp = std::make_unique<Node>(data);
                index->left_child = temp.release();

                return;
            }
            if (index->right_child != nullptr) {
                index = index->right_child;
                continue;
            }
            std::unique_ptr<Node> temp = std::make_unique<Node>(data);
            index->right_child = temp.release();

            return;
        }
    }
private:
    // owning the root and all descendants recursively
    Node* root;
};
0 голосов
/ 19 марта 2019

Конечно, плохая идея иметь vector всех выделенных узлов в вашем Tree классе.Как вы указали, манипулирование им для поиска и удаления Node является медленным (то есть линейно зависит от размера вашего дерева) и уменьшает все преимущества, которые должно иметь ваше дерево.

Первое предложение будетиспользовать std::unique_ptr<Node> для ваших left_child и right_child членов вашего Node.Тогда вам не понадобится vector для хранения всех узлов.

Но в вашей конкретной реализации этого недостаточно: вы ничего не делаете для уравновешивания дерева, поэтому в худшем случае его глубина будет расти линейно,следовательно, рекурсивная очистка не удастся (переполнение стека).Вам понадобится гибридная итеративно-рекурсивная очистка.

Но вы можете сделать это в качестве следующего шага.Первый шаг - просто избавьтесь от vector.

...