I am implementing AVL tree in C++ and using unique_ptr
for children.
struct Node
{
const int key;
std::unique_ptr<Node> left, right;
std::size_t height; ///< for avl tree.
Node(const int key) : key(key), height(0) {}
};
class AVL
{
std::unique_ptr<Node> root;
public:
AVL(int rootKey) : root(std::unique_ptr<Node>(new Node(rootKey))) {
}
void insert(std::unique_ptr<Node> newNode) {
std::unique_ptr<Node> & node = root;
std::weak_ptr<Node> parentWeak;
while(node.get()) {
parentWeak = node->parent;
if (node->key == newNode->key)
throw std::runtime_error("Key already present");
if (node->key < newNode->key)
node = node->right;
else
node = node->left;
}
std::unique_ptr<Node> & parent = parentWeak.lock();
const int key = newNode->key;
if (parent == nullptr) {
// there is no root
root = std::move(newNode);
} else {
if (parent->key < newNode->key) {
assert(NULL == parent->right.get());
parent->right = std::move(newNode);
} else {
assert(NULL == parent->left.get());
parent->left = std::move(newNode);
}
}
// Now increment the height upto down.
incrementHeight(key);
// balance starting from parent upwards untill we find some dislanace in height
balance(parent, key);
}
};
I am getting compiler errors on line node = node->right;
. Which is right because it can be possible with only std::move
semantics. but that would be wrong because i want to just iterate over the tree, otherwise it would just remove them from the child-list.
However, i need the unique_ptr
also, as it would passed in function balance
as it would modify the pointers and re-balance the tree.
If i use shared_ptr
it would all work. However, i do not need to share the ownership with others. Or am i misunderstanding ownership ?
Aucun commentaire:
Enregistrer un commentaire