Implement Balanced Binary Search Tree with existing STL containers

[sajis997]

Hello forum,

So far I know that there is no tree data structure implemented into the STL. Probably there are reasons behind it, which I am not aware of. I need to implement the data structure that is mentioned in the subject. I was wondering if the existing STL containers could be used extensively to achieve the purpose.

Some references/hints would be of great help.

Thanks

[Peter87]

std::map and std::set are usually implemented as balanced binary search trees.

http://en.cppreference.com/w/cpp/container/map
http://en.cppreference.com/w/cpp/container/set

[sajis997]

Thanks for the reference. It would be even better if it is possible to visualize the map or set contents as the parent/child relationship of the self-balancing binary search tree.

[sajis997]

Hello again,

I am following the Professional C++ and it says the following:

The STL does not provide any generic tree or graph structures. Although map s and
set s are generally implemented as balanced binary trees, the STL does not expose this
implementation in the interface. If you need a tree or graph structure for something like
writing a parser, you will need to implement your own or find an implementation in another
library.


Is it really true ?

[Peter87]

Yes, it is true.

[moorecm]

Writing functions that insert into and search for an element in a binary search tree is a common interview question. I had to do this on the whiteboard for my last job... The balancing would be the hardest part, IMO. Give it a shot!