By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,956 Members | 1,722 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,956 IT Pros & Developers. It's quick & easy.

Binary Search Tree

P: n/a
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.
Jul 22 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
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.
Jul 22 '05 #2

P: n/a
On Fri, 16 Apr 2004 14:59:24 -0400 in comp.lang.c++, Ravi
<Ra**@xxx.yyy.zzz> 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?

Jul 22 '05 #3

P: n/a

"Ravi" <Ra**@xxx.yyy.zzz> wrote in message
news:c5*********@prometheus.acsu.buffalo.edu...
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).
Jul 22 '05 #4

P: n/a

"Dave" <be***********@yahoo.com> wrote in message
news:10*************@news.supernews.com...

"Ravi" <Ra**@xxx.yyy.zzz> wrote in message
news:c5*********@prometheus.acsu.buffalo.edu...
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...
Jul 22 '05 #5

P: n/a
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.
Jul 22 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.