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();
}
