K&R2, Binary-Tree, section 6.5

Discussion in 'C Programming' started by arnuld, May 12, 2008.

  1. arnuld

    arnuld Guest

    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, May 12, 2008
    #1
    1. Advertising

  2. arnuld

    arnuld Guest

    > 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 :)
     
    arnuld, May 12, 2008
    #2
    1. Advertising

  3. arnuld

    Ben Pfaff Guest

    arnuld <> 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,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)case 1:putchar(a[i&15]);break;}}}
     
    Ben Pfaff, May 12, 2008
    #3
  4. arnuld

    arnuld Guest

    > 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, May 13, 2008
    #4
  5. arnuld

    arnuld Guest

    > 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 :)
     
    arnuld, May 13, 2008
    #5
  6. arnuld

    Ben Pfaff Guest

    arnuld <> 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,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)case 1:putchar(a[i&15]);break;}}}
     
    Ben Pfaff, May 13, 2008
    #6
  7. arnuld

    arnuld Guest

    > 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 :)
     
    arnuld, May 15, 2008
    #7
  8. arnuld

    Ben Pfaff Guest

    arnuld <> 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
     
    Ben Pfaff, May 15, 2008
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,128
  2. sharan
    Replies:
    4
    Views:
    691
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    834
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    692
    CBFalconer
    Oct 30, 2007
  5. kampy
    Replies:
    9
    Views:
    336
    Steven D'Aprano
    Oct 19, 2012
Loading...

Share This Page