2 Attachment(s)
AVL left & right rotation
Hey fellow programmers. I am creating and implementing a left and a right rotation to balance a bst into an avl tree. I have made and tried 5 different codes that are commented in the functions left_rotate() and right_rotate() but none have run correctly. Sometimes the program works, sometimes there is a segmentation fault and sometimes not all inserted numbers are shown. Can you guys help me with this?
avl.c
Code:
#include<stdio.h>#include<stdlib.h>
#include<time.h>
#include "avl.h"
#define N 10
void swap(int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}
main(){
avl_node *root = NULL;
int i, a[N];
for(i = 0; i < N; i++){
a[i] = i+1;
}
//randomize
srand(time(NULL));
for(i = 0; i < N; i++){
swap(&a[i], &a[rand()%N]);
}
for(i = 0; i < N; i++){
insert_value(&root, a[i]);
view(root, 0);
printf("--------------Inserted %i--------------\n", a[i]);
getc(stdin);
}
}
avl.h
Code:
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 10
#define BALANCED 0
#define LEFT_LEANING 1
#define RIGHT_LEANING 2
typedef struct node_tag{
int x, height;
struct node_tag *parent;
struct node_tag *left;
struct node_tag *right;
}avl_node;
int max(int a, int b){ return(a>b?a:b);}
void updateheight(avl_node *temp){
if(temp!=NULL)
temp->height = max(temp->left==NULL?-1:temp->left->height,
temp->right==NULL?-1:temp->right->height)+1;
}
//implement left rotate right rotate functions
void left_rotate(avl_node **temp){
/*
avl_node *temp2;
(*temp)->right=(*temp)->parent;
(*temp)->parent=temp2->parent;
temp2->parent=(*temp)->left;
*/
/*
avl_node *temp2=malloc(sizeof(avl_node *));
temp2 = (*temp)->left;
(*temp)->left = temp2->right;
temp2->right = (*temp);
(*temp) = temp2;
*/
/*
avl_node *t = (*temp)->right;
(*temp)->right = t->left;
t->left = (*temp);
(*temp) = t;
*/
/*
avl_node *k1;
k1=(*temp)->left;
(*temp)->left=k1->right;
k1->right=(*temp);
(*temp)=k1;
*/
/*
avl_node *t = (*temp);
(*temp)=t->right;
t->right = (*temp)->left;
(*temp)->left = t;
updateheight(t);
updateheight(*temp);
*/
}
void *right_rotate(avl_node **temp){
/*
avl_node *temp2;
(*temp)->left=(*temp)->parent;
(*temp)->parent=temp2->parent;
temp2->parent=(*temp)->right;
*/
/*
avl_node *temp2=malloc(sizeof(avl_node *));
temp2 = (*temp)->right;
(*temp)->right = temp2->left;
temp2->left = (*temp);
(*temp) = temp2;
*/
/*
avl_node *t = (*temp)->left;
(*temp)->left = t->right;
t->right = (*temp);
(*temp) = t;
*/
/*
avl_node *k1;
k1=(*temp)->right;
(*temp)->right=k1->left;
k1->left=(*temp);
(*temp)=k1;
*/
/*
avl_node *t = (*temp);
(*temp)=t->left;
t->left = (*temp)->right;
(*temp)->right = t;
updateheight(t);
updateheight(*temp);
*/
}
void insert_fixup(avl_node **rootptr, avl_node *temp){
int current=BALANCED, previous, lh, rh;
//call left rotate right rotate functions
do{
lh = (temp->left == NULL?-1:temp->left->height);
rh = (temp->right == NULL?-1:temp->right->height);
previous = current;
current = (lh==rh?BALANCED:(lh>rh?LEFT_LEANING:RIGHT_LEANING));
if(abs(lh-rh)>1){ //anomaly or violation found!
if(current==LEFT_LEANING){
if(previous==LEFT_LEANING)
right_rotate(&temp);
else{
left_rotate(&(temp->left));
right_rotate(&temp);
}
}
else{
if(previous==RIGHT_LEANING)
left_rotate(&temp);
else{
right_rotate(&(temp->right));
left_rotate(&temp);
}
}
}//endif anomaly found
updateheight(temp);
if(temp->parent == NULL) //if root is reached
*rootptr=temp; //update root in main
temp=temp->parent; //move up
}while(temp!=NULL);
}
void insert_node(avl_node **rootptr, avl_node *temp){
avl_node *temp2 = (*rootptr);
avl_node *y = NULL;
temp->left = NULL;
temp->right = NULL;
//temp->x = x;
// Add your code here
while (temp2!=NULL){
y=temp2;
if (temp->x < temp2->x)
temp2= temp2->left;
else temp2 = temp2->right;
}
temp->parent=y;
if (y==NULL)
(*rootptr)=temp;
else if (temp->x < y->x)
y->left =temp;
else y->right =temp;
}
void insert_value(avl_node **rootptr, int x){
avl_node *temp;
temp = (avl_node *) malloc(sizeof(avl_node));
temp->x = x;
temp->parent = temp->left = temp->right = NULL;
insert_node(rootptr, temp);
insert_fixup(rootptr, temp);
}
void view(avl_node *root, int tabs){
int i;
if(root != NULL){
view(root->right, tabs+1);
for(i = 0; i < tabs; i++) printf("\t");
printf("%2i\n", root->x);
view(root->left, tabs+1);
}
}