Friday, January 9, 2009

Generic Skip list (skiplist)

Skip lists are an interesting randomize data structure for storing pairs of . Skip lists have logaritmic search and insertion time. Here I sketch a generic skip list code
Pubblicato da a

5 comments:

  1. AnonymousMarch 23, 2009 at 1:21 AM

    The right grammar should be that "skip lists are a ..."

    ReplyDelete
  2. codingplaygroundMarch 23, 2009 at 4:14 AM

    more precisely: "are an interesting"

    ReplyDelete
  3. AnonymousMay 30, 2009 at 4:11 AM

    if ((tk == 0) || // null?
    ( key < tk->key_)) // search key < next level link's key

    Is not correct. C++ does not guarantee left to right evaluation and so this may result in a segmentation fault depending on the compiler.

    ReplyDelete
  4. gpdJune 18, 2009 at 5:50 AM

    @anonymous:

    of course it does for && and ||: it is called shortcut evaluation, and test for null OR dereference is idiomatic both in C and C++.

    ReplyDelete
  5. floJanuary 20, 2011 at 5:30 AM

    I believe you have a bug in your search__ function:

    if ((x == 0)) ||
    (key < x->val_))

    Shouldn't this read:

    if ((x == 0)) ||
    (key < x->key_))

    ?

    ReplyDelete

Subscribe to: Post Comments (Atom)