I have implemented a binary search tree in c++. Instead of using bare pointers to point to a nodes children I used the std::shared_ptr. The nodes of the tree are implemented as follows
struct treeNode;
typedef std::shared_ptr<treeNode> pTreeNode;
struct treeNode {
T key;
pTreeNode left;
pTreeNode right;
treeNode(T key) : key(key), left(nullptr), right(nullptr) {}
};
When removing a node from the BST, one of the cases is when the node has only one child. The node is simply replaced by this child as shown below:
| remove node
node ---------> |
\ right
right
In an similar Java implementation this can be coded as:
node = node.getRight();
In my C++ implementation it is:
node = node->right;
where node is of type pTreeNode.
When calling the = operator on an pTreeNode (std::shared_ptr<TreeNode>), node's destructor will be called. The number of shared pointers pointing to the underlying TreeNode is 1, hence the TreeNode is destroyed freeing its memory. When the TreeNode (default) destructor is called, each of its members are destroyed. This surely would result in the pTreeNode right member being destroyed. The problem is that node->right is what is being assigned to node. When testing my BST, it appears to work fine with no errors/memory leaks.
- Is what I am doing unsafe?
- If it is unsafe, what could I do to get around this problem?
A 'hack' that i figured may work would be to make another pointer to increase its reference count. Would this be an adequate solution?
//increase reference to node->right by 1 so it doesn't get destroyed
pTreeNode temp(node->right);
node = node->right;
Aucun commentaire:
Enregistrer un commentaire