STL and Balanced Trees???

Discussion in 'C++' started by Peter Tkacz, Oct 23, 2003.

  1. Peter Tkacz

    Peter Tkacz Guest

    Are there any data types within STL that implement a balanced tree?

    Peter
     
    Peter Tkacz, Oct 23, 2003
    #1
    1. Advertising

  2. Peter Tkacz

    Dave Guest

    "Peter Tkacz" <> wrote in message
    news:8zFlb.31253$...
    > Are there any data types within STL that implement a balanced tree?
    >
    > Peter
    >
    >


    Well, the performance requirements imposed on maps, multimaps, sets and
    multisets cause them to be implemented as balanced trees.
     
    Dave, Oct 23, 2003
    #2
    1. Advertising

  3. On Wed, 22 Oct 2003 20:41:52 -0400, Peter Tkacz <> wrote:

    > Are there any data types within STL that implement a balanced tree?
    >
    > Peter
    >
    >
    >

    map , multimap , set , mutliset


    --
    grzegorz
     
    Grzegorz Sakrejda, Oct 23, 2003
    #3
  4. Peter Tkacz wrote:
    > Are there any data types within STL that implement a balanced tree?


    There is no requirement to implement a certain algorithm but STL
    templates that might do somthing similar are std::map<...> or
    std::multimap<...> .
     
    Gianni Mariani, Oct 23, 2003
    #4
  5. Peter Tkacz

    Dave Guest

    "Gianni Mariani" <> wrote in message
    news:bn79ad$...
    > Peter Tkacz wrote:
    > > Are there any data types within STL that implement a balanced tree?

    >
    > There is no requirement to implement a certain algorithm but STL
    > templates that might do somthing similar are std::map<...> or
    > std::multimap<...> .
    >


    True, but can anyone think of any known data structures other than balanced
    binary trees that would meet the logarithmic time complexity requirements
    imposed by the Standard? I'm really seriously asking because, as far as I
    know, there are none, but I don't know that I am right on that...
     
    Dave, Oct 23, 2003
    #5
  6. Peter Tkacz

    Jerry Coffin Guest

    In article <>,
    says...

    [ ... ]

    > Well, the performance requirements imposed on maps, multimaps, sets and
    > multisets cause them to be implemented as balanced trees.


    More or less, partly depending on how tightly you define "tree" -- just
    for example, you might be able to do the job with a heap, but it's open
    to argument that a heap really IS a tree, just represented differently
    than usual.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Oct 23, 2003
    #6
  7. Peter Tkacz

    Dave Guest

    "Dave" <> wrote in message
    news:...
    >
    > "Gianni Mariani" <> wrote in message
    > news:bn79ad$...
    > > Peter Tkacz wrote:
    > > > Are there any data types within STL that implement a balanced tree?

    > >
    > > There is no requirement to implement a certain algorithm but STL
    > > templates that might do somthing similar are std::map<...> or
    > > std::multimap<...> .
    > >

    >
    > True, but can anyone think of any known data structures other than

    balanced
    > binary trees that would meet the logarithmic time complexity requirements
    > imposed by the Standard? I'm really seriously asking because, as far as I
    > know, there are none, but I don't know that I am right on that...
    >
    >


    In looking around a bit on this, it appears that skip lists might also be a
    data structure that could be used to implement the STL associative
    containers and meet the logarithmic time complexity requirements.
     
    Dave, Oct 23, 2003
    #7
  8. Peter Tkacz

    Jerry Coffin Guest

    In article <>,
    says...

    [ ... ]

    > In looking around a bit on this, it appears that skip lists might also be a
    > data structure that could be used to implement the STL associative
    > containers and meet the logarithmic time complexity requirements.


    IIRC, a skip list provides excellent _expected_ complexity, but at least
    the usual ones don't meet the requirements for worst-case complexity.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Oct 24, 2003
    #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. Garrek
    Replies:
    3
    Views:
    577
    Bobby Ryzhy
    Jul 12, 2004
  2. C++ Shark

    implementing trees in STL

    C++ Shark, Sep 15, 2003, in forum: C++
    Replies:
    6
    Views:
    384
    Frank Schmitt
    Sep 23, 2003
  3. jacob navia

    Binary search trees (AVL trees)

    jacob navia, Jan 3, 2010, in forum: C Programming
    Replies:
    34
    Views:
    1,433
    Dann Corbit
    Jan 8, 2010
  4. 3P
    Replies:
    1
    Views:
    380
    Jason Keats
    Apr 24, 2010
  5. Chris Bellini

    Server.Transfer and Load Balanced Environments

    Chris Bellini, Sep 8, 2006, in forum: ASP General
    Replies:
    2
    Views:
    113
    Aaron Bertrand [SQL Server MVP]
    Sep 8, 2006
Loading...

Share This Page