A Binary Tree in C

Discussion in 'C Programming' started by arnuld, Aug 4, 2009.

  1. arnuld

    arnuld Guest

    A Binary Search Tree implemented in C. Any advice on how to complete the
    one remained function ?


    /* A Binary tree learned from "The Practice of Programming", section
    2.8 . Its a little bit different though. It also includes the
    * count of each element added into the tree. Currentlly it supports 3
    functions: adding an element, printing and free()ing the whole
    * tree. Only one fucntion, the deletion of a single element, have
    remained.
    *
    *
    * VERSION 0.0
    *
    */


    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    enum { SIZE_NAME = 30 };


    /* One disadvantage of using char [] as a struct memeber is the size of
    name is limited. but if we use char* there will be no limit
    on the size then. */
    struct namev
    {
    char name[SIZE_NAME];
    int cnt;
    struct namev* left;
    struct namev* right;
    };


    struct namev* tree_add_name(struct namev*, char* );
    void tree_free(struct namev* );
    void tree_print(struct namev* );
    struct namev* tree_delete_name(struct namev*, char*);



    int main(void)
    {
    struct namev* root = NULL;

    root = tree_add_name(root, "comp.lang.c");
    root = tree_add_name(root, "comp.lang.c++");
    root = tree_add_name(root, "comp.lang.lisp");
    root = tree_add_name(root, "comp.unix.programmer");
    root = tree_add_name(root, "comp.unix.programmer");
    root = tree_add_name(root, "comp.lang.c");
    root = tree_add_name(root, "comp.lang.");


    tree_print(root);

    return 0;
    }


    struct namev* tree_add_name(struct namev* r, char* name)
    {
    int cmp;

    if(NULL == name)
    {
    fprintf(stderr, "FILE: %s, LINE: %d : No name provided\n",
    __FILE__, __LINE__);
    return r;
    }


    if(NULL == r) /* We got a new element */
    {
    r = malloc(1 * sizeof *r);
    if(NULL == r)
    {
    fprintf(stderr,"FILE: %s, LINE: %d : malloc() failed\n",
    __FILE__, __LINE__);
    return NULL;
    }
    strcpy(r->name, name);
    r->cnt = 1;
    r->left = r->right = NULL;
    }
    else if(0 == (cmp = strcmp(name, r->name)))
    {
    r->cnt++;
    }
    else if(cmp < 0)
    {
    r->left = tree_add_name(r->left, name);
    }
    else
    {
    r->right = tree_add_name(r->right, name);
    }

    return r;
    }



    void tree_free(struct namev* r)
    {
    if(r)
    {
    tree_free(r->left);
    tree_free(r->right);
    tree_free(r);

    r = NULL;
    }
    }


    void tree_print(struct namev* r)
    {
    if(r)
    {
    tree_print(r->left);
    printf("name = %s, count = %d\n", r->name, r->cnt);
    /* how can I keep those printed elements properly aligned ? */
    tree_print(r->right);
    }
    }



    struct namev* tree_delete_name(struct namev* e, char* c)
    {
    int cmp;

    if(NULL == e || NULL == c)
    {
    fprintf(stderr, "FILE: %s, LINE: %d: NUL arguments\n", __FILE__,
    __LINE__);
    return e;
    }
    else if(0 == (cmp = strcmp(c, e->name)))
    {
    /* How can keep the pointers/left-right intact after free()ing
    this ?
    or I am just dealing with a theoretical problem. Practically, we
    never remove a single element from a tree ?? */
    }
    else if(cmp < 0)
    {
    tree_delete_name(e->left, c);
    }
    else
    {
    tree_delete_name(e->right, c);
    }

    return e;
    }


    =================== OUTPUT ==========================
    [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra binary-tree.c
    [arnuld@dune programs]$ ./a.out
    name = comp.lang., count = 1
    name = comp.lang.c, count = 2
    name = comp.lang.c++, count = 1
    name = comp.lang.lisp, count = 1
    name = comp.unix.programmer, count = 2
    [arnuld@dune programs]$










    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Aug 4, 2009
    #1
    1. Advertising

  2. arnuld <> writes:

    > A Binary Search Tree implemented in C. Any advice on how to complete the
    > one remained function ?


    <snip>
    > enum { SIZE_NAME = 30 };
    >
    >
    > /* One disadvantage of using char [] as a struct memeber is the size of
    > name is limited. but if we use char* there will be no limit
    > on the size then. */


    Yes, I'm not a fan of fixed-size arrays for string, but they are
    simple.

    > struct namev
    > {
    > char name[SIZE_NAME];
    > int cnt;
    > struct namev* left;
    > struct namev* right;
    > };


    <snip>
    > void tree_print(struct namev* r)
    > {
    > if(r)
    > {
    > tree_print(r->left);
    > printf("name = %s, count = %d\n", r->name, r->cnt);
    > /* how can I keep those printed elements properly aligned ? */


    You can't -- not without finding the longest string first and using
    that as a field width. try %20s or %-20s for the moment and see if
    that is what you want.

    > tree_print(r->right);
    > }
    > }
    >
    >
    >
    > struct namev* tree_delete_name(struct namev* e, char* c)
    > {
    > int cmp;
    >
    > if(NULL == e || NULL == c)
    > {
    > fprintf(stderr, "FILE: %s, LINE: %d: NUL arguments\n", __FILE__,
    > __LINE__);
    > return e;
    > }
    > else if(0 == (cmp = strcmp(c, e->name)))
    > {
    > /* How can keep the pointers/left-right intact after free()ing
    > this ?
    > or I am just dealing with a theoretical problem. Practically, we
    > never remove a single element from a tree ?? */


    If e->left and e->right are both NULL you can delete and return NULL.
    if only one of them is non-null you can return that pointer but what
    do you do if both are non-null? One strategy (that you can use in the
    other cases as well, BTW) is to set e->cnt to zero. Provided that
    your print and any future "find" function ignore strings with zero
    count, it will all work.

    The usual alternatives are to write a balanced tree, or to store
    strings only in leaf nodes.

    > }
    > else if(cmp < 0)
    > {
    > tree_delete_name(e->left, c);


    You have to write:

    e->left = tree_delete_name(e->left, c);

    or the tree is not modified.

    > }
    > else
    > {
    > tree_delete_name(e->right, c);


    and again here.

    > }
    >
    > return e;
    > }


    <snip>
    --
    Ben.
     
    Ben Bacarisse, Aug 4, 2009
    #2
    1. Advertising

  3. On 4 Aug, 12:25, arnuld <> wrote:

    > void tree_free(struct namev* r)
    > {
    >   if(r)
    >     {
    >       tree_free(r->left);
    >       tree_free(r->right);
    >       tree_free(r);
    >
    >       r = NULL;
    >     }
    >
    > }


    this looks odd. Suppose you have a tree with only a single node in it.

    &r = 7777;
    r->left = 0;
    r->right = 0;

    now call tree_free(&r) a trace looks like this

    tree_free (777)
    tree_free (0)
    tree_free (0)
    tree_free (777) oops!

    I think you should have freed a node rather than a tree
     
    Nick Keighley, Aug 4, 2009
    #3
  4. "Ben Bacarisse" <> wrote in message
    news:...
    > arnuld <> writes:
    >
    >> A Binary Search Tree implemented in C. Any advice on how to complete the
    >> one remained function ?

    >
    > <snip>
    >> enum { SIZE_NAME = 30 };
    >>
    >>
    >> /* One disadvantage of using char [] as a struct memeber is the size of
    >> name is limited. but if we use char* there will be no limit
    >> on the size then. */

    >
    > Yes, I'm not a fan of fixed-size arrays for string, but they are
    > simple.
    >
    >> struct namev
    >> {
    >> char name[SIZE_NAME];
    >> int cnt;
    >> struct namev* left;
    >> struct namev* right;
    >> };


    For what it's worth. I would've used
    char name[CHAR_MAX];

    Bill
     
    Bill Cunningham, Aug 4, 2009
    #4
  5. "arnuld" <> wrote in message
    news:p...
    >A Binary Search Tree implemented in C. Any advice on how to complete the
    > one remained function ?
    >
    >
    > /* A Binary tree learned from "The Practice of Programming", section
    > 2.8 . Its a little bit different though. It also includes the
    > * count of each element added into the tree. Currentlly it supports 3
    > functions: adding an element, printing and free()ing the whole
    > * tree. Only one fucntion, the deletion of a single element, have
    > remained.
    > *
    > *
    > * VERSION 0.0
    > *
    > */
    >
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <string.h>
    >
    > enum { SIZE_NAME = 30 };
    >
    >
    > /* One disadvantage of using char [] as a struct memeber is the size of
    > name is limited. but if we use char* there will be no limit
    > on the size then. */
    > struct namev
    > {
    > char name[SIZE_NAME];
    > int cnt;
    > struct namev* left;
    > struct namev* right;
    > };
    >
    >
    > struct namev* tree_add_name(struct namev*, char* );
    > void tree_free(struct namev* );
    > void tree_print(struct namev* );
    > struct namev* tree_delete_name(struct namev*, char*);
    >
    >

    Thanks Arnuld. Something here just clicked. I've been struugling with
    this algorithm for awhile. What you have written above is simple.

    Bill
     
    Bill Cunningham, Aug 4, 2009
    #5
  6. "Bill Cunningham" <> writes:

    > "Ben Bacarisse" <> wrote in message
    > news:...
    >> arnuld <> writes:
    >>
    >>> A Binary Search Tree implemented in C. Any advice on how to complete the
    >>> one remained function ?

    >>
    >> <snip>
    >>> enum { SIZE_NAME = 30 };
    >>>
    >>>
    >>> /* One disadvantage of using char [] as a struct memeber is the size of
    >>> name is limited. but if we use char* there will be no limit
    >>> on the size then. */

    >>
    >> Yes, I'm not a fan of fixed-size arrays for string, but they are
    >> simple.
    >>
    >>> struct namev
    >>> {
    >>> char name[SIZE_NAME];
    >>> int cnt;
    >>> struct namev* left;
    >>> struct namev* right;
    >>> };

    >
    > For what it's worth. I would've used
    > char name[CHAR_MAX];


    That would be very odd. CHAR_MAX is defined to be the largest value
    that plain char can hold. It bears no relationship to the length of
    name that one might want to store in this tree.

    --
    Ben.
     
    Ben Bacarisse, Aug 4, 2009
    #6
  7. arnuld

    arnuld Guest

    > On Tue, 04 Aug 2009 11:25:45 +0000, arnuld wrote:

    > ..SNIP...


    > struct namev
    > {
    > char name[SIZE_NAME];
    > int cnt;
    > struct namev* left;
    > struct namev* right;
    > };
    >



    Can't we do something like we do with a Queue in C:


    struct my_struct
    {
    int num;
    struct my_struct* next;
    };

    struct my_list
    {
    struct my_struct* head;
    struct my_struct* tail;
    };



    See the original struct is something but we implemented Queue in a new
    struct using 2 pointers to the original struct. Can we do something like
    that with Binary Tree ?




    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Aug 5, 2009
    #7
  8. arnuld <> writes:

    >> On Tue, 04 Aug 2009 11:25:45 +0000, arnuld wrote:

    >
    >> ..SNIP...

    >
    >> struct namev
    >> {
    >> char name[SIZE_NAME];
    >> int cnt;
    >> struct namev* left;
    >> struct namev* right;
    >> };
    >>

    >
    > Can't we do something like we do with a Queue in C:
    >
    > struct my_struct
    > {
    > int num;
    > struct my_struct* next;
    > };
    >
    > struct my_list
    > {
    > struct my_struct* head;
    > struct my_struct* tail;
    > };


    The first name is not very helpful. The two structures define,
    respectively, a node in a list and the list itself. I'd call the
    first my_node (if i had to use a "my_" prefix).

    > See the original struct is something but we implemented Queue in a new
    > struct using 2 pointers to the original struct. Can we do something like
    > that with Binary Tree ?


    Yes, but it helps less because the whole tree is one pointer, rather
    than two. You end up with:

    struct my_tree {
    struct my_tree_node *root;
    };

    Of course, if there is any reason to hold extra information then it
    starts to look more useful. However, because a tree is recursive, you
    will often find that any extra information you need (like, say, the
    depth) will be needed at every node, so it never belongs to the root
    alone.

    --
    Ben.
     
    Ben Bacarisse, Aug 5, 2009
    #8
  9. arnuld

    arnuld Guest

    > On Aug 4, 6:30 pm, Nick Keighley <> wrote:
    >> On 4 Aug, 12:25, arnuld <> wrote:
    > > void tree_free(struct namev* r)
    > > {
    > >   if(r)
    > >     {
    > >       tree_free(r->left);
    > >       tree_free(r->right);
    > >       tree_free(r);

    >
    > >       r = NULL;
    > >     }

    >
    > > }



    > this looks odd. Suppose you have a tree with only a single node in it.
    >
    >    &r = 7777;
    >     r->left = 0;
    >     r->right = 0;
    >
    > now call tree_free(&r) a trace looks like this
    >
    >    tree_free (777)
    >        tree_free (0)
    >        tree_free (0)
    >        tree_free (777)   oops!
    >
    >  I think you should have freed a node rather than a tree


    I am sure I did not get you.
     
    arnuld, Aug 6, 2009
    #9
  10. arnuld

    arnuld Guest

    > On Tue, 04 Aug 2009 13:30:58 +0100, Ben Bacarisse wrote:
    >> arnuld wrote:


    > Yes, I'm not a fan of fixed-size arrays for string, but they are simple.


    We are even then :)



    >> void tree_print(struct namev* r)
    >> {
    >> if(r)
    >> {
    >> tree_print(r->left);
    >> printf("name = %s, count = %d\n", r->name, r->cnt); /* how can
    >> I keep those printed elements properly aligned ? */


    > You can't -- not without finding the longest string first and using that
    > as a field width. try %20s or %-20s for the moment and see if that is
    > what you want.


    That does not work, I already tried.


    >> /* How can keep the pointers/left-right intact after free()ing this ?
    >> or I am just dealing with a theoretical problem. Practically, we
    >> never remove a single element from a tree ?? */


    > If e->left and e->right are both NULL you can delete and return NULL. if
    > only one of them is non-null you can return that pointer but what do you
    > do if both are non-null? One strategy (that you can use in the other
    > cases as well, BTW) is to set e->cnt to zero. Provided that your print
    > and any future "find" function ignore strings with zero count, it will
    > all work.


    But that way, memory will still be there being used by the elements.


    > The usual alternatives are to write a balanced tree, or to store strings
    > only in leaf nodes.


    I will take this one then. So I can conclude when you want to remove lots
    of elements then Binary Search Tree is not the choice to make ?



    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Aug 6, 2009
    #10
  11. arnuld <> writes:

    >> On Tue, 04 Aug 2009 13:30:58 +0100, Ben Bacarisse wrote:
    >>> arnuld wrote:

    <snip>
    >>> printf("name = %s, count = %d\n", r->name, r->cnt); /* how can
    >>> I keep those printed elements properly aligned ? */

    >
    >> You can't -- not without finding the longest string first and using that
    >> as a field width. try %20s or %-20s for the moment and see if that is
    >> what you want.

    >
    > That does not work, I already tried.


    You are on your own then unless you explain "does not work" or you
    specify "properly aligned"!

    >>> /* How can keep the pointers/left-right intact after free()ing this ?
    >>> or I am just dealing with a theoretical problem. Practically, we
    >>> never remove a single element from a tree ?? */

    >
    >> If e->left and e->right are both NULL you can delete and return NULL. if
    >> only one of them is non-null you can return that pointer but what do you
    >> do if both are non-null? One strategy (that you can use in the other
    >> cases as well, BTW) is to set e->cnt to zero. Provided that your print
    >> and any future "find" function ignore strings with zero count, it will
    >> all work.

    >
    > But that way, memory will still be there being used by the elements.


    How bad a problem is that? It may be a show-stopper or it may be
    quite unimportant.

    >> The usual alternatives are to write a balanced tree, or to store strings
    >> only in leaf nodes.

    >
    > I will take this one then.


    Which one? The leaf only option may use more memory than leaving
    nodes with a count of zero.

    > So I can conclude when you want to remove lots
    > of elements then Binary Search Tree is not the choice to make ?


    No. The benefit does decrease as the proportion of deletes vs.
    look-ups increases -- but that is not the same as a bad choice.

    --
    Ben.
     
    Ben Bacarisse, Aug 6, 2009
    #11
  12. arnuld

    Guest

    On 04 Aug 2009 11:25:45 GMT arnuld <> wrote:

    | /* One disadvantage of using char [] as a struct memeber is the size of
    | name is limited. but if we use char* there will be no limit
    | on the size then. */
    | struct namev
    | {
    | char name[SIZE_NAME];
    | int cnt;
    | struct namev* left;
    | struct namev* right;
    | };

    This isn't a binary tree issue, but a data structure issue.
    What I do for any kind of struct with ONE variable part is
    put the variable part last, define it as having 1 member,
    but actually allocate the node as large as needed. I do this
    for binary trees and for linked lists. The complication is
    when you want the key and value to both be variable. But
    even this can be done in a single piece of data.

    --
    -----------------------------------------------------------------------------
    | Phil Howard KA9WGN | http://linuxhomepage.com/ http://ham.org/ |
    | (first name) at ipal.net | http://phil.ipal.org/ http://ka9wgn.ham.org/ |
    -----------------------------------------------------------------------------
     
    , Aug 6, 2009
    #12
  13. writes:
    > On 04 Aug 2009 11:25:45 GMT arnuld <> wrote:
    > | /* One disadvantage of using char [] as a struct memeber is the size of
    > | name is limited. but if we use char* there will be no limit
    > | on the size then. */
    > | struct namev
    > | {
    > | char name[SIZE_NAME];
    > | int cnt;
    > | struct namev* left;
    > | struct namev* right;
    > | };
    >
    > This isn't a binary tree issue, but a data structure issue.
    > What I do for any kind of struct with ONE variable part is
    > put the variable part last, define it as having 1 member,
    > but actually allocate the node as large as needed. I do this
    > for binary trees and for linked lists. The complication is
    > when you want the key and value to both be variable. But
    > even this can be done in a single piece of data.


    This is the infamous "struct hack"; see question 2.6 of the
    comp.lang.c FAQ, <http://www.c-faq.com/>.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Aug 7, 2009
    #13
  14. arnuld

    arnuld Guest

    Binary Search Tree and free() (was: A Binary Tree in C)

    > On Thu, 06 Aug 2009 15:19:01 +0100, Ben Bacarisse wrote:

    >> arnuld <> writes:
    >> That does not work, I already tried.


    > You are on your own then unless you explain "does not work" or you
    > specify "properly aligned"!


    I will leave this feature as its not technical point but printing that
    pleases to eyes.


    >> But that way, memory will still be there being used by the elements.


    > How bad a problem is that? It may be a show-stopper or it may be quite
    > unimportant.



    I think it a very serious problem. When an element is not in use then we
    need to free the memory hold by it otherwise it could lead to Segfault or
    malloc() failed when system will have no memory to allocate.



    >> I will take this one then.


    > Which one? The leaf only option may use more memory than leaving nodes
    > with a count of zero.


    I will write a balanced tree then. if a data-structure does not allow me
    to free the memory, its of no use.


    >> So I can conclude when you want to remove lots of elements then Binary
    >> Search Tree is not the choice to make ?


    > No. The benefit does decrease as the proportion of deletes vs. look-ups
    > increases -- but that is not the same as a bad choice.



    If a program can't free the memory, how good is that. The it will be like
    writing one more Windows.




    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Aug 7, 2009
    #14
  15. Re: Binary Search Tree and free()

    arnuld <> writes:

    >> On Thu, 06 Aug 2009 15:19:01 +0100, Ben Bacarisse wrote:
    >>> arnuld <> writes:

    <snip>
    >>> But that way, memory will still be there being used by the elements.

    >
    >> How bad a problem is that? It may be a show-stopper or it may be quite
    >> unimportant.

    >
    > I think it a very serious problem. When an element is not in use then we
    > need to free the memory hold by it otherwise it could lead to Segfault or
    > malloc() failed when system will have no memory to allocate.


    Only you know, of course, but what you give here is a very general
    argument. Note that what I suggested does not mean that the space
    can't every be reclaimed. When the tree is no longer needed you can
    delete it and as you delete more and more nodes, more of the nodes
    will have null left and right pointers and you can always clean up the
    tree -- either looking for nodes that have only zero-count children or
    simply deleting an re-building it.

    I felt it worth suggesting because allocating fixed-length strings in
    the nodes is also wasteful of space so I did not think you were being
    careful with memory use.

    <snip>
    > I will write a balanced tree then. if a data-structure does not allow me
    > to free the memory, its of no use.


    All the above is beside the point now because a balanced tree is
    absolutely the right way to do it.

    <snip>
    --
    Ben.
     
    Ben Bacarisse, Aug 7, 2009
    #15
  16. arnuld

    Guest

    Re: Binary Search Tree and free()

    On 07 Aug 2009 06:41:33 GMT arnuld <> wrote:

    | I think it a very serious problem. When an element is not in use then we
    | need to free the memory hold by it otherwise it could lead to Segfault or
    | malloc() failed when system will have no memory to allocate.

    I have written programs where I needed the binary tree(s) right up to the
    end of the program. I could have then gone through the tree and freed
    each node. But I didn't. I let VM destruction take care of it. That is
    not an option when the VM is not being destroyed or it's not a VM case
    (such as a kernel or driver). I regularly skip free() calls in my CGI
    code, for example, because the VM lifetime is so short.


    | I will write a balanced tree then. if a data-structure does not allow me
    | to free the memory, its of no use.

    In my AVL code, I did write an avl_empty() function. It deletes all the
    nodes in a tree without the extra work that would be needed (such as the
    pointless rebalancing) by calling avl_delete() in a loop. It calls a
    provided callback function passing it the pointer to the node. I pass it
    the function pointer for free() in most cases.

    I see no reason free() cannot be used when deleting a node, or all nodes
    all at once.

    --
    -----------------------------------------------------------------------------
    | Phil Howard KA9WGN | http://linuxhomepage.com/ http://ham.org/ |
    | (first name) at ipal.net | http://phil.ipal.org/ http://ka9wgn.ham.org/ |
    -----------------------------------------------------------------------------
     
    , Aug 7, 2009
    #16
  17. arnuld

    arnuld Guest

    Re: Binary Search Tree and free()

    > On Fri, 07 Aug 2009 15:49:05 +0100, Ben Bacarisse wrote:

    >> arnuld <> writes:
    >> I think it a very serious problem. When an element is not in use then
    >> we need to free the memory hold by it otherwise it could lead to
    >> Segfault or malloc() failed when system will have no memory to
    >> allocate.


    > Only you know, of course, but what you give here is a very general
    > argument. Note that what I suggested does not mean that the space can't
    > every be reclaimed. When the tree is no longer needed you can delete it
    > and as you delete more and more nodes, more of the nodes will have null
    > left and right pointers and you can always clean up the tree -- either
    > looking for nodes that have only zero-count children or simply deleting
    > an re-building it.



    I don't follow you here. Lets leave the zero-count feature and talk about
    deleting (which of course means free()ing) the tree elements. You say,
    you did not suggest that memory hold by the elements can not be
    reclaimed. Fine, that is what I want, to get back the memory but then u
    suggest, in the last line, to simple deleting and building the whole tree
    which of course seems like a wastage of resources to me when the input is
    much larger.




    > I felt it worth suggesting because allocating fixed-length strings in
    > the nodes is also wasteful of space so I did not think you were being
    > careful with memory use.


    You have 2 choices here, either allocate the local array or use pointer
    and then malloc() the memory. I did not want to use malloc(), I avoid
    malloc() *all* the time *while* I can.

    >> I will write a balanced tree then. if a data-structure does not allow
    >> me to free the memory, its of no use.


    > All the above is beside the point now because a balanced tree is
    > absolutely the right way to do it.


    Okay, Balanced Tree is the next Data Structure I will implement in C. I
    have fever, there is some sort of flu that is happened to spread
    Hyderabad (this is where I work). I have 5 days of medication, after that
    I will work on Balanced Tree.






    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Aug 8, 2009
    #17
  18. Re: Binary Search Tree and free()

    arnuld <> writes:

    >> On Fri, 07 Aug 2009 15:49:05 +0100, Ben Bacarisse wrote:

    >
    >>> arnuld <> writes:
    >>> I think it a very serious problem. When an element is not in use then
    >>> we need to free the memory hold by it otherwise it could lead to
    >>> Segfault or malloc() failed when system will have no memory to
    >>> allocate.

    >
    >> Only you know, of course, but what you give here is a very general
    >> argument. Note that what I suggested does not mean that the space can't
    >> every be reclaimed. When the tree is no longer needed you can delete it
    >> and as you delete more and more nodes, more of the nodes will have null
    >> left and right pointers and you can always clean up the tree -- either
    >> looking for nodes that have only zero-count children or simply deleting
    >> an re-building it.

    >
    > I don't follow you here. Lets leave the zero-count feature and talk about
    > deleting (which of course means free()ing) the tree elements. You say,
    > you did not suggest that memory hold by the elements can not be
    > reclaimed. Fine, that is what I want, to get back the memory but then u
    > suggest, in the last line, to simple deleting and building the whole tree
    > which of course seems like a wastage of resources to me when the input is
    > much larger.


    And it may not be worth it. I was just offering alternatives. You
    seemed to be making a general claim that not deleting every node as
    early as possible is useless, but that is not true. It is not space
    optimal but there may be programs in which it is the right balance
    between programming complexity and performance.
    >
    >> I felt it worth suggesting because allocating fixed-length strings in
    >> the nodes is also wasteful of space so I did not think you were being
    >> careful with memory use.

    >
    > You have 2 choices here, either allocate the local array or use pointer
    > and then malloc() the memory. I did not want to use malloc(), I avoid
    > malloc() *all* the time *while* I can.


    (Aside: local is not the best word. You mean in the same struct.
    Local should probably be kept to refer to named objects with automatic
    storage class.)

    Allocating the string in the same struct as the pointers does not mean
    that they have to be of fixed size. C99 has formalised "the struct
    hack" that was common in C90 for dealing with this.

    Secondly, you can reduce the number of malloc calls in other ways: you
    could allocate large string buffers and use them to store your
    strings, allocating again when they run out, or you could allocate
    arrays of node structures and hand these out as you need them. In the
    bad old days these were very useful techniques, but it their relative
    benefit has decreased as malloc (and OS memory allocation) have got
    better. I am not suggesting your do either, but I do want to explain
    why, to me, your program does not look as if you want to avoid malloc
    wherever possible.

    >>> I will write a balanced tree then. if a data-structure does not allow
    >>> me to free the memory, its of no use.

    >
    >> All the above is beside the point now because a balanced tree is
    >> absolutely the right way to do it.

    >
    > Okay, Balanced Tree is the next Data Structure I will implement in C. I
    > have fever, there is some sort of flu that is happened to spread
    > Hyderabad (this is where I work). I have 5 days of medication, after that
    > I will work on Balanced Tree.


    Sorry to hear that. I with you a speedy recovery.

    --
    Ben.
     
    Ben Bacarisse, Aug 8, 2009
    #18
  19. On 6 Aug, 07:58, arnuld <> wrote:
    > > On Aug 4, 6:30 pm, Nick Keighley <> wrote:
    > >> On 4 Aug, 12:25, arnuld <> wrote:
    > > > void tree_free(struct namev* r)
    > > > {
    > > >   if(r)
    > > >     {
    > > >       tree_free(r->left);
    > > >       tree_free(r->right);
    > > >       tree_free(r);

    >
    > > >       r = NULL;
    > > >     }

    >
    > > > }

    > > this looks odd. Suppose you have a tree with only a single node in it.

    >
    > >    &r = 7777;
    > >     r->left = 0;
    > >     r->right = 0;

    >
    > > now call tree_free(&r) a trace looks like this

    >
    > >    tree_free (777)
    > >        tree_free (0)
    > >        tree_free (0)
    > >        tree_free (777)   oops!

    >
    > >  I think you should have freed a node rather than a tree

    >
    > I am sure I did not get you.


    you've called tree_free() inside tree_free() with the same parameter.
    This looks like a recursive loop tome
     
    Nick Keighley, Aug 9, 2009
    #19
    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,243
  2. sharan
    Replies:
    4
    Views:
    725
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    869
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    717
    CBFalconer
    Oct 30, 2007
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,239
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page