Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   K&R2, Binary-Tree, section 6.5 (http://www.velocityreviews.com/forums/t614295-k-and-r2-binary-tree-section-6-5-a.html)

 arnuld 05-12-2008 06:44 AM

K&R2, Binary-Tree, section 6.5

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 05-12-2008 07:49 AM

Re: K&R2, Binary-Tree, section 6.5

> 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 05-12-2008 04:17 PM

Re: K&R2, Binary-Tree, section 6.5

arnuld <sunrise@see.sigs.invalid> writes:

> 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 05-13-2008 04:13 PM

Re: K&R2, Binary-Tree, section 6.5

> 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 05-13-2008 04:15 PM

Re: K&R2, Binary-Tree, section 6.5

> 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 :)

 Ben Pfaff 05-13-2008 05:15 PM

Re: K&R2, Binary-Tree, section 6.5

arnuld <sunrise@see.sigs.invalid> writes:

>> 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 05-15-2008 05:28 AM

Re: K&R2, Binary-Tree, section 6.5

> 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 05-15-2008 03:37 PM

Re: K&R2, Binary-Tree, section 6.5

arnuld <sunrise@see.sigs.invalid> writes:

> 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

 All times are GMT. The time now is 12:07 AM.