On 5/9/07, Hugo Ferreira <[EMAIL PROTECTED]> wrote: > Olivier, > > Olivier Andrieu wrote: > > On 5/7/07, Hugo Ferreira <[EMAIL PROTECTED]> wrote: > >> Hello, > >> > >> Olivier Andrieu wrote: > >>> On 5/7/07, Hugo Ferreira <[EMAIL PROTECTED]> wrote: > > snip... > >> My understanding is that (imperative) Skip lists have the performance of > >> balanced trees but also allow for iterating over all elements in O(N), > >> which is what I want (but not necessarily in order). > > > > Balanced trees also allow for iterating over all elements in O(N) ! > > > > Ok, I confess my ignorance. Apologies if this is a stupid question. How > is this possible? > > To reach all leaf nodes don't I have to visit each non-leaf node at > least once (at most twice). And aren't their SUM(i=0 to log(N)) 2^i > nodes in the tree? If so don't I have to visit all > SUM(i=0 to log(N)) 2^i nodes?
but the data isn't stored in leaf nodes, and furthermore the tree isn't complete (ie all leaves do not have the same depth). Anyway, have a look at the set.ml file in the standard library: http://camlcvs.inria.fr/cgi-bin/cvsweb/ocaml/stdlib/set.ml?rev=1.19 type t = Empty | Node of t * elt * t * int let rec iter f = function Empty -> () | Node(l, v, r, _) -> iter f l; f v; iter f r > > The advantage of skip lists IMO is that they are easy to understand > > and implement, that's all. > > Well, for the doubly linked list version I agree. The use of the > sentinel references demands some care though. BTW are you aware that > their is a deterministic version of the skip list? no, what does it look like ? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "ocaml-developer" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/ocaml-developer?hl=en For other OCaml forums, see http://caml.inria.fr/resources/forums.en.html -~----------~----~----~----~------~----~------~--~---
