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.
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