How to understand a skip table

• Skip list: linked list based on the idea of dichotomy

  • Binary queries apply to arrays and support random access
  • The same applies to red-black tree scenarios

• What is a skip watch

  • Ordered single linked list query time is still O(n)
  • A skip table is a linked list index that uses extra space

\

Use the hop table to query how fast

• The time complexity of a single list is order n.

• The time complexity of the hop table is O(logn), and the space complexity obtained by sacrificing the space complexity is O(n).

  • When storing large objects, the index space is small

Efficient dynamic insert and delete

• Insert and delete time complexity O(logn)\

The hop table index is dynamically updated

• If no efficient update method is adopted, the skip list will degenerate into a single linked list

  • Red black tree, balanced binary tree of AVL tree, left-handed and preferred hold tree size

• A random function determines which level of index a node is inserted into

  • Randomly generated K

conclusion

• Compared to red-black trees, jump tables add range queries
• The code for a skip table is much cleaner than a red-black tree