美文网首页
跳跃表的原理和实现

跳跃表的原理和实现

作者: 棒棒0_0 | 来源:发表于2018-07-22 20:14 被阅读0次

    链表如何做到二分搜索?
    我们知道,普通链表查询一个元素的时间复杂度为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;
    }
    

    相关文章

      网友评论

          本文标题:跳跃表的原理和实现

          本文链接:https://www.haomeiwen.com/subject/xhjrmftx.html