Binary Search Tree

[Ravi]

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.

 

[Kevin Goodsell]

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

 

[David Harmon]

On Fri, 16 Apr 2004 14:59:24 -0400 in comp.lang.c++, Ravi

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?

 

[Dave]

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]

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...

 

[Kevin Goodsell]

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