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
Reazioni: 

5 comments:

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

    ReplyDelete

  2. more precisely: "are an interesting"

    ReplyDelete

  3. 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. @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. 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)