Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to master the jump table of the data structure and algorithm". The content of the explanation in the article is simple and clear, and it is easy to learn and understand. let's study and learn how to master the jump table in the data structure and algorithm.

Data structure and algorithm Note-data structure-Jump Table (skip list)

Jump table code-gitee

Jump table code-github

Keywords

Jump list is a kind of dynamic data structure based on linked list, which can be thought of as adding multi-level index to the nodes of linked list.

The jump table supports fast insert, delete and search operations. The time complexity is O (logn) and the space complexity is O (n).

Skipping table is the design idea of adding index to exchange space for time, and building multi-level index to improve query efficiency.

The time complexity of skipping table is O (logn).

The number of jump tables maintains balance through random functions.

When inserting data, it is necessary to maintain the balance between indexes and nodes, otherwise, in extreme cases, the jump table may degenerate into a linked list.

Table skipping is more flexible and can effectively balance execution efficiency and memory consumption by changing index building strategy.

The jump table has the performance comparable to the red-black tree, but it is much easier to write. In many cases, it can directly replace the red-black tree.

By the operation of finding data according to the interval, the efficiency of the red-black tree is not as high as the jump table. For the operation of finding data by interval, the jump table can do this: the time complexity of O (logn) locates the starting point of the interval, and then traverses back in the original linked list.

Understand the jump table

The binary search method depends on the random access of the time array at the bottom, so it can only be realized by the array.

Linked lists also have a similar binary search operation, called skip list.

Linked list is a dynamic data structure with excellent performance in all aspects, which supports: fast insert, delete, find. It is also easy to write and can even replace the red-black tree.

The ordered list (sorted set) of Redis is implemented using a jump table, because:

Strictly speaking, Redis also uses Hash table's main Redis manual, and the core operation of ordered collections is to insert a data, delete a data, find a data, find data by interval (such as finding data with values between [100,356]), and iteratively output ordered sequences. Among them, insert, delete, search and iterative output ordered sequence of these operations, the red-black tree can also be completed, the time complexity is the same as the jump table. However, according to the operation of finding data by interval, the efficiency of the red-black tree is not as high as the jump table. For the operation of finding data according to the interval, the jump table can locate the starting point of the interval with the time complexity of O (logn), and then traverse the original linked list sequentially. Also, the jump table is more flexible, it can effectively balance execution efficiency and memory consumption by changing the index construction strategy.

Even if the data of the single item linked list is ordered, the specified data should be traversed one by one from the beginning, and the time complexity is O (n).

As shown in the figure:

First-level index

To improve query efficiency, you can build a first-level index on the linked list. Extract one node from every two nodes as an index or index layer

As shown below: the down below represents the pointer to the next node

If you get node 16:

First traversing the index layer, when traversing to the node with the value of 13 in the index layer, it is found that the next node is 17, and that node 16 must be between the two nodes.

Continue to traverse backwards in the original linked list through the index layer and the down pointer of the single

At this point, you only need to traverse two more and one more to find a node with a value equal to 16.

It used to take 16 searches, but now it only needs 7 traverses.

It can be seen that after adding a layer of index, the number of traversing to find a node is greatly reduced, and the search efficiency is improved.

Secondary index

Similar to the way of establishing the first-level index, on the basis of the first-level index, every two nodes extract a node to the second-level index as the second-level index.

To find 16 at this point, you only need to traverse 6 nodes.

As shown in the figure:

When the amount of data is large enough, the query efficiency will be greatly improved. Below is a linked list of 64 nodes. Set up a five-level index.

To find a node with a value of 62, you need to traverse 62 nodes without an index.

Now you only need to traverse 11 nodes.

As shown in the figure:

The structure of the linked list plus multi-level index is the jump table, which can be seen to greatly reduce the number of queries. The optimization of the linked list is obvious.

How fast is the jump table query?

The time complexity of querying specified data in a single linked list is O (n).

In a jump table with multi-level indexes, assume how many levels of indexes are required for n nodes:

Suppose that every two nodes extract one node as the upper-level index

The first-level index is about 2 nUniverse.

The second-level index is about 4 nUniverse.

The third polar index is about 8 nUniverse.

The fourth-level index is about 16 nUniverse.

. and so on

The number of nodes of the k-level index is 1 / 2 of the number of nodes of the k-level index.

The number of k-level index nodes is n / (2 ^ k).

Set, the index has h level, and the highest index has 2 nodes

Apply the above formula to get n / (2 ^ h) = 2 and get h=log2n-1.

If the original linked list layer is included, the height of the entire jump table is log2n.

If m nodes are traversed each time when querying a data in a hopping table, the time complexity of querying a data in the hopping table is O (m*logn).

Multi-level index

If you extract one out of every three or five as an index, as shown in the figure, there are 14 nodes:

The first-level index requires three nodes for nplink.

The second-level index requires nine nodes for nplink.

. For each level up, the number of indexes is divided by 3

Suppose the number of advanced indexes is 1, and the number of nodes at each level is listed, which is a proportional series.

Through the summation formula of the proportional series, the total index node is about njump 3 times 9 cycles 27 +. + 9+3+1=n/2

Although the space complexity is still O (n), compared with the index construction method of drawing one node for every two nodes above, the storage space of index nodes is reduced by half.

Generally speaking, in real development, regardless of the space occupied by the index, the index node only needs to store key values and a few pointers, but does not need to store objects.

Efficient dynamic insertion and deletion

Inserting and deleting actually requires two steps:

Find the right node

Insert or delete

Find

The time complexity of dynamic insert, delete, cut insert and delete is all O (logn).

By contrast, the insertion of a single linked list is O (1), but this is the time complexity after setting the insertion position.

However, in order to ensure the order of the linked list data, we still need to find the insertion position before inserting.

One-way linked list, you need to traverse each node to find the insertion location

Insert operation

As mentioned above, the time complexity of the jump table to find a specified node is O (logn), and it is the same to find the insertion location. The insertion process is shown below:

Delete operation

If the node is in the index at the same time, you want to delete the node in the original linked list as well as the node in the index.

The delete operation of a single connected table needs to get the previous node of the node, and then delete the latter node through the pointer to complete the deletion of the node.

So when looking for a node to be deleted, be sure to get the previous node of that node. (the two-way linked list does not consider this problem)

Dynamic update of jump table index

When constantly inserting data without updating the index, there may be a large number of nodes between the two indexes.

In extreme cases, it can cause the jump table to degenerate into a linked list.

As shown below:

As a dynamic data structure, jump table requires us to maintain the balance between the index and the original linked list.

If there are more linked list nodes, the index nodes should be increased to avoid complexity degradation and lead to the decline of search and delete performance.

The red-black tree and the avl number keep the balance between the left and right subtrees by rotating the left and right subtrees, while the jump table number maintains the balance by random functions.

The random function is used to determine which index the node is inserted into.

If the random function generates the value k, then add this node to the index from the first level to the K level.

As shown below:

The random function should be relatively high, in terms of probability, it is necessary to ensure the index size and data size balance of the jump table, so as not to degrade the performance excessively.

Thank you for your reading. the above is the content of "how to master the jump table of data structure and algorithm". After the study of this article, I believe you have a deeper understanding of the problem of how to master the jump table of data structure and algorithm. the specific use of the situation also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.