I am rewritting some data structures and I have not done this one before so I am pretty new with AVL trees. Following the link here I tried to implement the insert function.
Although, I get an error for the left and right rotate function. For example in the right rotate function the line where I perform the rotation, my compiler flags this line: y->left = std::move(T2);
with an error:
binary '=': no operator found which takes a right-hand operand of type '_Ty
*' (or there is no acceptable conversion)
I am not sure how to fix this issue. Here is my code:
#include <algorithm>
#include <iostream>
#include <memory>
#include <utility>
struct Node {
int key;
int height;
std::unique_ptr<Node> left = nullptr;
std::unique_ptr<Node> right = nullptr;
Node(const int& x, const int& y, std::unique_ptr<Node>&& p = nullptr, std::unique_ptr<Node>&& q = nullptr) :
key(x),
height(y),
left(std::move(p)),
right(std::move(q)) {}
};
std::unique_ptr<Node> root = nullptr;
int getDepth(std::unique_ptr<Node>& root) {
if (!root) return 0;
else {
int l = getDepth(root->left);
int r = getDepth(root->right);
return std::max(l, r) + 1;
}
}
void rightRotate(std::unique_ptr<Node>& y) {
auto x = y->left.get();
auto T2 = x->right.get();
// Perform rotation
x->right = std::move(y);
y->left = std::move(T2);
// Update heights
y->height = std::max(getDepth(y->left), getDepth(y->right));
x->height = std::max(getDepth(x->left), getDepth(x->right));
}
void leftRotate(std::unique_ptr<Node>& x) {
auto y = x->right.get();
auto T2 = y->left.get();
// Perform rotation
y->left = std::move(x);
x->right = std::move(T2);
// Update heights
x->height = std::max(getDepth(x->left), getDepth(x->right));
y->height = std::max(getDepth(y->left), getDepth(y->right));
}
int getBalance(std::unique_ptr<Node>& root) {
if (!root) return 0;
return getDepth(root->left) - getDepth(root->right);
}
void insert(std::unique_ptr<Node>& root, int key) {
std::unique_ptr<Node> newNode = std::make_unique<Node>(key);
// Perform normal BST insertion
if (root == nullptr) {
root = std::move(newNode);
return;
}
else if (key < root->key) {
insert(root->left, key);
}
else {
insert(root->right, key);
}
// Update height of this ancestor node
root->height = std::max(getDepth(root->left), getDepth(root->right));
// Get the balance factor of this ancestor node to check whether this node became unbalanced
int balance = getBalance(root);
// If this node become unbalaced, then we have 4 cases
// Left Left Case
if (balance > 1 && key < root->left->key)
rightRotate(root);
// Right Right Case
if (balance < -1 && key > root->right->key)
leftRotate(root);
// Left Right Case
if (balance > 1 && key > root->left->key) {
leftRotate(root->left);
rightRotate(root);
}
// Right Left Case
if (balance < -1 && key < root->right->key) {
rightRotate(root->right);
leftRotate(root);
}
}
void preorderTraversal(std::unique_ptr<Node>& root) {
if (root != nullptr) {
std::cout << root->key << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
int main() {
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
insert(root, 10);
insert(root, 20);
insert(root, 30);
insert(root, 40);
insert(root, 50);
insert(root, 25);
preorderTraversal(root);
}
Aucun commentaire:
Enregistrer un commentaire