Skip List Runtime on dictionay operation compared to Splay Trees and Hash Tables. (Coded in Java)
Skip lists are a relatively new data structure. This is an ordered list where the nodes are connected together at multiple levels. Different levels of connected nodes need not be uniform. This allows the skip list to skip items during a search. Each level is an ordered list in itself. Every node has a level and is connected to different nodes in the same level. This allows data structure operations to skip through the list. Example is the following list where there are two levels.
Level 1 connections E ----------> X
Level 0 connections A ->; B -> E -> F -> G->X -> Y -> Z
Level 0 list is the same as a linked list. E has connections has two levels. If a search was for say 'G'. The algorithms is as follows Start at Level 1, X > F so we move down at 'E' and then proceed at level 0 from E till G is found. Nodes A and B were skipped.
SkipList Search Algorithm:
1) Start from the top level proceed until level 0
a) Move to the right until a node with node Key < search Key
b) Jump to the next lower level.
2) If 1a resulted in an exit in level 0, the next node could be the search node. else it is absent.
Skip lists are a relatively new data structure. This is an ordered list where the nodes are connected together at multiple levels. Different levels of connected nodes need not be uniform. This allows the skip list to skip items during a search. Each level is an ordered list in itself. Every node has a level and is connected to different nodes in the same level. This allows data structure operations to skip through the list. Example is the following list where there are two levels.
Level 1 connections E ----------> X
Level 0 connections A ->; B -> E -> F -> G->X -> Y -> Z
Level 0 list is the same as a linked list. E has connections has two levels. If a search was for say 'G'. The algorithms is as follows Start at Level 1, X > F so we move down at 'E' and then proceed at level 0 from E till G is found. Nodes A and B were skipped.
SkipList Search Algorithm:
1) Start from the top level proceed until level 0
a) Move to the right until a node with node Key < search Key
b) Jump to the next lower level.
2) If 1a resulted in an exit in level 0, the next node could be the search node. else it is absent.
Here is a skip list implementation holding values A to Z. The nodes encountered during the search for H and M are shown.
Level 2 Skip List.
Level 6 Skip List
In order for the list to be helpful level at each node needs to be decided at Random during the insert operation of that node. The maximum level that is useful in a skip list is ln N -1 where N is the number of items expected to go into the skip list.
Algorithm Inserting in to the Skip List
1 Find the node as in search. This will return the node that will be to the left of the new node (L).
a) While dropping down to the lower levels maintain the nodes in an update List.
2 Create the new node with a random level.
3 Adjust the pointers from the existing L node to the new node.If the new level is greater than the existing level of the list, then the head of the list should be adjusted to point to the new node at the new level.
4 Set the next pointers of the new node to next pointers of L
5 Set next pointers of L to the new node at that level. This is done for each node where level was changed in step 1.
For example in the case of
Level 1 connections E ----------> X
Level 0 connections A -> B -> E -> G->X -> Y -> Z. We need to insert H with level 3 then, at level 1 we drop down at E and also at G in level 0. So, G->next = H at level 0, E-> next = H at level 1, F -> next = X at level 1 and at level 2 H is linked to head and tail of the list.
Level 2 connections *<-H->*
Level 1 connections E ----------->H-> X
Level 0 connections A -> B -> E -> F -> G->H->X -> Y -> Z
Runtime of Skip Lists: Dictionary operations on skip lists take O(Log(n)) time. Finding each new node's level is done in random as follows
Comparison of Skip List, Splay Binary Search Trees and Hash Table
For a serious input of 56000 word dictionary, the search operations on Skip lists, Splay Trees and Hash Table is as follows. Skip list took 40 comparisons at 11 levels to find the word 'Skip' in the dictionary.
Splay tree took less time than the skip list at
Result: In general skip lists and splay trees can't hold candle to hash tables.
Level 0 connections A -> B -> E -> G->X -> Y -> Z. We need to insert H with level 3 then, at level 1 we drop down at E and also at G in level 0. So, G->next = H at level 0, E-> next = H at level 1, F -> next = X at level 1 and at level 2 H is linked to head and tail of the list.
Level 2 connections *<-H->*
Level 1 connections E ----------->H-> X
Level 0 connections A -> B -> E -> F -> G->H->X -> Y -> Z
Runtime of Skip Lists: Dictionary operations on skip lists take O(Log(n)) time. Finding each new node's level is done in random as follows
Comparison of Skip List, Splay Binary Search Trees and Hash Table
For a serious input of 56000 word dictionary, the search operations on Skip lists, Splay Trees and Hash Table is as follows. Skip list took 40 comparisons at 11 levels to find the word 'Skip' in the dictionary.
Splay tree took less time than the skip list at
Hash Table left the above two way behind in run time
No comments:
Post a Comment