设计跳表

虾米姐 阅读:846 2020-10-21 17:08:56 评论:0

不使用任何库函数,设计一个跳表。

跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树,其功能与性能相当,并且跳表的代码长度相较下更短,其设计思想与链表相似。

例如,一个跳表包含 [30, 40, 50, 60, 70, 90],然后增加 80、45 到跳表中,以下图的方式操作:

 

 


Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

跳表中有很多层,每一层是一个短的链表。在第一层的作用下,增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n)),空间复杂度是 O(n)。

在本题中,你的设计应该要包含这些函数:

bool search(int target) : 返回target是否存在于跳表中。
void add(int num): 插入一个元素到跳表。
bool erase(int num): 在跳表中删除一个值,如果 num 不存在,直接返回false. 如果存在多个 num ,删除其中任意一个即可。
了解更多 : https://en.wikipedia.org/wiki/Skip_list

注意,跳表中可能存在多个相同的值,你的代码需要处理这种情况。

样例:

Skiplist skiplist = new Skiplist();

skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0); // 返回 false
skiplist.add(4);
skiplist.search(1); // 返回 true
skiplist.erase(0); // 返回 false,0 不在跳表中
skiplist.erase(1); // 返回 true
skiplist.search(1); // 返回 false,1 已被擦除
约束条件:

0 <= num, target <= 20000
最多调用 50000 次 search, add, 以及 erase操作。

 

struct Node{ 
    Node *right,*down;   //向右向下足矣 
    int val; 
    Node(Node *right,Node *down,int val):right(right),down(down),val(val){} 
}; 
 
class Skiplist { 
private: 
    Node *head; 
 
public: 
    Skiplist() { 
        head=new Node(NULL,NULL,-1);  //初始化头结点 
    } 
     
    bool search(int target) { 
        Node *p=head; 
        while(p){ 
            while(p->right && p->right->val<target){   //寻找目标区间,基本就是这个思路 
                p=p->right; 
            } 
            if(!p->right || target<p->right->val){ //没找到目标值,则继续往下走 
                p=p->down; 
            }else{         //找到目标值,结束 
                return true; 
            } 
        } 
        return false; 
    } 
     
    void add(int num) { 
        vector<Node*> pathList;    //从上至下记录搜索路径 
        Node *p=head; 
        while(p){ 
            while(p->right && p->right->val<num){  
                p=p->right; 
            } 
            pathList.push_back(p); 
            p=p->down; 
        } 
 
        bool  insertUp=true; 
        Node* downNode=NULL; 
        while(insertUp && pathList.size()>0){   //从下至上搜索路径回溯,50%概率 
            Node *insert=pathList.back(); 
            pathList.pop_back(); 
            insert->right=new Node(insert->right,downNode,num); //add新结点 
            downNode=insert->right;    //把新结点赋值为downNode 
            insertUp=(rand()&1)==0;   //50%概率 
        } 
        if(insertUp){  //插入新的头结点,加层 
            head=new Node(new Node(NULL,downNode,num),head,-1); 
        } 
    } 
     
    bool erase(int num) { 
        Node *p=head; 
        bool seen=false; 
        while(p){ 
            while(p->right && p->right->val<num){ 
                p=p->right; 
            } 
            if(!p->right ||p->right->val>num){   
                p=p->down; 
            }else{    //搜索到目标结点,进行删除操作,结果记录为true,继续往下层搜索,删除一组目标结点 
                seen=true; 
                p->right=p->right->right; 
                p=p->down; 
            } 
        } 
        return seen; 
    } 
};

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号