Implementing an AVL Tree

Question

I am trying to implement an AVL Tree following the guidelines from here. I been having some issues getting this to work. Currently I am getting this error in the "Right Right Case" of insert. Specifically at this line:

// Right Right Case
if (balance < -1 && theData > root->right->data)
    leftRotate(root);

The error I get is:

Exception thrown: read access violation.
root._Mypair._Myval2->right._Mypair._Myval2 was nullptr.

I would really appreciate if someone could help me fix this.

Here is my code:

#include <algorithm>
#include <iostream>
#include <memory>
#include <utility>
#include <stack>
#include <queue>

struct Node {
    int data;
    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) :
        data(x),
        height(y),
        left(std::move(p)),
        right(std::move(q)) {}

    Node(const int& data) : data(data), height(1) {}

};
std::unique_ptr<Node> root = nullptr;

int height(std::unique_ptr<Node>& root) {
    if (!root) return 0;
    return root->height;
}

void rightRotate(std::unique_ptr<Node>& y) {
    std::unique_ptr<Node> x = std::move(y->left);
    std::unique_ptr<Node> T2 = std::move(x->right);

    // Perform rotation
    x->right = std::move(y);
    x->right->left = std::move(T2);

    // Update heights
    x->right->height = std::max(height(x->right->left), height(x->right->right)) + 1;
    x->height = std::max(height(x->left), height(x->right)) + 1;
}

void leftRotate(std::unique_ptr<Node>& x) {
    std::unique_ptr<Node> y = std::move(x->right);
    std::unique_ptr<Node> T2 = std::move(y->left);

    // Perform rotation
    y->left = std::move(x);
    y->left->right = std::move(T2);

    // Update heights
    y->left->height = std::max(height(y->left->left), height(y->left->right)) + 1;
    y->height = std::max(height(y->left), height(y->right)) + 1;

}

int heightDiff(std::unique_ptr<Node>& root) {
    if (!root) return 0;

    return height(root->left) - height(root->right);
}

void insert(std::unique_ptr<Node>& root, const int& theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
    // Perform normal BST insertion
    if (root == nullptr) {
        root = std::move(newNode);
        return;
    }

    else if (theData < root->data) {
        insert(root->left, theData);
    }

    else {
        insert(root->right, theData);
    }

    // Update height of this ancestor node
    root->height = 1 + std::max(height(root->left), height(root->right));

    // Get the balance factor of this ancestor node to check whether this node became unbalanced
    int balance = heightDiff(root);

    // If this node become unbalaced, then we have 4 cases

    // Left Left Case
    if (balance > 1 && root->left && theData < root->left->data)
        rightRotate(root);

    // Right Right Case
    if (balance < -1 && root->right && theData > root->right->data)
        leftRotate(root);

    // Left Right Case
    if (balance > 1 && root->left && theData > root->left->data) {
        leftRotate(root->left);
        rightRotate(root);
    }

    // Right Left Case
    if (balance < -1 && root->right && theData < root->right->data) {
        rightRotate(root->right);
        leftRotate(root);
    }
}

auto findMin(std::unique_ptr<Node>& root) {
    while (root->left != nullptr) root = std::move(root->left);
    return root.get();
}

void deleteNode(std::unique_ptr<Node>& root, const int& theData) {
    // Step 1: Perform regular deletion for BST
    if (!root) return;
    else if (theData < root->data) deleteNode(root->left, theData);
    else if (theData > root->data) deleteNode(root->right, theData);

    else {
        // Case 1: No child
        if (root->left == nullptr && root->right == nullptr) {
            root = nullptr;
        }

        // Case 2: One child
        else if (root->left == nullptr) {
            root = std::move(root->left);
        }

        else if (root->right == nullptr) {
            root = std::move(root->right);
        }

        // Case 3: Two children
        else {
            auto temp = findMin(root->right);
            temp->data = root->data;
            deleteNode(root->right, temp->data);
        }
    }


    // Step 2: Update height of the current node
    root->height = 1 + std::max(height(root->left), height(root->right));

    // Step 3: Get the balalce factor of the this node (to 
    // check whether this node became unbalanced)
    int balance = heightDiff(root);

    // If this node becomes unbalanced, then there are 4 cases

    // Left Left Case
    if (balance > 1 && heightDiff(root->left) >= 0)
        rightRotate(root);

    // Left Right Case
    if (balance > 1 && heightDiff(root->left) < 0) {
        leftRotate(root->left);
        rightRotate(root);
    }

    // Right Right Case
    if (balance < -1 && heightDiff(root->right) <= 0)
        leftRotate(root);

    // Right Left Case
    if (balance < -1 && heightDiff(root->right) > 0) {
        rightRotate(root->right);
        leftRotate(root);
    }
}

void inorderTraversal(std::unique_ptr<Node>& root) {
    if (!root) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

void preorderTraversal(std::unique_ptr<Node>& root) {
    if (root != nullptr) {
        std::cout << root->data << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

void postorderTraversal(std::unique_ptr<Node>& root) {
    if (root != nullptr) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        std::cout << root->data << " ";
    }
}

void DFS(std::unique_ptr<Node>& root) {
    if (!root) return;

    std::stack<Node const *> s;
    s.push(root.get());

    while (!s.empty()) {
        auto p = s.top();
        s.pop();

        if (p->right != nullptr) s.push(p->right.get());
        if (p->left != nullptr) s.push(p->left.get());

        std::cout << p->data << " ";
    }
}

void BFS(std::unique_ptr<Node>& root) {
    if (!root) return;

    std::queue<Node const *> q;
    q.push(root.get());

    while (!q.empty()) {
        auto p = q.front();
        q.pop();

        if (p->left != nullptr) q.push(p->left.get());
        if (p->right != nullptr) q.push(p->right.get());

        std::cout << p->data << " ";
    }
}

bool exists(int d) {
    auto temp = root.get();
    while (temp != nullptr) {
        if (temp->data == d) {
            return true;
        }
        else {
            if (d > temp->data) {
                temp = temp->right.get();
            }
            else {
                temp = temp->left.get();
            }
        }
    }
    return false;
}

int main() {

    //        8
    //      /    \
    //    4       10
    //   / \     /  \
    //  2   6   9    12

    //insert(root, 8);
    //insert(root, 10);
    //insert(root, 4);
    //insert(root, 2);
    //insert(root, 6);
    //insert(root, 12);
    //insert(root, 9);


  /* Constructing tree given in the above figure */
    insert(root, 9);
    insert(root, 5);
    insert(root, 10);
    insert(root, 0);
    insert(root, 6);
    insert(root, 11);
    insert(root, -1);
    insert(root, 1);
    insert(root, 2);

    /* The constructed AVL Tree would be
            9
           /  \
          1    10
        /  \     \
       0    5     11
      /    /  \
     -1   2    6
    */

    printf("Preorder traversal of the constructed AVL "
        "tree is \n");
    preorderTraversal(root);

    //deleteNode(root, 10);

    /* The AVL Tree after deletion of 10
            1
           /  \
          0    9
        /     /  \
       -1    5     11
           /  \
          2    6
    */

    //printf("\nPreorder traversal after deletion of 10 \n");
    //preorderTraversal(root);

    /*inorderTraversal(root);
    std::cout << "\n";

    preorderTraversal(root);
    std::cout << "\n";

    postorderTraversal(root);
    std::cout << "\n";

    DFS(root);
    std::cout << "\n";

    BFS(root);
    std::cout << "\n";

    exists(4) ? std::cout << "Yes" << std::endl : std::cout << "No" << std::endl;*/


    std::cin.get();
}

Generally, when implementing trees, you can reduce repetition (and thus chance of copy-paste error) by replacing `std::unique_ptr left, right;` with `std::unique_ptr children[2];`, supported by `enum {LEFT_CHILD, RIGHT_CHILD};` — o11c, Sep 29 '18 at 00:22
The best advice is to use a debugger step by step and find the state of your tree and what is causing you to dereference a nullptr. — Tony Tannous, Sep 29 '18 at 00:24
The way the code is laid out leaves many opportunities for these kinds of bugs to happen. The best way to avoid bugs is to make them logically impossible. I see at least two likely causes of bugs. 1) One of `Node` constructors fails to initialize `height`. As such, any usage of it is undefined behavior. 2) Lack of error checking. Example: `leftRotate` fails to check that `x` is not null, and `y` is not null. The fact that your exception refers to a null pointer access is highly suggestive that this class of errors is your bug. Oh, and use a debugger to tell you where your code crashed. — Sam Varshavchik, Sep 29 '18 at 00:26
@SamVarshavchik Thank you for your points as for your 1) what do you suggest I do? Also for 2) are simple if(!x) or if(!y) return sufficient? — , Sep 29 '18 at 00:32
My suggestion for you is to learn how to use a debugger. Knowing how to effectively use a debugger is a required skill for every C++ developer. You say that you have isolated your error to the "the Right Right Case of insert". Excellent. Now, write down on a sheet of paper what you expect your code to do in this case. Then, fire up the debugger and step through your program, one line at a time, comparing what it's doing to what you've written down. As soon as the observable behavior diverges from the expected one, you found your bug, and its cause. Problem solved. — Sam Varshavchik, Sep 29 '18 at 00:46
@SamVarshavchik - the combination of the two comments would make a fine answer... — David C. Rankin, Sep 29 '18 at 02:15
@SamVarshavchik I appreciate the suggestions, I just haven't learned how to debug that effectively yet, was just hoping someone could spot the error. — , Sep 29 '18 at 02:28
x->right = std::move(y); y->left = std::move(T2); In the first statement, y doesn't own a object. so it's invalid to use y->left. — Andy Chang, Sep 29 '18 at 03:20
Since y is used throughout the function, I suggest to use variables to keep height of each node and move std::move (perform rotation) to the end of function. — Andy Chang, Sep 29 '18 at 05:44
Is there any reason why you cannot use a debugger? Read [how to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Basile Starynkevitch, Sep 29 '18 at 06:06
Possible duplicate of [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Raedwald, Sep 29 '18 at 07:18

score 0 · Accepted Answer · answered Sep 30 '18 at 05:25

I noticed that you have fixed std::move() issue. But you may need to add the following lines into your program.

void rightRotate(std::unique_ptr<Node>& y) {
    ....
    x->height = std::max(height(x->left), height(x->right)) + 1;
    y = std::move(x);
}

void leftRotate(std::unique_ptr<Node>& x) {
    ...
    y->height = std::max(height(y->left), height(y->right)) + 1;
    x = std::move(y);
}

Implementing an AVL Tree

1 Answers1

Linked