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.


--
http://lispmachine.wordpress.com/
my email ID is @ the above blog.
just check the "About Myself" page :)

[arnuld]

On Mon, 12 May 2008 11:44:18 +0500, arnuld wrote:

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 ;) .

--
http://lispmachine.wordpress.com/
my email ID is @ the above blog.
just check the "About Myself" page :)

[Ben Pfaff]

arnuld <su*****@see.sigs.invalidwrites:

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".
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa6 7f6aaa,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)case 1:putchar(a[i&15]);break;}}}

[arnuld]

On Mon, 12 May 2008 09:17:46 -0700, Ben Pfaff wrote:

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 ?


--
http://lispmachine.wordpress.com/
my email ID is @ the above blog.
just check the "About Myself" page :)

[arnuld]

On Mon, 12 May 2008 09:17:46 -0700, Ben Pfaff wrote:

...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)case1:putchar(a[i&15]);break;}}}

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

;)
--
http://lispmachine.wordpress.com/
my email ID is @ the above blog.
just check the "About Myself" page :)

[Richard Heathfield]

arnuld said:

>On Mon, 12 May 2008 09:17:46 -0700, Ben Pfaff wrote:

>...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)case1:putchar(a[i&15]);break;}}}

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

;)

gcc is mistaken. Control does not reach the end of that function at all,
except via the return statement in line 16 (after indenting with the
canonical options, i.e. mine).

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Ben Pfaff]

arnuld <su*****@see.sigs.invalidwrites:

>On Mon, 12 May 2008 09:17:46 -0700, Ben Pfaff wrote:

>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 ?

No, because "is" has a balance factor of -2 (1 minus 3).
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa6 7f6aaa,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)case 1:putchar(a[i&15]);break;}}}

[arnuld]

On Tue, 13 May 2008 10:15:01 -0700, Ben Pfaff wrote:

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 ?
--
http://lispmachine.wordpress.com/
my email ID is @ the above blog.
just check the "About Myself" page :)

[Ben Pfaff]

arnuld <su*****@see.sigs.invalidwrites:

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.
--
"We put [the best] Assembler programmers in a little glass case in the hallway
near the Exit sign. The sign on the case says, `In case of optimization
problem, break glass.' Meanwhile, the problem solvers are busy doing their
work in languages most appropriate to the job at hand." --Richard Riehle