Unique pointers for a Binary Search Tree - Conceptual question

[VoB]

Hi everyone,

I'm coding a binary search tree. I have a question about the following struct Node, which I have seen has been implemented this way:

template <typename T>
struct Node{
 
    T data; 
    std::unique_ptr<Node<T>> left;
    std::unique_ptr<Node<T>> right;
    Node<T>* parent;
};

Here (and on lots of sites) the left and right children are a std::unique_ptr to a Node. I have some issues on "describing" this choice.

- Why should I prefer a unique pointer instead of a raw one for the children? I know that I can use only raw pointers, but I want to grasp the basic motivation of using unique pointers in this case.


For instance, if I say std::unique_ptr<Node<T>> left{my_node}; I mean that left owns a raw pointer to the node my_node and the "uniqueness" comes from the fact that left owns the object pointed to, which is the node my_node.



- Why can't be the parent a unique_ptr too? I've read somewhere that I somewhat loose the uniqueness, but I can'y figure out what this means.

Let's say I have a node with value 8, with left child 3, and the right child of 3 is 6. If each parent is a unique_ptr, then I would have (for instance) that the parent of node 6 should be a unique_prt to 3, which is already "uniquely" owned by the left child of node 8 and hence I have a conceptual conflict, in some sense.



I don't think my argument above is correct, so any help is highly appreciated!

[dhayden]

We use unique_ptr<> when the pointer "owns" the data that it points to. That means when the unique_ptr is destroyed, the data it points to gets destroyed too.

So conceptually, who owns a node in a tree? It makes sense that the parent node owns it. After all, if you destroyed the parent node, then there'd be nothing pointing to the children.

In the same way, a child's "parent" pointer does not own the parent. After all, there can be two children and they can't both own the parent. The parent is owned by it's parent.

So it's all about this concept of "ownership" and that is most easily defined as "who destroys the object."

[VoB]

Thanks for your answer. I see now the logic behind this choice.

In practice, if I erroneously say that parent is a unique_ptr, I think I will end up, somewhere in my code, in troubles.

To use the example of before, let's say that I insert a new node, 5 with key (and value) 5 in the tree of my first message. I will have to say that its parent is a unique_ptr to the node 3, which is already owned by his parent 8, something like

tmp->right.reset(new Node<pair_type> {my_key,tmp})

where tmp will be the unique_ptr that is used in insertion of a node by starting from the root and traversing the tree, pair_type is std::pair<int,int> and pair_type my_key=pair_type {5,5}, and hence I will end up with a compiler error because, by saying that the parent is the (unique_ptr) tmp, I'm copy the content of a unique_ptr

Am I right?

[VoB]

@dhayden if you don't mind, could you please give me a feedback about my last comment? I'm sorry for bothering you

[dhayden]

I don't follow your last comment so I can't give feedback.

[VoB]

I'm sorry for the confusion. I'll try to be more concise now.

My point is: I should get a compiler error if I would use a std::unique_ptr for the parent Node too, because when I will create a new node of the tree I would end up with copying a unique_ptr, which of course is forbidden.

Is this correct?

[JLBorges]

> Is this correct?

Yes. The parent node owns this node (since it holds unique pointers to its child nodes);
this node does not (cannot, should not) simultaneously try to own the parent node.

[VoB]

Thanks @JLBorges for your confirmation.