RE: [Dev-C++] 'extern const' and std::vector

[Per W. <pw...@ia...>]

That's the logaritmic search time.

If the tree is binary, every step down the tree halves the alternative,
similar to the bsearch() function available in ISO 9899.

If the tree is of higher order, i.e. more than two alternatives at heach
level, it will subdivide the alternatives faster.

If there are 32 values at each level, each level will do a 2^5
subdivision. A 6-level tree would hold up to 2^(5*6) entries. Max 6 tree
nodes to test for locating a single entry among 1 billion alternatives.

Too bad that all insert/remove operations also takes O(log n) for a total
of O(n*log n) time to populate the tree. But then again, O(n*log n) is the
expected efficiency for a general sort.

Check out libredblack at sourceforge. A red-black tree is an improvement
of the trusty btree, with a built-in hysteresis when a tree has to grow
with one more level, or shrunk one level.

Because of the good behaviour, it isn't uncommon that the stl map template
is implemented with a red-black tree.

/Per W

On Thu, 1 May 2003, Ioannis Vranos wrote:

> > -----Original Message-----
> > From: Per Westermark [mailto:pw...@ia...]
> > Sent: Thursday, May 01, 2003 8:23 PM
> > To: Ioannis Vranos
> > Cc: dev...@li...
> > Subject: RE: [Dev-C++] 'extern const' and std::vector
> >
> >
> > I assume MMORPG is Massive Multiplayer Online Role-Playing Game.
> >
> > If the game isn't too boring, I'm also assuming that you don't walk
> > through the rooms in a sequential order.
> >
> > If you need random access, I would really go for a tree
> > construct. Each
> > node might point zero more alternative rooms, while you would still be
> > able to locate a room in O(log n) time.
> >
> > If the tree for some reason gets too large to keep in memory, it might
> > easily be placed partially on disk.
>
>
>
> I do not know much about trees but how can one have random access in a tree?
> Trees involve sequential comparisons, don't they?
>
>
>
>
> Ioannis Vranos
>
> * Programming pages: http://www.noicys.freeurl.com
> * Alternative URL 1: http://run.to/noicys
> * Alternative URL 2: http://www.noicys.cjb.net
>
>
>
>
> -------------------------------------------------------
> This sf.net email is sponsored by:ThinkGeek
> Welcome to geek heaven.
> http://thinkgeek.com/sf
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>