Binary Search Tree

Discussion in 'C++' started by Ravi, Apr 16, 2004.

  1. Ravi

    Ravi Guest

    I recently had to write some code which required me to use a binary
    search tree (BST) due to running time concerns. I found that there is no
    BST class in the Standard C++ library. I have been told that other
    container classes such as set use a balanced BST internally. Is it
    possible to access this functionality or is the only solution to write a
    BST class from scratch?
    -Ravi.
     
    Ravi, Apr 16, 2004
    #1
    1. Advertising

  2. Ravi wrote:

    > I recently had to write some code which required me to use a binary
    > search tree (BST) due to running time concerns. I found that there is no
    > BST class in the Standard C++ library. I have been told that other
    > container classes such as set use a balanced BST internally. Is it
    > possible to access this functionality or is the only solution to write a
    > BST class from scratch?
    > -Ravi.


    The standard library does not provide a BST. If you need one you'll have
    to get it elsewhere, possibly by writing it yourself.

    -Kevin
    --
    My email address is valid, but changes periodically.
    To contact me please use the address from a recent posting.
     
    Kevin Goodsell, Apr 16, 2004
    #2
    1. Advertising

  3. Ravi

    David Harmon Guest

    On Fri, 16 Apr 2004 14:59:24 -0400 in comp.lang.c++, Ravi
    <> wrote,
    >container classes such as set use a balanced BST internally. Is it
    >possible to access this functionality or is the only solution to write a
    >BST class from scratch?


    The ordinary solution is to use std::set or std::map. They were meant
    to be used. What functionality do you want that they do not provide?
     
    David Harmon, Apr 16, 2004
    #3
  4. Ravi

    Dave Guest

    "Ravi" <> wrote in message
    news:c5paeh$uv$...
    > I recently had to write some code which required me to use a binary
    > search tree (BST) due to running time concerns. I found that there is no
    > BST class in the Standard C++ library. I have been told that other
    > container classes such as set use a balanced BST internally. Is it
    > possible to access this functionality or is the only solution to write a
    > BST class from scratch?
    > -Ravi.


    There is no guarantee that the Standard Library containers are implemented
    as a binary search tree, but you *are* guaranteed the performance of a
    binary search tree (i.e. O(lg N) time complexity). So, if you must have a
    literal binary search tree, you'll have to roll your own. However, if
    performance is your only concern, you should take a look at std::set<> or
    std::map<> (or their multi counterparts).
     
    Dave, Apr 16, 2004
    #4
  5. Ravi

    Dave Guest

    "Dave" <> wrote in message
    news:...
    >
    > "Ravi" <> wrote in message
    > news:c5paeh$uv$...
    > > I recently had to write some code which required me to use a binary
    > > search tree (BST) due to running time concerns. I found that there is no
    > > BST class in the Standard C++ library. I have been told that other
    > > container classes such as set use a balanced BST internally. Is it
    > > possible to access this functionality or is the only solution to write a
    > > BST class from scratch?
    > > -Ravi.

    >
    > There is no guarantee that the Standard Library containers are implemented
    > as a binary search tree, but you *are* guaranteed the performance of a
    > binary search tree (i.e. O(lg N) time complexity). So, if you must have a
    > literal binary search tree, you'll have to roll your own. However, if
    > performance is your only concern, you should take a look at std::set<> or
    > std::map<> (or their multi counterparts).
    >
    >


    As an aside, given the performance requirements that must be met, there
    aren't too many data structures besides balanced binary search trees that
    could be used to implement the associative containers. Someone had told me
    once that "skip lists" might be an alternative, but I am not familiar with
    them, so I can't corroborate that statement myself...
     
    Dave, Apr 17, 2004
    #5
  6. Dave wrote:

    > As an aside, given the performance requirements that must be met, there
    > aren't too many data structures besides balanced binary search trees that
    > could be used to implement the associative containers. Someone had told me
    > once that "skip lists" might be an alternative, but I am not familiar with
    > them, so I can't corroborate that statement myself...
    >
    >


    Skip lists are supposed to have favorable performance compared to most
    types of balanced search tree (in one experiment I read about, only
    non-recursive AVL did better, if I recall correctly).

    However, skip lists have a random component, which means there's a
    chance (remote though it is) that the performance will degrade severely.
    This would probably be enough to make a map or set implementation using
    skip lists not strictly compliant (though nobody would ever know the
    difference, I think).

    -Kevin
    --
    My email address is valid, but changes periodically.
    To contact me please use the address from a recent posting.
     
    Kevin Goodsell, Apr 17, 2004
    #6
    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,136
  2. sharan
    Replies:
    4
    Views:
    694
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    835
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    693
    CBFalconer
    Oct 30, 2007
  5. Bogdan

    Binary tree search vs Binary search

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

Share This Page