Why does my insert function, in a C implementation of an AVL tree, fails to rotate the nodes with unbalance factor?
Here is my code:
// AVL Tree Implementation
typedef struct Node{
int key;
struct Node *left;
struct Node *right;
int height;
int balanceFactor;
}node;
int max(int a, int b);
int getHeight(node *n);
int getBalanceFactor(node *n);
void insert(node **n, int key);
void rotateLeft(node **n);
void rotateRight(node **n);
// Traversal
// In-Order Traversal
// Pre-Order Traversal
InOrder(node *n){
if (n != NULL){
InOrder(n->left);
printf("%d ", n->key);
InOrder(n->right);
}
}
define MAX_SIZE 6
int main(){
node *root = NULL;
int a[MAX_SIZE] = {10,9,8,7,6,5};
int i;
printf("\n\nInserting items in the Tree...\n\n");
for(i = 0; i < MAX_SIZE; i++){
printf("\nInserted: %d",a[i]);
insert(&root, a[i]);
}
printf("\n\nElements in the Tree: ");
InOrder(root);
printf("\n\n");
}
int max(int a, int b){
return (a > b)? a : b;
}
/* Get the height of a Node */
int getHeight(node *n){
if(n == NULL)
return 0;
return n->height;
}
/* Get the Balance Factor of a Node */
int getBalanceFactor(node *n){
if(n == NULL)
return 0;
return (getHeight(n->left)-getHeight(n->right));
}
Insert Function, Rotate Left and Rotate Right
void insert(node **n, int key){
if(*n == NULL){
/* Create a New Node */
*n = (node*)malloc(sizeof(node));
if(*n != NULL){
(*n)->key = key;
(*n)->left = (*n)->right = NULL;
(*n)->height = 0;
return;
} else {
printf("\nError: Memory Allocation Fail");
return;
}
}
if (key < (*n)->key){
insert(&((*n)->left), key);
}else{
insert(&((*n)->right), key);
}
(*n)->height = max(getHeight((*n)->left), getHeight((*n)->right)) + 1;
printf("\nHeight of %d is updated to %d",(*n)->key, (*n)->height);
if(getBalanceFactor(*n) > 1){
if(getBalanceFactor((*n)->left) < 0)
rotateLeft(&(*n));
rotateRight(&(*n));
}
else if(getBalanceFactor(*n) < -1){
if(getBalanceFactor((*n)->right) > 0)
rotateRight(&(*n));
rotateLeft(&(*n));
}
}
void rotateRight(node **n){
node *lChild, *subtree;
lChild = (*n)->left;
subtree = lChild->right;
// Rotate Right
printf("\nRotating Right");
lChild->right = *n;
(*n)->left = subtree;
// Update Height
lChild->height = max(getHeight(lChild->left), getHeight(lChild->right)) + 1;
(*n)->height = max(getHeight((*n)->left), getHeight((*n)->right)) + 1;
}
void rotateLeft(node **n){
node *rChild, *subtree;
rChild = (*n)->right;
subtree = rChild->left;
// Rotate Left
printf("\nRotating Left");
rChild->left = *n;
(*n)->right = subtree;
// Update Height
rChild->height = max(getHeight(rChild->left), getHeight(rChild->right)) + 1;
(*n)->height = max(getHeight((*n)->left), getHeight((*n)->right)) + 1;
}
I have fixed this code.
Here is the link: Pastebin