I am really trying to figure out the bug in my code I wrote for AVL tree but there seems to be a bug in it.
It calls the rotation functions but when it finishes rotation there are several problem:
I have been trying to fix this bug since 2-3 days but cant seem to solve it.
Would love some help from you guys. I will be attaching the code with this.
/*
insertion
rotations all DONE
level order DONE
deletion
*/
#include <iostream>
#include <queue>
using namespace std;
struct node
{
int data;
int height;
node *left;
node *right;
node()
{
height = 0;
left = right = NULL;
}
};
class AVL
{
public:
node *root;
AVL()
{
root = NULL;
}
// search function
bool search(int num)
{
node *nodePtr = root;
if (root->data == num)
{
cout << "FOUND " << endl;
return true;
}
else
{
while (nodePtr != NULL)
{
if (nodePtr->data < num)
{
nodePtr = nodePtr->right;
}
else if (nodePtr->data > num)
{
nodePtr = nodePtr->left;
}
else
{
cout << "FOUND " << endl;
return true;
}
}
cout << "NOT FOUND " << endl;
return false;
}
}
// inorder
void inorder()
{
inorder(root);
}
// postorder
void postorder()
{
postorder(root);
}
// preorder
void preorder()
{
preorder(root);
}
// inorder utility function
void inorder(node *&nodePtr)
{
if (nodePtr)
{
inorder(nodePtr->left);
cout << nodePtr->data << ", ";
inorder(nodePtr->right);
}
}
// preorder utility function
void preorder(node *&nodePtr)
{
if (nodePtr)
{
cout << nodePtr->data << ", ";
preorder(nodePtr->left);
preorder(nodePtr->right);
}
}
// postorder utility function
void postorder(node *&nodePtr)
{
if (nodePtr)
{
postorder(nodePtr->left);
postorder(nodePtr->right);
cout << nodePtr->data << ", ";
}
}
// returns the number of nodes in the tree
int size(node *&nodePtr)
{
if (!nodePtr)
{
return 0;
}
else
{
return (size(nodePtr->left) + size(nodePtr->right)) + 1;
}
}
// function to check if tree is empty or not
bool isempty()
{
if (root == NULL)
{
return true;
}
else
{
return false;
}
}
// max function to calculate height and also the balance factor
int maximum(int x, int y)
{
if (x>y)
{
return x;
}
else
{
return y;
}
}
// returns the level of the tree
int returnHeight(node *&nodePtr)
{
if (nodePtr == NULL)
{
return 0;
}
else
{
return nodePtr->height;
}
}
// assigning the height to the node
void assignHeightToNode(node *&nodePtr)
{
int left = returnHeight(nodePtr->left);
int right = returnHeight(nodePtr->right);
nodePtr->height = maximum(left, right) + 1;
}
// single left rotate
node *singleLeftRotate(node *&nodePtr)
{
// if (nodePtr==NULL)
// {
// return;
// }
node * b = nodePtr->right;
nodePtr->right = b->left;
b->left = nodePtr;
return b;
}
// single right rotate
node *singleRightRotate(node *&nodePtr)
{
// if (nodePtr==NULL)
// {
// return ;
// }
node * b = nodePtr->left;
nodePtr->left = b->right;
b->right = nodePtr;
assignHeightToNode(nodePtr);
assignHeightToNode(b);
return b;
}
// double left rotate
node *doubleLeft(node *&nodePtr)
{
nodePtr->right = singleRightRotate(nodePtr->right);
return singleLeftRotate(nodePtr);
}
// double right rotate
node *doubleRight(node *&nodePtr)
{
nodePtr->left = singleLeftRotate(nodePtr->left);
return singleRightRotate(nodePtr);
}
// insert function
void insert1(int x)
{
cout << "NOW INSERTING " << x << endl;
insert2(x, root);
}
// insert utility function
void insert2(int &x, node *&nodePtr)
{
if (nodePtr == NULL)
{
node *newNode = new node;
newNode->data = x;
newNode->height = 0;
nodePtr = newNode;
checkRotations(nodePtr, x);
return;
}
else
{
if (x < nodePtr->data)
{
cout << endl << "GOING LEFT " << endl;
insert2(x, nodePtr->left);
}
else if (x > nodePtr->data)
{
cout << endl << "GOING RIGHT " << endl;
insert2(x, nodePtr->right);
}
else if (nodePtr->data == x)
{
cout << "DUPLICATE VALUES NOT ALLOWED " << endl;
return;
}
}
checkRotations(nodePtr, x);
}
// checking if rotations needed
void checkRotations(node *&nodePtr, int &x)
{
assignHeightToNode(nodePtr);
cout << endl << endl << "HEIGHT OF " << nodePtr->data << " IS " << nodePtr->height << endl;
int bf = returnHeight(nodePtr->left) - returnHeight(nodePtr->right);
cout << endl << endl << "BALANCE FACTOR AT NODE " << nodePtr->data << " IS " << bf << endl;
if (bf < -1 || bf > 1)
{
cout << endl << endl << "ROTATION IS HAPPEENING " << endl << endl;
if (x > nodePtr->data)
{
singleLeftRotate(nodePtr);
cout << endl << "ROTATION DONE SINGLE LEFT " << endl;
return;
}
else if (x < nodePtr->data)
{
singleRightRotate(nodePtr);
cout << endl << "ROTATION DONE SINGLE RIGHT " << endl;
return;
}
else if (x < root->data && x > root->left->data)
{
doubleRight(nodePtr);
cout << endl << "ROTATION DONE DOUBLE LEFT " << endl;
return;
}
else if (x > root->data && x < root->right->data)
{
doubleLeft(nodePtr);
cout << endl << "ROTATION DONE DOUBLE LEFT " << endl;
return;
}
}
}
// level order display code
void levelOrderDisplay()
{
levelOrderDisplay2(root);
}
// level order display utility function
void levelOrderDisplay2(node *&nodePtr)
{
if (nodePtr == NULL)
{
cout << "THE TREE IS EMPTY" << endl;
return;
}
queue <node *> displayer;
displayer.push(nodePtr);
while (!displayer.empty())
{
node *currentNode = displayer.front();
cout << currentNode->data << ", ";
if (currentNode->left != NULL)
{
displayer.push(currentNode->left);
}
else if (currentNode->right != NULL)
{
displayer.push(currentNode->right);
}
displayer.pop();
}
}
void rootD()
{
cout << "root is " << root->data << endl;
}
};
int main()
{
AVL tree;
tree.insert1(3);
tree.insert1(2);
tree.insert1(1);
tree.insert1(4);
tree.insert1(5);
tree.insert1(6);
tree.insert1(7);
tree.inorder();
// tree.rootD();
// tree.levelOrderDisplay();
// tree.rootD();
return 0;
}
Really late answer, but this is what you had to do. You should set the node passed in the function equal to the temporary node made in the function. In coding language, nodePtr=b should have been the last line of the single rotate functions.
Hope this helps :)