Skip list
Definition
Searching in a dictionary of n number pairs described by an ordered linked list requires at most n key comparisons. If a pointer is added to the middle node of the linked list, the number of comparisons can be reduced to n/2 + 1. At this time, in order to find a number pair, first compare it with the middle number pair. If the number of key pairs to be searched is relatively small, the search will only continue in the left half of the linked list; otherwise, the search will continue in the right half of the linked list.
There is a set of hierarchical linked lists in the skip list structure. Level 0 linked list contains all pairs, and the number pairs of level 1 linked list are a subset of the number pairs of level 0 linked list. The number pairs of the i-level linked list are a subset of the number pairs of the i-1 level linked list.
Allocation at insert time
In the regular skip list structure, the ratio of the number of number pairs in the i-1 level linked list to the number of number pairs in the i-level linked list is a fraction p. Therefore, the probability that a number pair belonging to level i-1 linked list also belongs to level i linked list is p. Assume that a unified random number generator is used to generate real numbers between 0 and 1. The probability of the generated random number <= p is p. If the next random number <= p, the new number corresponds to the level 1 linked list. To determine whether the number pair is on the level 2 linked list, it is determined by the next random number. If the new random number <= p, then the element also belongs to the level 2 linked list. Repeat this process until a random number > p.
This method has potential shortcomings. The series assigned to some number pairs may be particularly large, far exceeding
l
o
g
1
/
p
N
log_{1/p}N
log1/p?N, where N is the maximum expected number of dictionary pairs. To avoid this situation, you can set an upper limit for the series maxLevel. The maximum value is:
?
l
o
g
1
/
p
N
?
?
1
\lceil log_{1/p}N \rceil-1
?log1/p?N1
This method also has a disadvantage. Even if the upper limit of the series maxLevel is used, there may be a situation where there are 3 linked lists before inserting a new number pair, and there are 10 linked lists after inserting. In other words, although there are no number pairs in the level 3 to level 8 linked lists, the new number pairs are assigned to the level 9 linked lists. In other words, there are no level 3~8 linked lists before and after the insertion. Because these empty-level linked lists are of no benefit, we can adjust the linked list level of new records to 3.
Time complexity
The average time complexity of search, insertion, and deletion operations is O(logn), and the worst time complexity is O(n + maxLevel).
Exercise questions
[Exercise 9] Expand the skipList class, add a delete method, delete the node with the smallest keyword, and delete the node with the largest keyword. Calculate the complexity of each method?
Code
Each node has a value, and there is also an array that stores the pointer of each level of the key-value pair. If the key-value pair belongs to the highest level, then the key-value pair also belongs to other levels below the highest level; so the pointer of each node The array is the highest level + 1 (there is also level 0) size.
main.cpp
#include <iostream>
#include "_24skipList.h"
int main() {<!-- -->
skipListTest();
return 0;
}
_24skipList.h
/*
Project name: allAlgorithmsTest
Last modified Date: August 23, 2022 10:18
Last Version: V1.0
Descriptions: Jump table class---randomly determine the level, the level when inserting, and the level now---Header file
Save time when searching
*/
#pragma once
#ifndef _SKIPLIST_H_
#define _SKIPLIST_H_
#include <iostream>
#include <cmath>
#include <sstream>
#include <string>
#include <cstdlib>
#include "_1myExceptions.h"
#include "_23dictionary.h"
#include "_24skipNode.h"
using namespace std;
/*Test function*/
void skipListTest();
template<class K, class E>
class skipList : public dictionary<K, E>
{<!-- -->
public:
skipList(K largeKey, int maxPairs = 10000, float prob = 0.5);
~skipList();
bool empty() const {<!-- --> return dSize == 0; }
int size() const {<!-- --> return dSize; }
pair<const K, E>* find(const K & amp;) const;
void erase(const K & amp;);
void insert(const pair<const K, E> & amp;);
void deleteFront();
void deleteBack();
/*Friend function*/
/*Input dictionary*/
istream & amp; input(istream & amp; in);
// friend istream & amp; operator>> <K, E>(istream & amp; in, skipList<K, E> & amp; m);
/*Output dictionary*/
ostream & amp; output(ostream & amp; out) const;
// friend ostream & amp; operator<< <K, E>(ostream & amp; out, const skipList<K, E> & amp; m);
protected:
float cutOff; // used to decide level number--used to determine the number of layers
int level() const; // generate a random level number
int levels; // max current nonempty chain
int dSize; // number of pairs in dictionary
int maxLevel; // max permissible chain level
K tailKey; // a large key
skipNode<K, E>* search(const K & amp;) const;
// search saving last nodes seen
skipNode<K, E>* headerNode; // header node pointer
skipNode<K, E>* tailNode; // tail node pointer
skipNode<K, E>** last; // last[i] = last node seen on level i
};
/*Input dictionary*/
template<class K, class E>
istream & amp; skipList<K, E>::input(istream & amp; in)
//istream & amp; operator>>(istream & amp; in, skipList<K, E> & amp; m)
{<!-- -->
int numberOfElement = 0;
cout << "Please enter the number of element:";
while (!(in >> numberOfElement))
{<!-- -->
in.clear();//Clear the flag bit
while (in.get() != '\\
')//Delete invalid input
continue;
cout << "Please enter the number of element:";
}
K first;
E second;
for (int i = 0; i < numberOfElement; i + + )
{<!-- -->
cout << "Please enter the element " << i + 1 << ":";
while (!(in >> first >> second))
{<!-- -->
in.clear();//Clear the flag bit
while (in.get() != '\\
')//Delete invalid input
continue;
cout << "Please enter the element " << i + 1 << ":";
}
const pair<const K, E> element(first, second);
insert(element);
}
return in;
}
template<class K, class E>
istream & amp; operator>>(istream & amp; in, skipList<K, E> & amp; m){<!-- -->
m.input(in);
return in;
}
/*Output dictionary*/
template<class K, class E>
ostream & amp; skipList<K, E>::output(ostream & amp; out) const
//ostream & amp; operator<<(ostream & amp; out, const skipList<K, E> & amp; m)
{<!-- -->
skipNode<K, E>* currentNode = headerNode->next[0];
while (currentNode != tailNode)
{<!-- -->
out << *currentNode;
currentNode = currentNode->next[0];
}
cout << endl;
return out;
}
template<class K, class E>
ostream & amp; operator<<(ostream & amp; out, const skipList<K, E> & amp; m){<!-- -->
m.output(out);
return out;
}
/*Constructor*/
template<class K, class E>
skipList<K, E>::skipList(K largeKey, int maxPairs, float prob)
{<!-- -->
/*RAND_MAX This is a macro definition, which is the maximum value of random numbers generated, in the stdlib header file*/
/*prob is usually 0.5*/
cutOff = prob * RAND_MAX;
/*ceil() function represents rounding down, logf() function represents taking logarithm, maxPairs represents the maximum number of pairs*/
maxLevel = (int)ceil(logf((float)maxPairs) / logf(1 / prob)) - 1; //Maximum number of layers allowed
levels = 0; //The initial number of non-empty levels is 0
dSize = 0; //Initial jump table size is 0
tailKey = largeKey;//Indicates the maximum key value
// create header & tail nodes and last array
pair<K, E> tailPair;
tailPair.first = tailKey;
headerNode = new skipNode<K, E>(tailPair, maxLevel + 1);//Create the head node
tailNode = new skipNode<K, E>(tailPair, 0);//Create tail node
last = new skipNode<K, E> *[maxLevel + 1];//last[i] represents the last node of layer i
// In the initial state, the head nodes of all i-level linked lists point to the tail nodes
for (int i = 0; i <= maxLevel; i + + )
headerNode->next[i] = tailNode;
}
/*Delete all nodes and pointer array last*/
template<class K, class E>
skipList<K, E>::~skipList()
{<!-- -->// Delete all nodes and array last.
skipNode<K, E>* nextNode;
/*It must be executed once because there is a head node. */
while (headerNode != tailNode)
{<!-- -->
nextNode = headerNode->next[0];
delete headerNode;
headerNode = nextNode;
}
delete tailNode;
delete[] last;
}
/*Returns a pointer to the matching number pair; if there is no matching number pair, returns nullptr*/
template<class K, class E>
pair<const K, E>* skipList<K, E>::find(const K & amp; theKey) const
{<!-- -->
if (theKey >= tailKey)
return nullptr; // no matching pair possible
// position beforeNode just before possible node with theKey
skipNode<K, E>* beforeNode = headerNode;
for (int i = levels; i >= 0; i--) // go down levels
// follow level i pointers
while (beforeNode->next[i]->element.first <theKey)
beforeNode = beforeNode->next[i];
// check if next node has theKey
if (beforeNode->next[0]->element.first == theKey)
return &beforeNode->next[0]->element;
return nullptr; // no matching pair
}
template<class K, class E>
int skipList<K, E>::level() const
{<!-- -->// Return a random level number <= maxLevel.
int lev = 0;
while (rand() <= cutOff)
lev + + ;
return (lev <= maxLevel) ? lev : maxLevel;
}
/*Search for the keyword theKey and store the last node to be viewed in each level of the linked list in the array last*/
/*Return the node containing the keyword theKey*/
/*The position beforeNode is the rightmost position before the node with the key word theKey*/
template<class K, class E>
skipNode<K, E>* skipList<K, E>::search(const K & amp; theKey) const
{<!-- -->
skipNode<K, E>* beforeNode = headerNode;
for (int i = levels; i >= 0; i--)
{<!-- -->
while (beforeNode->next[i]->element.first <theKey)
beforeNode = beforeNode->next[i];
last[i] = beforeNode; //The node before theKey keyword
}
return beforeNode->next[0];//The return value is in level 0. It is very likely that it is a node with theKey as a keyword, or a node that is larger than its key value.
}
/*Insert element thePair into the linked list. If there is no element with the same keyword as thePair in the linked list, insert it, otherwise update the corresponding value of the keyword*/
template<class K, class E>
void skipList<K, E>::insert(const pair<const K, E> & amp; thePair)
{<!-- -->
/*When the key value exceeds the maximum key value*/
if (thePair.first >= tailKey) // key too large
{<!-- -->
ostringstream s("");
s << "Key = " <<thePair.first << " Must be < " << tailKey;
throw illegalParameterValue(s.str());
}
/*When the key value of thePair already exists, update the value corresponding to the key*/
skipNode<K, E>* theNode = search(thePair.first);
if (theNode->element.first == thePair.first)
{<!-- -->
theNode->element.second = thePair.second;
return;
}
/*When the key value does not exist, determine the level i*/
int theLevel = level(); //Randomly calculate the level of the new node
/*If the level is greater than the number of non-empty levels, correct it*/
if (theLevel > levels)
{<!-- -->
theLevel = + + levels;
last[theLevel] = headerNode;
}
/*Store the new node after theNode*/
skipNode<K, E>* newNode = new skipNode<K, E>(thePair, theLevel + 1);
for (int i = 0; i <= theLevel; i + + )
{<!-- -->// insert into level i chain
newNode->next[i] = last[i]->next[i];
last[i]->next[i] = newNode;
}
dSize++;
return;
}
template<class K, class E>
void skipList<K, E>::erase(const K & amp; theKey)
{<!-- -->// Delete the pair, if any, whose key equals theKey.
if (theKey >= tailKey) // too large
return;
// see if matching pair present
skipNode<K, E>* theNode = search(theKey);
if (theNode->element.first != theKey) // not present
return;
//delete node from skip list
for (int i = 0; i <= levels & amp; & amp; last[i]->next[i] == theNode; i + + )
last[i]->next[i] = theNode->next[i];
// update levels
while (levels > 0 & amp; & amp; headerNode->next[levels] == tailNode)
levels--;
delete theNode;
dSize--;
}
/*Exercise 9: Delete the node with the smallest keyword*/
template<class K, class E>
void skipList<K, E>::deleteFront()
{<!-- -->
if (dSize == 0)
return;
/*Find the node with the smallest keyword*/
skipNode<K, E>* frontNode = headerNode->next[0];
/*Delete the node at each level*/
for(int i = 0;i <= levels & amp; & amp; headerNode->next[i] == frontNode;i + + )
headerNode->next[i] = frontNode->next[i];
/*update levels*/
while (levels > 0 & amp; & amp; headerNode->next[levels] == tailNode)
levels--;
delete frontNode;
dSize--;
}
/*Exercise 9: Delete the node with the largest keyword*/
template<class K, class E>
void skipList<K, E>::deleteBack()
{<!-- -->
/*Find the node with the largest keyword*/
skipNode<K, E>* deleteBack = headerNode;
for (int i = levels; i >= 0; i--)
{<!-- -->
while (deleteBack->next[i]->element.first < tailKey)
deleteBack = deleteBack->next[i];
}
/*Find the element address before deleteBack at each level*/
search(deleteBack->element.first);
/*Delete the node at each level*/
for (int i = 0; i <= levels & amp; & amp; last[i]->next[i] == deleteBack; i + + )
last[i]->next[i] = deleteBack->next[i];
/*Update levels*/
while (levels > 0 & amp; & amp; headerNode->next[levels] == tailNode)
levels--;
delete deleteBack;
dSize--;
}
#endif
_24skipList.cpp
/*
Project name: allAlgorithmsTest
Last modified Date: August 23, 2022 10:18
Last Version: V1.0
Descriptions: Jump table class---randomly determine what level it is, what level it is when inserting, and what level it is now---cpp file
*/
#include <iostream>
#include "_24skipList.h"
using namespace std;
void skipListTest()
{<!-- -->
cout << endl << "************************************skipListTest() function starts**** ***********************************" << endl;
//Test input and output
cout << endl << "Test input and output*************************************** ****" << endl;
cout << "Input and output**********************" << endl;
skipList<int, int> a(20);
cin >> a;
cout << "The dictionary is " << a;
cout << endl << "Test member function****************************************** ****" << endl;
cout << "empty()******************************" << endl;
cout << "a.empty() = " << a.empty() << endl;
cout << "size()******************************" << endl;
cout << "a.size() = " << a.size() << endl;
cout << "find()******************************" << endl;
cout << "Element associated with 1 is " << a.find(1)->second << endl;
cout << "insert()************************" << endl;
pair<const int, int> insertData(4, 4);
a.insert(insertData);
cout << "The dictionary is " << a;
cout << "erase()************************" << endl;
a.erase(1);
cout << "The dictionary is " << a;
cout << "deleteFront()************************" << endl;
a.deleteFront();
cout << "The dictionary is " << a;
cout << "deleteBack()**********************" << endl;
a.deleteBack();
cout << "The dictionary is " << a;
cout << "************************************skipListTest() function ends****** ************************************" << endl;
}
_23dictionary.h
/*
Project name: allAlgorithmsTest
Last modified Date: August 22, 2022 09:17
Last Version: V1.0
Descriptions: Abstract class for dictionary
*/
/*
pair:
Introduction: It combines 2 data into a set of data, which is a structure. The two main member variables, first and second, store two pieces of data respectively.
Usage: Use the std namespace to introduce the pair std::pair
*/
#pragma once
#ifndef _DICTIONARY_H_
#define _DICTIONARY_H_
using namespace std;
template<class K,class E>
class dictionary
{<!-- -->
public:
virtual ~dictionary() {<!-- -->}
/*Returns true if and only if the dictionary is empty*/
virtual bool empty() const = 0;
/*Return the number of pairs in the dictionary*/
virtual int size() const = 0;
/*Return a pointer to the matching pair*/
virtual pair<const K, E>* find(const K & amp;) const = 0;
/*Delete matching pairs*/
virtual void erase(const K & amp;) = 0;
/*Insert a number pair into the dictionary*/
virtual void insert(const pair<const K, E> & amp;) = 0;
};
#endif
_24skipNode.h
/*
Project name: allAlgorithmsTest
Last modified Date: August 23, 2022 10:18
Last Version: V1.0
Descriptions: Jump list structure
// node type used in skip lists
// node with a next and element field; element is a pair<const K, E>
// next is a 1D array of pointers
*/
#pragma once
#ifndef _SKIPNODE_H_
#define _SKIPNODE_H_
template <class K, class E>
struct skipNode
{<!-- -->
typedef pair<const K, E> pairType;
pairType element;
skipNode<K, E>** next; // 1D array of pointers
skipNode(const pairType & amp; thePair, int size)
:element(thePair) {<!-- -->
next = new skipNode<K, E>*[size];
}
friend ostream & amp; operator<<(ostream & amp; out, skipNode<K, E> & amp; m)
{<!-- -->
out << "(" << m.element.first << " ," << m.element.second << ")" << " ";
return out;
}
};
#endif
_1myExceptions.h
/*
Project name: allAlgorithmsTest
Last modified Date: 17:38 on August 13, 2022
Last Version: V1.0
Descriptions: Comprehensive various anomalies
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include <string>
#include<iostream>
using namespace std;
// illegal parameter value
class illegalParameterValue
{<!-- -->
public:
illegalParameterValue(string theMessage = "Illegal parameter value")
{<!-- -->message = theMessage;}
void outputMessage() {<!-- -->cout << message << endl;}
private:
string message;
};
// illegal input data
class illegalInputData
{<!-- -->
public:
illegalInputData(string theMessage = "Illegal data input")
{<!-- -->message = theMessage;}
void outputMessage() {<!-- -->cout << message << endl;}
private:
string message;
};
//illegal index
class illegalIndex
{<!-- -->
public:
illegalIndex(string theMessage = "Illegal index")
{<!-- -->message = theMessage;}
void outputMessage() {<!-- -->cout << message << endl;}
private:
string message;
};
//matrix index out of bounds
class matrixIndexOutOfBounds
{<!-- -->
public:
matrixIndexOutOfBounds
(string theMessage = "Matrix index out of bounds")
{<!-- -->message = theMessage;}
void outputMessage() {<!-- -->cout << message << endl;}
private:
string message;
};
//matrix size mismatch
class matrixSizeMismatch
{<!-- -->
public:
matrixSizeMismatch(string theMessage =
"The size of the two matrics doesn't match")
{<!-- -->message = theMessage;}
void outputMessage() {<!-- -->cout << message << endl;}
private:
string message;
};
// stack is empty
class stackEmpty
{<!-- -->
public:
stackEmpty(string theMessage =
"Invalid operation on empty stack")
{<!-- -->message = theMessage;}
void outputMessage() {<!-- -->cout << message << endl;}
private:
string message;
};
// queue is empty
class queueEmpty
{<!-- -->
public:
queueEmpty(string theMessage =
"Invalid operation on empty queue")
{<!-- -->message = theMessage;}
void outputMessage() {<!-- -->cout << message << endl;}
private:
string message;
};
// hash table is full
class hashTableFull
{<!-- -->
public:
hashTableFull(string theMessage =
"The hash table is full")
{<!-- -->message = theMessage;}
void outputMessage() {<!-- -->cout << message << endl;}
private:
string message;
};
// edge weight undefined
class undefinedEdgeWeight
{<!-- -->
public:
undefinedEdgeWeight(string theMessage =
"No edge weights defined")
{<!-- -->message = theMessage;}
void outputMessage() {<!-- -->cout << message << endl;}
private:
string message;
};
// method undefined
class undefinedMethod
{<!-- -->
public:
undefinedMethod(string theMessage =
"This method is undefined")
{<!-- -->message = theMessage;}
void outputMessage() {<!-- -->cout << message << endl;}
private:
string message;
};
#endif