samedi 5 novembre 2022

unique_ptr unexpectedly deletes after function return?

I am currently trying to implement a binary search tree/AVL tree in C++, and trying to learn and understand smart pointers. I have tried to use unique_ptr as the children of a node, and as root, in the binary search tree. Everything seems to work quite fine, except, that, with a testcase, it seems that, but insert function keeps deleting the parent pointer. And I cannot seem to understand why.

Now, My code is definetly not the best, I can already say, but my primary goal right now is trying to understand these smart pointers.

So, the testcase. is making a binary search tree. inserting 5, 1, 2, and 6. When inserting 6, this is where it deletes the parent pointer?? I have given the code for the functions that run during this testcase. Therefore, all the rotations functions are not included, since they are never called.

TestCase

TreeNode<T>* insert(TreeNode<T>* src, const T& data) {
    if (src == NULL) {
        return new TreeNode<T>(data);
    }

    if (data < src->data) {
        TreeNode<T>* tempLeft = NULL;
        deep_copy_tree(&tempLeft, src->leftChild);
        src->leftChild = unique_ptr<TreeNode<T>>(insert(tempLeft, data));
        src->leftChild->parent = src;
    }
    else {
        TreeNode<T>* tempRight = src->rightChild.get();
        deep_copy_tree(&tempRight, src->rightChild);
        src->rightChild = unique_ptr<TreeNode<T>>(insert(tempRight, data));
        src->rightChild->parent = src;
    }

    // balance
    return balance(src);
}

TreeNode<T>* balance(TreeNode<T>* node) {
    if (maxDepth() < 2) {
        return node;
    }
    int balance;
    if (node->leftChild == NULL && node->rightChild == NULL) {
        balance = 0;
    }
    else if (node->leftChild == NULL) {
        TreeNode<T>* tempRight = NULL;
        deep_copy_tree(&tempRight, node->rightChild);
        balance = node->maxDepth(tempRight) + 1;
    }
    else if (node->rightChild == NULL) {
        TreeNode<T>* tempLeft = node->leftChild.get();
        deep_copy_tree(&tempLeft, node->leftChild);
        balance = -1 - node->maxDepth(tempLeft);
    }
    else {
        TreeNode<T>* tempLeft = NULL;
        deep_copy_tree(&tempLeft, node->leftChild);
        TreeNode<T>* tempRight = NULL;
        deep_copy_tree(&tempRight, node->rightChild);
        balance = node->maxDepth(tempRight) - node->maxDepth(tempLeft);
    }

    if (balance == -2) {
        TreeNode<T>* tempLeft = NULL;
        deep_copy_tree(&tempLeft, node->leftChild);
        if (tempLeft != NULL && tempLeft->balanceFactor() <= 0) {
            return leftLeftCase(node);
        }
        else {
            return leftRightCase(node);
        }
    }
    else if (balance == 2) {
        TreeNode<T>* tempRight = NULL;
        deep_copy_tree(&tempRight, node->rightChild);
        if (tempRight != NULL && tempRight->balanceFactor() >= 0) {
            return rightRightCase(node);
        }
        else {
            return rightLeftCase(node);
        }
    }

    return node;
}

int maxDepth(TreeNode<T>* node) {
    if (node->leftChild == nullptr && node->rightChild == nullptr) {
        return 0;
    }

    int max = 1;
    if (node->leftChild != nullptr && node->rightChild != nullptr) {
        max += std::max(maxDepth(node->leftChild.get()), maxDepth(node->rightChild.get()));
    }
    else if (node->leftChild != nullptr) {
        max += maxDepth(node->leftChild.get());
    }
    else {
        max += maxDepth(node->rightChild.get());
    }
    return max;
}

template <typename T>
class TreeNode {
public:
T data;
unique_ptr<TreeNode<T>> leftChild;
unique_ptr<TreeNode<T>> rightChild;
TreeNode<T>* parent;
}

template <typename T>
class BinarySearchTree {
private:
unique_ptr<TreeNode<T>> root;
}

Aucun commentaire:

Enregistrer un commentaire