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

K&R2, Binary-Tree, section 6.5This 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 :) |

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

Re: K&R2, Binary-Tree, section 6.5arnuld <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;}}} |

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

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

Re: K&R2, Binary-Tree, section 6.5arnuld <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;}}} |

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

Re: K&R2, Binary-Tree, section 6.5arnuld <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. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.