Binary tree search algorithm in C++

[Bogdan]

Hi

Could you recommend a C++ library implementing binary tree search
algorithm ? STL and boost libraries don't seem to provide directly
such a specialized algorithm.

regards
Bogdan

 

[Maxim Yegorushkin]

Could you recommend a C++ library implementing binary tree search
algorithm ? STL and boost libraries don't seem to provide directly
such a specialized algorithm.

http://en.wikipedia.org/wiki/Binary_search_tree#Searching

 

[Alf P. Steinbach /Usenet]

* Bogdan, on 19.10.2010 12:15:

Hi

Could you recommend a C++ library implementing binary tree search
algorithm ? STL and boost libraries don't seem to provide directly
such a specialized algorithm.

Check if std::map, std::multimap, std::set or std::multiset fits your needs.

These do binary tree searches for lookup.

At least with ordinary implementations.


Cheers & hth.,

- Alf

 

[Juha Nieminen]

At least with ordinary implementations.

Given that the standard imposes pretty strict requirements for those
data containers, is it even *possible* to use anything but a balanced
binary search tree?

 

[Alf P. Steinbach /Usenet]

* Juha Nieminen, on 19.10.2010 18:57:

Given that the standard imposes pretty strict requirements for those
data containers, is it even *possible* to use anything but a balanced
binary search tree?

Yes, one could use a more general tree. E.g. something like a B-tree (it's a
generalization, see e.g. http://en.wikipedia.org/wiki/B-tree). Or some hybrid
thing, since simple insertions and deletions in an array can be more efficient
for small number of items -- the idea would then be to switch over to tree for
larger number of items.

Cheers,

- Alf