K&R2, Binary-Tree, section 6.5

[arnuld]

This is the code form section 6.5 of K&R2:


struct tnode
{
char *word;
int count;
struct tnode *left;
struct tnode *right;
};


struct tnode *add_node( struct tnode *p, char *w )
{
int cond;

if ( !p )
{
p = talloc();
p->word = strdup( w );
p->count = 1;
p->left = p->right = NULL;
}
else if( !(cond = strcmp( w, p->word )) )
{
p->count++;
}
else if( cond < 0 )
{
p->left = add_node( p->left, w );
}
else if( cond > 0 )
{
p->right = add_node( p->right, w );
}

return p;
}



/* aloocate memory for new node */
struct tnode *talloc( void )
{
return malloc( sizeof( struct tnode ) );
}


for input:

"Now is the time for all good men to come to the aid
of their party"

This produces a tree like this:


now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come



This is an unbalanced-tree, where balanced factor is:

(1 - 3) = -2

balance factor = (height of right-subtree) - (height of left-subtree)

right-subtree starts with word "the" which has only 1 child-node.
left-subtree starts with "is" and it has 3 nodes

Can I convert this binary-tree into an AVL tree which has a balance factor
of 1, 0 or -1 ? I am not able to change the code to do that
conversion.

 

[arnuld]

This is the code form section 6.5 of K&R2:

...SNIP...
This produces a tree like this:


now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come

..SNIP..

eh... I don't understand why the tree is not looking like the way I typed.
Si I type again:


now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come



BTW, most folks have K&R2 already. Though Ben Bacarisse has K&R only .

 

[Ben Pfaff]

now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come



This is an unbalanced-tree, where balanced factor is:

(1 - 3) = -2

balance factor = (height of right-subtree) - (height of left-subtree)

I don't see how you get a balance factor of -2 from that tree. I
see a balance factor of -1:

now
/ \
^ is the ^
| / \ / \ |
height | for men of time | height
4 | / \ \ / \ | 3
| all good party their to V
| / \
V aid come

The right child of "now" has height 3. The left child of "now"
has height 4. The difference is -1.

right-subtree starts with word "the" which has only 1 child-node.

"the" has two children: "of" and "time".

left-subtree starts with "is" and it has 3 nodes

"is" also has two children: "for" and "men".

 

[arnuld]

I don't see how you get a balance factor of -2 from that tree. I
see a balance factor of -1:

now
/ \
^ is the ^
| / \ / \ |
height | for men of time | height
4 | / \ \ / \ | 3
| all good party their to V
| / \
V aid come

The right child of "now" has height 3. The left child of "now"
has height 4. The difference is -1.

I thought you don't count the nodes with single-child but I was wrong.
Now it has a balance factor of -1 but cab I call it an AVL tree ?

 

[arnuld]

...SNIP...

char a[]="\n .CJacehknorstu";int putchar(int);int main(void)
{unsignedlong b[]={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,
0xa67f6aaa,0xaa9aa9f6,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)break;else
default:continue;if(0)case1utchar(a[i&15]);break;}}}

gcc -ansi -pedantic -Wall -Wextra test.c
: In function `main':
: warning: control reaches end of non-void function

 

[Ben Pfaff]

I thought you don't count the nodes with single-child but I was wrong.
Now it has a balance factor of -1 but cab I call it an AVL tree ?

No, because "is" has a balance factor of -2 (1 minus 3).

 

[arnuld]

now
/ \
^ is the ^
| / \ / \ |
height | for men of time | height
4 | / \ \ / \ | 3
| all good party their to V
| / \
V aid come

No, because "is" has a balance factor of -2 (1 minus 3).

Oh... Now I got it, every node ( whether child or root) in AVL tree must
have a balance factor of -1,0 or 1.

right ?

 

[Ben Pfaff]

Oh... Now I got it, every node ( whether child or root) in AVL tree must
have a balance factor of -1,0 or 1.

right ?

Correct.