Hello, Olivier Andrieu wrote: > 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,
Oops... stupid mistake. I was thinking of trie structures that I am working on now. You are absolutely correct. Everything makes sense now. > 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 ? > Basically the same thing. You can find the relevant article here: http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=139478 Deterministic skip lists J. Ian Munro Thomas Papadakis Robert Sedgewick Symposium on Discrete Algorithms archive Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms table of contents Orlando, Florida, United States Pages: 367 - 375 Year of Publication: 1992 ISBN:0-89791-466-X > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
