Re: van Emde Boas hash.

[tomas@tuxteam.de]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Fri, Nov 20, 2009 at 07:41:15AM +0100, A. Soare wrote:
> 
> Van Emde Boas arrays are hashed arrays [...]
> 
> For example, for an array of length 2^32, the complexity is O(0), and
> the number of steps is less than log_2 (32) = "maximum 5 steps" for every operation.
> 
> The operations are:
> 
> * insert a new number
> * delete a number
> * seek for a number
> * find the successor of a number
> * find the predecessor of a number

If  I understood the Wikipedia page correctly (thnks, Deniz), you
can find "next" and "previous" to a number not in the hash? Then
they look like a good candidate to represent markers and boundaries of
overlays, no?

Regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFLCgpZBcgs9XrR2kYRAvh6AJ9TxH4v/4jFSN90gK/X/QHgJQuf/wCfUYYU
mZjOWuTH3spYQJWvZ3HtWzg=
=7Ccl
-----END PGP SIGNATURE-----