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,2 0,&h);
avl = buildtree(avl,6 ,&h);
avl = buildtree(avl,5 ,&h);
avl = buildtree(avl,2 9,&h);
avl = buildtree(avl,1 2,&h);
avl = buildtree(avl,2 5,&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("\nMemor y allocation failed\ngoing to exit");
exit(1);
}

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

return temp;
}

[Ben Pfaff]

Re: avl tree

sophia <sophia.agnes@g mail.comwrites:

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

--
char a[]="\n .CJacehknorstu" ;int putchar(int);in t main(void){unsi gned long b[]
={0x67dffdff,0x 9aa9aa6a,0xa77f fda9,0x7da6aa6a ,0xa67f6aaa,0xa a9aa9f6,0x11f6} ,*p
=b,i=24;for(;p+ =!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)bre ak;else default:continu e;if(0)case 1:putchar(a[i&15]);break;}}}

[sophia]

Re: avl tree

On Apr 22, 1:38 pm, Ben Pfaff <b...@cs.stanfo rd.eduwrote:

sophia <sophia.ag...@g mail.comwrites:

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

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

[Ben Pfaff]

Re: avl tree

sophia <sophia.agnes@g mail.comwrites:

On Apr 22, 1:38 pm, Ben Pfaff <b...@cs.stanfo rd.eduwrote:

>sophia <sophia.ag...@g mail.comwrites:

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
>implementati on 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

>
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.
--
char a[]="\n .CJacehknorstu" ;int putchar(int);in t main(void){unsi gned long b[]
={0x67dffdff,0x 9aa9aa6a,0xa77f fda9,0x7da6aa6a ,0xa67f6aaa,0xa a9aa9f6,0x11f6} ,*p
=b,i=24;for(;p+ =!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)bre ak;else default:continu e;if(0)case 1:putchar(a[i&15]);break;}}}