01 跳跃表

Myth丶恋晨 2023-01-05 03:54 11阅读 0赞

学习自：https://www.cnblogs.com/lfri/p/9991925.html

对一个有序列的查找插入。(也可以用红黑树平衡树)

跳表。

知识点1 、层数决定，随机数、  
知识点2、查找，先稀疏层，再稠密层  
知识点3、插入：先查找再插入。

注释代码:

#include<cstdio>
    #include<cstdlib>
    using namespace std;
    
    const int maxn = 100000 + 10;
    const int max_level = 25;        //层数上限
    
    //定义节点
    struct Node
    { 
        int key;
        int next[max_level + 1];  //next[i]表示这个节点在第i层的下一个编号
    }node[maxn + 2];
    int node_tot, head, tail;
    
    //生成层数
    inline int rand_level()
    { 
        int ret = 1;
        while (rand() % 2 && ret <= max_level)
            ret++;
        return ret;
    }
    
    //分配新节点 //key默认为0，表示head、tail的值为0
    inline void new_node(int& p, int key = 0)
    { 
        p = ++node_tot;
        node[p].key = key;
    }
    
    
    //初始化
    inline void init()
    { 
        new_node(head); new_node(tail);
        for (register int i = 1; i <= max_level; i++)//head层所有的下一个节点都是tail
            node[head].next[i] = tail;
    }
    
    //插入操作
    void insert(int key)
    { 
        int p = head;
        int update[max_level + 1];
        int K = rand_level();//这个节点随机占了K层
        for (register int i = max_level; i; i--)//
        { 
            //异或，相同为0，否则为1 
            //下一个节点不是 tail && 下一个节点的值小于当前的key 
            //这一层中 ，第一个大于等于key的节点。
            while ( node[p].next[i] ^ tail && node[  node[p].next[i]   ].key < key)  p = node[p].next[i];
            update[i] = p;
        }
        
        int tmp;
        new_node(tmp, key);
        //在每一层中插入。
        for (register int i = K; i; i--)
        { 
            node[tmp].next[i] = node[update[i]].next[i];
            node[update[i]].next[i] = tmp;
        }
    }
    
    //查找元素
    int find(int key)
    { 
        int p = head;
        for(register int i = max_level; i; i--)//遍历找到是否有这个节点、
        { 
            while (node[p].next[i] ^ tail && node[node[p].next[i]].key < key)
                p = node[p].next[i];
        }
        if (node[node[p].next[1]].key == key)  return node[p].next[1] - 2;
        else return -1;
    }
    
    int n, m;
    //给出 n 个正整数，然后有 m 个询问，每个询问一个整数，询问该整数是否在 n 个正整数中出现过。
    int main()
    { 
        srand(19260817);
        scanf("%d%d", &n, &m);
        init();//创建两个节点，头节点的25层的下一个节点初始化为尾节点。
        int tmp;
        while (n--)
        { 
            scanf("%d", &tmp);
            insert(tmp);
        }
        while (m--)
        { 
            scanf("%d", &tmp);
            int res = find(tmp);
            if (res > 0)  printf("YES\n");
            else  printf("NO\n");
        }
        return 0;
    }