Design and Analysis of Algorithms

694 Design and Analysis of Algorithms

It makes the coding simpler if we create a level 16 sentinel node, called nil, which holds a key value

that is larger than any legal key. This makes the code simpler, since we do not need to worry about checking

for NULL values as we traverse the skip list.

One of the advantages of a skiplist is that the shortcut lists are not decided by the nature of the data (that

is, key values), but by a random number generator. Thus its performance cannot be affected by the data set,

even if someone purposefully tries to feed such adversary data.

C.10 HASH TABLES

We have seen various data structures (for example, binary trees, AVL trees, splay trees, skip lists) that can

perform the dictionary operations insert(), delete() ...