jeudi 27 septembre 2018

AVL Tree implementation, error with left and right rotate

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