Итеративный findMin () в бинарном дереве поиска реализован с помощью unique_ptr

Question

Я реализовал BST, используя обычный unique_ptr:

class BinarySearchTree
{
public:
struct Node {
    Node(int k)
    {
        key = k;
        left = nullptr;
        right = nullptr;
    }
    int key;
    // This will auto-destroy all child nodes when this Node is destroyed
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};

BinarySearchTree():
      m_root(nullptr)
    , m_depth(0)
{}

void deleteKey(int key)
{
    deleteKeyRec(key, m_root);
}

void deleteKeyRec(int key, std::unique_ptr<Node>& node)
{
    if (key == node->key) {
        // This node needs to be deleted and replaced with one of its children
        if (node->left == nullptr && node->right == nullptr) {
            // Node to be deleted has no children
            node = nullptr;
        }
        else if (node->left != nullptr && node->right == nullptr) {
            // Only left child present
            node = std::move(node->left);
        }
        else if (node->left == nullptr && node->right != nullptr) {
            // Only right child present
            node = std::move(node->right);
        }
        else {
            // Both children present, find minimum node in left subtree and replace
            auto minNode = findMin(node->left);
            node->key = minNode->key;
            deleteKeyRec(minNode->key, minNode);                
        }
    }
    else if (key < node->key) {
        deleteKeyRec(key, node->left);
    }
    else if (key > node->key) {
        deleteKeyRec(key, node->right);
    }
}

std::unique_ptr<Node> findMin(std::unique_ptr<Node> & node)
{
    Node *current = node.get();
    while (current->left) {
        current = current->left.get();
    }
    return std::make_unique<Node>(current);
}

private:
    std::unique_ptr<Node> m_root;   // Clean-up all children when this object is destroyed
    int m_depth;

};

Я пытаюсь реализовать findMin () итеративно, чтобы он возвращал unique_ptr &, поэтому я могу использовать его в deleteKeyRe c ( ) удалить минимальный узел. Но, похоже, я не могу вернуть unique_ptr & из findMin (). Есть ли другой способ реализовать findMin () итеративно?

Указанная ошибка c от MSV C находится в этой строке в findMin (): return std :: make_unique (current);

Ошибка C2664 «BinarySearchTree :: Node :: Node (BinarySearchTree :: Node &&)»: невозможно преобразовать аргумент 1 из «BinarySearchTree :: Node *» в «int»

Кажется, я не должен делать новый unique_ptr с использованием текущего узла *. Но тогда как мне перебрать дерево?

---

Модифицированный код с логами c для последнего встроенного регистра:

void deleteKeyRec(int key, std::unique_ptr<Node>& node)
{
    if (key == node->key) {
        // This node needs to be deleted and replaced with one of its children
        if (node->left == nullptr && node->right == nullptr) {
            // Node to be deleted has no children
            node = nullptr;
        }
        else if (node->left != nullptr && node->right == nullptr) {
            // Only left child present
            node = std::move(node->left);
        }
        else if (node->left == nullptr && node->right != nullptr) {
            // Only right child present
            node = std::move(node->right);
        }
        else {
            // Both children present, find minimum node in right subtree and replace 'node'
            Node *owner = nullptr;         // stays one step behind current after first iteration
            Node *current = node->right.get();
            while (current->left.get()) {
                owner = current;
                current = current->left.get();
            }

            //auto minNode = findMin(node->left.get());
            node->key = current->key;      // transfer the key here, we do not free the memory of this node.
            if (owner == nullptr) {
                // The right node of 'node' is the correct replacement as it has no children
                node->right = nullptr;  // delete the node from which key was copied
            }
            else {
                // A left node was found when traversing the right subtree of 'node', so that node's owner now will have no left child!
                // This left child thats being deleted has already had its key copied to 'node' via 'current'
                owner->left = nullptr;   // delete the node from which key was copied
            }
        }
    }
    else if (key < node->key) {
        deleteKeyRec(key, node->left);
    }
    else if (key > node->key) {
        deleteKeyRec(key, node->right);
    }
}

Answer 1

Функция find должна возвращать ссылку / указатель / итератор найденному элементу. Он вообще не должен возвращать владеющий указатель. Точно так же он не должен принимать указатель-владелец в качестве аргумента. Вместо этого он должен передать ссылку / указатель / итератор на узел.

Каждый объект / узел должен принадлежать ровно одному std::unique_ptr. Поэтому, если вы не намереваетесь удалить найденный узел из дерева, вы не должны возвращать его как std::unique_ptr.

Например:

Node& findMin(const Node& node)
{
    Node *current = node.get();
    while (current->left) {
        current = current->left.get();
    }
    return *current;
}

---

У вас та же проблема с deleteKeyRec. Аргумент не должен быть std::unique_ptr.