On Apr 26, 2:35 am, "Jeff Baker" <algort...@[EMAIL PROTECTED]
> wrote:
> In reading about <set> it is described as a binary tree without
duplicates.
> Why is it a binary tree rather then a linear tree. Is this really just
the
> same?
No, the performance of a linear list would degrade linearly as items
are added to the container, whereas the performance of a binary tree
would degrade logarithmically as more items are added. In other words,
there is a tremendous difference between a linear list and a binary
tree.
> Why not a straight line from top to bottom?
Consider the average number of comparisons needed to find a particular
item in a linear list versus a binary tree. For a container with, say,
64 items, a linear search would require on average 32 comparisons to
find the requested element - whereas a binary tree would average
around five comparisons - just one sixth as many. For a container with
1,024 elements, a linear list would need on average 512 comparisons to
find an item - whereas a binary tree would avere just nine (a fifty-
six fold difference). And by the time the container has grown to
1,048,576 items, searching for an item in the binary tree (19
comparisons on average) is about twenty-thousand times faster than
searching for the same item in the linear list (which would require
524,288 comparisons on average).
Greg
--
[ See http://www.gotw.ca/resources/clcm.htm
for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
