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? Note that I have to backtrack on this structure and need to use a simple backtracking iterator hence my considering skip-lists (I need only keep one reference to the current list position and visit each such element once). > 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? Regards, Hugo F. > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
