directory

    • Writing in the front
    • Jump table profile
    • To find the steps
    • Insert the steps
    • Remove steps
    • The complete code

Writing in the front

For more information about hoppers, see this article. It is best to read this article before looking at the detailed ideas -> Code replay steps: Skiplist insert and delete from linked lists. Insert and delete from linked lists. 【 Data structure foundation notes 】【 linked list 】 related code and other language writing method or other ideas can refer to: 1206. Design skip table code reference link: leetcode-cn.com/problems/de… www.iteye.com/blog/kenby-…

Jump table profile

The skip table uses a random method to determine which nodes in the linked list should have forward Pointers and how many Pointers should be added to that node. The head node of a hop table structure needs to have enough pointer fields to allow for the largest possible progression, while the tail node does not need pointer fields. Skip table in the original ordered linked list added multi-level index, through the index to achieve fast search. 2. Move to the lower level index and continue the search until you reach the lower level. If the search element exists, you are very close to the search element.

To find the steps

What you need to know:

Set head as upper left corner; initialize prevs array; find only right and Down directions; Maxlevel may be updated with the number of random levels generated when new nodes are inserted. But always: maxlevel <= maxlevel

Here’s an example: You should get a good idea of what the Prevs array means.



Traversing from top to bottom:





Code like this can be written along these lines:

vector<Node*> _search(int key)
{
	Node* cur = &head;
	vector<Node*> prevs(MAX_LEVEL);
	// The maxlevel is the maximum number of layers in the current table, not the limit of the original maxlevel.
	// Maxlevel may be updated with the number of random levels generated when new nodes are inserted.
	for(int i = maxlevel- 1; i >=0; i--) {// Compare in the current layer until the search element is less than key
		while(cur->level[i] && cur->level[i]->val < key)
			cur = cur->level[i];
		// Find the nearest point on each floor as the turning point downward
		prevs[i] = cur;
	}
	return prevs;
}

bool search(int target)
{
	// Get the first (lowest) node closest to key with val less than key
	Node* prev = _search(target)[0];
	return prev->level[0] && prev->level[0]->val == target;
}
Copy the code

Insert the steps

Prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs); prevs (prevs) If a node has a pointer to level I (I >=1) (that is, the node is already in the list from level 1 to level I), then the probability that it has a pointer to level (I +1) is p. The maximum number of layers of a node cannot exceed a maximum value, denoted as MaxLevel.

static int random_level(a) {
    int level = 1;
    while (rand() < SKIPLIST_P_VAL && level < MAX_LEVEL) level++;
    return level;
}
Copy the code

The pseudo-code for randomLevel() contains two parameters, p and MaxLevel. In the Skiplist implementation of Redis, the values of these two parameters are:

p = 1/4

MaxLevel = 32

Prevs []; prevs[]; prevs[]; prevs[]; prevs[];

As shown in the figure below: When the number of inserts is 2 and the number of randomly generated layers is 5, the nodes smaller than num in the new layer must be the headers.



Create a new node (num, level)

5, For each layer, a new node is inserted, so the original index relationship is changed:

Prevs’ successor in this layer as cur’s successor in this layer, and prevs’ successor as cur’s successor in this layer:

Take layer 0 for example



Prevs [I]; prevs[I]; prevs[I]; prevs[I];

Code:

void add(int num)
{
	<=num <=num <=num <=num <=num <=num
	auto prevs = _search(num);
	//2. Randomly generate the number of layers of this node
	int level = random_level(a);//3, update the maximum number of hops in the current table maxlevel, and
	if(level > maxlevel)
	{
		for(int i = maxlevel; i < level; i++)
			prevs[i] = &head;
		maxlevel = level;
	}
	Node* cur = new Node(num,level);
	//
	for(int i = level - 1; i >= 0; i--) { cur->level[i] = prevs[i]->level[i]; Prevs [I] - > level [I] = cur; }}Copy the code

Remove steps

Prevs = prevs; prevs = prevs; prevs = prevs; prevs = prevs; prevs = prevs; Prevs does not exist in the list, or the prevs does not exist in the list. Prevs does not exist in the list, or the prevs does not exist in the list. Prevs [0]->level[0]; prevs[0]->level[0]; Prevs is the successor of the prevs node, then add the successor of del to prevs as the successor of the new prevs node. If there are no successors to the maxLevel-1 header, there are no other nodes in this layer

bool erase(int num) 
{
	  Prevs = prevs; prevs = prevs; prevs = prevs; prevs = prevs
      auto prevs = _search(num);
      Prevs does not exist in the original list, or the prevs value does not equal num
      if(! prevs[0]->level[0] || prevs[0]->level[0]->val ! = num)return false;
      Prevs [0]->level[0]
      Node * del = prevs[0]->level[0];
      //4, the next step is to change the relationship between the nodes of num before and after the nodes of num.
      for (int i = 0; i < maxlevel; i++)
      	  Prevs: prevs: prevs: prevs: prevs: prevs
          if (prevs[i]->level[i] == del)
              prevs[i]->level[i] = del->level[i];
      // Free up space
      delete del;
      // Deleting a node may require updating the current maximum number of layers (if the node is deleted from the previous maximum number of layers)
      // If there is no successor of the maxlevel-1 node, there are no other nodes in this layer.
      while (maxlevel > 1 && !head.level[maxlevel - 1])
          maxlevel--;
      return true;
}
Copy the code

The complete code

Split member data and functions into private and public partitions:

class Skiplist {
private:
    // Define the node
    struct Node {
        int val;
        vector<Node *> level;
        Node(int val, int size = MAX_LEVEL) : val(val), level(size) {}
    };
    // Define parameters for the number of layers of random nodes
    static const int SKIPLIST_P_VAL = RAND_MAX / 4, MAX_LEVEL = 32;
    // Define the header
    Node head;
    // Define the current maximum number of layers
    int maxlevel = 1;
    // Define the search subfunction
    vector<Node*> _search(int key) 
    {
        Node* cur = &head;
        vector<Node *> prevs(MAX_LEVEL);
        // through every level, from top to bottom
        for (int i = maxlevel - 1; i >= 0; i--) 
        {
            // through elements in the current level with smaller value
            while (cur->level[i] && cur->level[i]->val < key)
                cur = cur->level[i];
            prevs[i] = cur;
        }
        return prevs;
    }
    // Define a random generation layer subfunction
    static int random_level(a) {
        int level = 1;
        while (rand() < SKIPLIST_P_VAL && level < MAX_LEVEL) level++;
        return level;
    }

public:
    // When initializing the hop table, we also need to initialize the head
    Skiplist() : head(INT_MIN, MAX_LEVEL) {}
    
    bool search(int target) {
        Node* prev = _search(target)[0];
        return prev->level[0] && prev->level[0]->val == target;
    }
    
    void add(int num) {
        auto prevs = _search(num);
        int level = random_level(a);if (level > maxlevel) {
            for (int i = maxlevel; i < level; i++)
                prevs[i] = &head;
            maxlevel = level;
        }
        Node * cur = new Node(num, level);
        for (int i = level - 1; i >= 0; i--) { cur->level[i] = prevs[i]->level[i]; prevs[i]->level[i] = cur; }}bool erase(int num) {
        auto prevs = _search(num);
        if(! prevs[0]->level[0] || prevs[0]->level[0]->val ! = num)return false;
        Node * del = prevs[0]->level[0];

        for (int i = 0; i < maxlevel; i++)
            if (prevs[i]->level[i] == del)
                prevs[i]->level[i] = del->level[i];
        delete del;

        while (maxlevel > 1 && !head.level[maxlevel - 1])
            maxlevel--;

        return true; }};/** * Your Skiplist object will be instantiated and called as such: * Skiplist* obj = new Skiplist(); * bool param_1 = obj->search(target); * obj->add(num); * bool param_3 = obj->erase(num); * /
Copy the code