Binary Search Tree

Discussion in 'C++' started by Defected, May 19, 2007.

  1. Defected

    Defected Guest

    Hi,

    How i can create a Binary Search Tree with a class ?


    thanks
     
    Defected, May 19, 2007
    #1
    1. Advertising

  2. Defected

    osmium Guest

    "Defected" writes:

    > How i can create a Binary Search Tree with a class ?


    The wordsmiths at C++ decided that right word for "tree" was "map". So get
    out your handy-dandy copy of Josuttis and go from there. Page 194.
     
    osmium, May 19, 2007
    #2
    1. Advertising

  3. On 2007-05-19 18:35, osmium wrote:
    > "Defected" writes:
    >
    >> How i can create a Binary Search Tree with a class ?

    >
    > The wordsmiths at C++ decided that right word for "tree" was "map". So get
    > out your handy-dandy copy of Josuttis and go from there. Page 194.


    Not really, a map is a class that allows you to map a key to a value and
    have some guarantees on how fast some operations can be performed, on
    most implementations a red-black tree, which is not a binary search tree.

    To the OP:

    To create a binary search tree you should probably have two classes, one
    for the nodes and one for the tree. The nodes will be quite simple, they
    only have to contain a value and links to child-nodes (and perhaps one
    for the parent). The other class contains information about the tree
    (number of nodes and so on) and a link to the root-node. It also
    contains methods to insert, find, delete and so on. How to perform those
    operations on the tree should be in your book on algorithms and data-
    structures (or google if you don't have a book).

    If you get any problems with getting the code to work then come back
    here and post your code and describe your problem. However before
    posting read the relevant sections of the FAQ first:

    http://www.parashift.com/c -faq-lite/how-to-post.html

    --
    Erik Wikström
     
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, May 19, 2007
    #3
  4. * Erik Wikström:
    > On 2007-05-19 18:35, osmium wrote:
    >> "Defected" writes:
    >>
    >>> How i can create a Binary Search Tree with a class ?

    >>
    >> The wordsmiths at C++ decided that right word for "tree" was "map".
    >> So get out your handy-dandy copy of Josuttis and go from there. Page
    >> 194.

    >
    > Not really, a map is a class that allows you to map a key to a value and
    > have some guarantees on how fast some operations can be performed, on
    > most implementations a red-black tree, which is not a binary search tree.


    On the contrary, a red-black tree is a binary search tree, more
    specifically a specific kind of self-balancing binary search tree.

    But on the third hand, there's no guarantee std::map is implemented as a
    red-black tree.

    However, that's the most common implementation, and std::map offers the
    same performance characteristics as a binary search tree.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, May 19, 2007
    #4
  5. Defected

    crh Guest

    Defected wrote:
    > Hi,
    >
    > How i can create a Binary Search Tree with a class ?
    >
    >
    > thanks


    Look at this one implementation: http://phpfi.com/235365
     
    crh, May 19, 2007
    #5
  6. Defected

    osmium Guest

    "Defected" writes:

    > How i can create a Binary Search Tree with a class ?


    I see now that I didn't read the question closely enough, sorry about that.
    The question is how to _create_ and my resposne was how to _use_.

    The best write up I know of is in _Algorithms + Data Structures = Programs_
    by Nicklaus Wirth. You will probably need access to a good college library
    to find it.

    The hardest part is comprehending the delete function. Save that for the
    last thing you do.
     
    osmium, May 19, 2007
    #6
  7. Defected

    Jon Harrop Guest

    Alf P. Steinbach wrote:
    > * Erik Wikström:
    >> Not really, a map is a class


    A map is not necessarily a class.

    >> that allows you to map a key to a value and
    >> have some guarantees on how fast some operations can be performed, on
    >> most implementations a red-black tree, which is not a binary search tree.

    >
    > On the contrary, a red-black tree is a binary search tree,


    A red-black tree is not necessarily a search tree. It could be used to
    implement a grab bag, for example.

    --
    Dr Jon D Harrop, Flying Frog Consultancy
    OCaml for Scientists
    http://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet
     
    Jon Harrop, May 30, 2007
    #7
  8. * Jon Harrop:
    > Alf P. Steinbach wrote:
    >> * Erik Wikström:
    >>> Not really, a map is a class

    >
    > A map is not necessarily a class.


    You snipped a lot of context there: Erik's statement that you quoted the
    start of was about std::map. And you leave us wondering whether that
    snipping and apparent "misunderstanding" is intentional or not. Not the
    least, considering your recent language advocacy postings, which were
    borderline trolling, as was this.


    >>> that allows you to map a key to a value and
    >>> have some guarantees on how fast some operations can be performed, on
    >>> most implementations a red-black tree, which is not a binary search tree.

    >> On the contrary, a red-black tree is a binary search tree,

    >
    > A red-black tree is not necessarily a search tree. It could be used to
    > implement a grab bag, for example.


    Go get yourself a cup of coffee, then start your change of the world's
    terminology by fixing what you can fix, e.g. Wikipedia.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, May 30, 2007
    #8
  9. Defected

    Jon Harrop Guest

    Alf P. Steinbach wrote:
    > Go get yourself a cup of coffee, then start your change of the world's
    > terminology by fixing what you can fix, e.g. Wikipedia.


    Ah yes, the encyclopaedia by children for children. Anyone reaching for that
    to learn about data structures (or anything else) is asking for trouble.
    I'd recommend Cormen et al.

    --
    Dr Jon D Harrop, Flying Frog Consultancy
    OCaml for Scientists
    http://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet
     
    Jon Harrop, May 31, 2007
    #9
  10. Defected

    Zeppe Guest

    Jon Harrop wrote:
    > Alf P. Steinbach wrote:
    >> Go get yourself a cup of coffee, then start your change of the world's
    >> terminology by fixing what you can fix, e.g. Wikipedia.

    >
    > Ah yes, the encyclopaedia by children for children. Anyone reaching for that
    > to learn about data structures (or anything else) is asking for trouble.
    > I'd recommend Cormen et al.
    >


    You mean this one?
    http://books.google.com/books?id=NL...rithms Cormen&sig=yd0Gq55nV9OzYCM97qRrFFTYMzc

    it seems like you have to edit this one as well, because it seems to
    agree with wikipedia, the encyclopaedia by children for children.

    Regards,

    Zeppe
     
    Zeppe, May 31, 2007
    #10
  11. Defected

    osmium Guest

    "Zeppe" wrote:

    > Jon Harrop wrote:
    >> Alf P. Steinbach wrote:
    >>> Go get yourself a cup of coffee, then start your change of the world's
    >>> terminology by fixing what you can fix, e.g. Wikipedia.

    >>
    >> Ah yes, the encyclopaedia by children for children. Anyone reaching for
    >> that
    >> to learn about data structures (or anything else) is asking for trouble.
    >> I'd recommend Cormen et al.
    >>

    >
    > You mean this one?
    > http://books.google.com/books?id=NL...rithms Cormen&sig=yd0Gq55nV9OzYCM97qRrFFTYMzc
    >
    > it seems like you have to edit this one as well, because it seems to agree
    > with wikipedia, the encyclopaedia by children for children.


    Good show, Zeppe!
     
    osmium, May 31, 2007
    #11
  12. Defected

    desktop Guest

    osmium wrote:
    > "Defected" writes:
    >
    >> How i can create a Binary Search Tree with a class ?

    >
    > The wordsmiths at C++ decided that right word for "tree" was "map". So get
    > out your handy-dandy copy of Josuttis and go from there. Page 194.
    >
    >


    What book are you referring to? Guess its not the C++ Templates book.
     
    desktop, May 31, 2007
    #12
    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,235
  2. sharan
    Replies:
    4
    Views:
    719
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    866
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    714
    CBFalconer
    Oct 30, 2007
  5. Bogdan

    Binary tree search vs Binary search

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

Share This Page