avl tree

[sophia]

Dear all,

The following is a simple avl tree program which i have found in my
book, now my question is how good is tha balancing method used in this
program, can any one give a general (easy to understand) algorithmic
procedure for balancing trees


/*Program for insertion in AVL tree*/

#include<stdio.h>
#include<stdlib.h>


#define FALSE 0
#define TRUE 1

typedef struct node
{
int val;
int balfact;

struct node* left;
struct node* right;

}node;


node* buildtree(node*,int,int*);
node* allocate(int);
void display(node*);
void deltree(node*);


int main(void)
{
node* avl = NULL;
int h;

avl = buildtree(avl,20,&h);
avl = buildtree(avl,6,&h);
avl = buildtree(avl,5,&h);
avl = buildtree(avl,29,&h);
avl = buildtree(avl,12,&h);
avl = buildtree(avl,25,&h);

printf("\n AVL TREE\n");
display(avl);

printf("\n checking root value %d", avl-> val);
printf("\n checking root balance value %d", avl-> balfact);

deltree(avl);

return EXIT_SUCCESS;
}

node* buildtree(node* root,int data,int *h)
{
node* n1,*n2;

if(!root)
{
root = allocate(data);
*h = TRUE;
return root;
}

if(data < root -> val)
{
root -> left = buildtree(root -> left,data,h);
/*if left sub tree is higher*/

if(*h)
{
switch(root -> balfact)
{

case -1:
root -> balfact = 0;
*h = FALSE;
break;

case 0:
root -> balfact = 1;
break;

case 1:

n1 = root -> left;

if(n1-> balfact == 1)
{
printf("\n Right rotation along %d", root -> val);
root -> left = n1 -> right;
n1 -> right = root;
root -> balfact = 0;
root = n1;
}
else
{
printf("\n Double rotation ...left along %d",n1-> val);
n2 = n1 -> right;
n1 -> right = n2 -> left;
n2 -> left = n1;
root -> left = n2 -> right;
n2 -> right = root;

if(n2 -> balfact == 1)
root -> balfact = -1;

else
root -> balfact = 0;

if(n2 -> balfact == -1)
n1 -> balfact = 1;
else
n1-> balfact = 0;

root = n2;
}

root -> balfact = 0;
*h = FALSE;
break;
}
}

}


if(data > root -> val)
{
/*if the right sub tree is higher*/
root -> right = buildtree(root -> right,data,h);

if(*h)
{

switch(root -> balfact)
{
case 0:
root -> balfact = -1;
break;

case 1:
root -> balfact = 0;
*h = FALSE;
break;
case -1:

n1 = root -> right;

if(n1 -> balfact == -1)
{
printf("\n Left rotation along %d",root -> val);
root -> right = n1 -> left;
n1 -> left = root;
root-> balfact = 0;
root = n1;
}
else
{

printf("Double rotation right along %d ", n1->
val);
n2 = n1 -> left;
n1 -> left = n2 -> right;
n2 -> right = n1;
root -> right = n2 -> left;
n2 -> left = root;

if(n2 -> balfact == -1)
root -> balfact = 1;
else
root -> balfact = 0;

if(n2 -> balfact == 1)
n1 -> balfact == -1;
else
n1 -> balfact = 0;

root = n2;
}

root ->balfact=0;
*h = FALSE;

}

}

}

return root;

}


void display(node* root)
{
if(root)
{
display(root -> left);
printf("\t %d",root -> val);
display(root -> right);
}
}


void deltree(node* root)
{
if(root)
{
deltree(root -> left);
deltree(root -> right);
}

free(root);
}


node* allocate(int val)
{
node *temp;

temp = malloc(sizeof(*temp));

if(!temp)
{
printf("\nMemory allocation failed\ngoing to exit");
exit(1);
}

temp -> val = val;
temp -> left = NULL;
temp -> right = NULL;
temp -> balfact = 0;

return temp;
}

 

[Ben Pfaff]

The following is a simple avl tree program which i have found in my
book, now my question is how good is tha balancing method used in this
program,

If your program correctly implements AVL balancing, then the
balance of the resulting tree is just as good as any other
implementation of AVL balancing. As for AVL balancing, it is
quite strict and results in efficient trees, but sometimes it can
do more work than necessary, so that a less aggressive balancing
scheme (such as red-black) can be slightly more efficient; see,
e.g.:
http://benpfaff.org/papers/libavl.pdf

can any one give a general (easy to understand) algorithmic
procedure for balancing trees

Here is one:
http://adtinfo.org/libavl.html/Balancing-a-BST.html

 

[sophia]

If your program correctly implements AVL balancing, then the
balance of the resulting tree is just as good as any other
implementation of AVL balancing. As for AVL balancing, it is
quite strict and results in efficient trees, but sometimes it can
do more work than necessary, so that a less aggressive balancing
scheme (such as red-black) can be slightly more efficient; see,
e.g.:
http://benpfaff.org/papers/libavl.pdf


Here is one:
http://adtinfo.org/libavl.html/Balancing-a-BST.html

but still u haven't said anything about the balancing method used in
this program ...?

 

[Ben Pfaff]

but still u haven't said anything about the balancing method used in
this program ...?

Sure I did. If it implements AVL balancing, then the results are
just as good as any other AVL balancing implementation. The
paper explains how good AVL balancing is in practice.