Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > STL and Balanced Trees???

Reply
Thread Tools

STL and Balanced Trees???

 
 
Peter Tkacz
Guest
Posts: n/a
 
      10-23-2003
Are there any data types within STL that implement a balanced tree?

Peter


 
Reply With Quote
 
 
 
 
Dave
Guest
Posts: n/a
 
      10-23-2003

"Peter Tkacz" <(E-Mail Removed)> wrote in message
news:8zFlb.31253$(E-Mail Removed)...
> Are there any data types within STL that implement a balanced tree?
>
> Peter
>
>


Well, the performance requirements imposed on maps, multimaps, sets and
multisets cause them to be implemented as balanced trees.


 
Reply With Quote
 
 
 
 
Grzegorz Sakrejda
Guest
Posts: n/a
 
      10-23-2003
On Wed, 22 Oct 2003 20:41:52 -0400, Peter Tkacz <(E-Mail Removed)> wrote:

> Are there any data types within STL that implement a balanced tree?
>
> Peter
>
>
>

map , multimap , set , mutliset


--
grzegorz
 
Reply With Quote
 
Gianni Mariani
Guest
Posts: n/a
 
      10-23-2003
Peter Tkacz wrote:
> Are there any data types within STL that implement a balanced tree?


There is no requirement to implement a certain algorithm but STL
templates that might do somthing similar are std::map<...> or
std::multimap<...> .

 
Reply With Quote
 
Dave
Guest
Posts: n/a
 
      10-23-2003

"Gianni Mariani" <(E-Mail Removed)> wrote in message
news:bn79ad$(E-Mail Removed)...
> Peter Tkacz wrote:
> > Are there any data types within STL that implement a balanced tree?

>
> There is no requirement to implement a certain algorithm but STL
> templates that might do somthing similar are std::map<...> or
> std::multimap<...> .
>


True, but can anyone think of any known data structures other than balanced
binary trees that would meet the logarithmic time complexity requirements
imposed by the Standard? I'm really seriously asking because, as far as I
know, there are none, but I don't know that I am right on that...


 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      10-23-2003
In article <(E-Mail Removed)>, http://www.velocityreviews.com/forums/(E-Mail Removed)
says...

[ ... ]

> Well, the performance requirements imposed on maps, multimaps, sets and
> multisets cause them to be implemented as balanced trees.


More or less, partly depending on how tightly you define "tree" -- just
for example, you might be able to do the job with a heap, but it's open
to argument that a heap really IS a tree, just represented differently
than usual.

--
Later,
Jerry.

The universe is a figment of its own imagination.
 
Reply With Quote
 
Dave
Guest
Posts: n/a
 
      10-23-2003

"Dave" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
>
> "Gianni Mariani" <(E-Mail Removed)> wrote in message
> news:bn79ad$(E-Mail Removed)...
> > Peter Tkacz wrote:
> > > Are there any data types within STL that implement a balanced tree?

> >
> > There is no requirement to implement a certain algorithm but STL
> > templates that might do somthing similar are std::map<...> or
> > std::multimap<...> .
> >

>
> True, but can anyone think of any known data structures other than

balanced
> binary trees that would meet the logarithmic time complexity requirements
> imposed by the Standard? I'm really seriously asking because, as far as I
> know, there are none, but I don't know that I am right on that...
>
>


In looking around a bit on this, it appears that skip lists might also be a
data structure that could be used to implement the STL associative
containers and meet the logarithmic time complexity requirements.


 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      10-24-2003
In article <(E-Mail Removed)>, (E-Mail Removed)
says...

[ ... ]

> In looking around a bit on this, it appears that skip lists might also be a
> data structure that could be used to implement the STL associative
> containers and meet the logarithmic time complexity requirements.


IIRC, a skip list provides excellent _expected_ complexity, but at least
the usual ones don't meet the requirements for worst-case complexity.

--
Later,
Jerry.

The universe is a figment of its own imagination.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cache, Applicatin and Load Balanced servers 3P ASP .Net 1 04-24-2010 12:06 AM
Server.Transfer and Load Balanced Environments Chris Bellini ASP General 2 09-08-2006 07:27 PM
Problem in NLB - 2 server is not balanced =?Utf-8?B?U0s=?= Microsoft Certification 0 09-14-2004 07:55 AM
Fair and Balanced View of the Sigma SD-10 Digital SLR Camera Steven M. Scharf Digital Photography 14 05-12-2004 02:33 PM
Cisco Fast Etherchannel and Intel Pro/1000MT Quad - TX Unicast Not Load Balanced Nikolai Schupbach Cisco 0 02-23-2004 09:00 AM



Advertisments