跳跃表的原理和实现

链表如何做到二分搜索？
我们知道，普通链表查询一个元素的时间复杂度为O(n)，即使该链表是有序的，我们也不能通过二分的方式缩减时间复杂地。

251350258885508.png

如上图，如果我们要查询元素为55的结点，必须从头结点循环遍历到最后一个节点，不算-INF一共查询8次。用什么方法能够用更少的次数访问到55呢？最直观的，当然是新开辟一条捷径去访问55.

251350261549492.png
如上图，我们要查询55的结点，只需要在L2层查找4次即可。在这个结构中，查找结点为46的元素将耗费5次查询。
那么，如何才能更开的查询到55呢？有了上面的经验，我们就很容易想到，再开辟一条捷径。 251350261549492.png

如上图，我们搜索55只要两次查找即可，这个结构中，查找46仍然是最耗时的，需要查询5次。很显然，这种思想和二分非常相似，那么我们最后的结构图就应该如下图：

251350261549492.png

我们可以看到，最耗时的访问46需要6次查询。即L4访问55，L3访问21、55，L2访问37、55，L1访问46。我们直觉上认为，这样的结构会让查询有序链表的某个元素更快。那么究竟算法复杂度是多少呢？
如果有n个元素，因为是2分，所以层数就应该是log n层 (本文所有log都是以2为底)，再加上自身的1层。以上图为例，如果是4个元素，那么分层为L3和L4，再加上本身的L2，一共3层；如果是8个元素，那么就是3+1层。最耗时间的查询自然是访问所有层数，耗时logn+logn，即2logn。为什么是2倍的logn呢？我们以上图中的46为例，查询到46要访问所有的分层，每个分层都要访问2个元素，中间元素和最后一个元素。所以时间复杂度为O(logn)。

算法实现：

#include <stdlib.h>

#define MAX_LEVEL 16
#define NULL 0

typedef struct _Node
{
    int value;
    _Node* pre[MAX_LEVEL];
    _Node* next[MAX_LEVEL];
}Node;

Node* head;
Node* tail;

int random()
{
    int level = 0;
    while (rand() % 2 && (level < MAX_LEVEL - 1))
        level++;
    return level;
}

void skiplist_init()
{
    if (head)
    {
        Node* node = head;
        Node* tmp = NULL;
        while (node)
        {
            tmp = node->next[0];
            delete node;
            node = tmp;
        }
    }
    head = new Node;
    head->value = INT_MIN;
    tail = new Node;
    tail->value = INT_MAX;
    for (register int i = 0; i < MAX_LEVEL; i++)
    {
        head->pre[i] = NULL;
        head->next[i] = tail;
        tail->pre[i] = head;
        tail->next[i] = NULL;
    }
}

void skiplist_insert(int value)
{
    Node* new_node = new Node;
    new_node->value = value;
    for (register int i = 0; i < MAX_LEVEL; i++)
        new_node->pre[i] = new_node->next[i] = NULL;

    int level = random();
    Node* node = head;
    for (register int i = MAX_LEVEL - 1; i >= 0; i--)
    {
        while (node->next[i]->value < new_node->value)
            node = node->next[i];
        if (i <= level)
        {
            new_node->next[i] = node->next[i];
            new_node->pre[i] = node;
            node->next[i]->pre[i] = new_node;
            node->next[i] = new_node;
        }
    }
}

Node* skiplist_find(int value)
{
    Node *node = head;
    for (register int i = MAX_LEVEL - 1; i >= 0; i--)
    {
        while (node->next[i]->value < value)
            node = node->next[i];
        if (node->next[i]->value == value)
            return node->next[i];
    }
    return NULL;
}

void skiplist_delete(Node* node)
{
    for (register int i = 0; i < MAX_LEVEL; i++)
    {
        if (!node->next[i] || !node->pre[i])
            return;
        node->pre[i]->next[i] = node->next[i];
        node->next[i]->pre[i] = node->pre[i];
    }
}

int main()
{
    skiplist_init();
    skiplist_insert(1);
    skiplist_insert(10000);
    skiplist_insert(1000);
    skiplist_insert(100);
    skiplist_insert(920);
    Node* node = skiplist_find(1);
    if (node)
    {
        printf("find it!\n");
        skiplist_delete(node);
    }   
    Node* node1 = skiplist_find(100000);
    if (!skiplist_find(100000))
        printf("find error!\n");
    
    return 0;
}