skiplist.cpp

Bài toán

Cài skip list, thực hiện các thao tác chèn, xóa, tìm kiếm giá trị trong một tập hợp.

Độ phức tạp

Bộ nhớ: trung bình O(n)

Chèn: trung bình O(logn)

Xóa: trung bình O(logn)

Tìm kiếm: trung bình O(logn)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <stdlib.h>

#include <set>

#include <iostream>

using namespace std;

#define scanf asdfsadfas

#define printf(...) fprintf(stderr, ">"__VA_ARGS__)

#define SetLength(a, n, t) a=(t*)calloc(n, sizeof(t))

#define f0(i,n) for (int i=0; i<n; i++)

#define f1(i,n) for (int i=1; i<=n; i++)

struct node;

node* nil;

struct node {

    int key, height;

    node ** succ;

    node(int _height, int _key){

        height=_height;

        key=_key;

        SetLength(succ, height, node*);

        f0(i,height) succ[i]=nil;

    }

};

struct skip_list {

    int height;

    node* header;

    int random_height(int height){

        f1(i,height) if (rand()&1) return i;

        return height;

    }

    node* surround(int key, node ** update){

        node* a=header;

        for (int i=height-1; i>=0; i--){

            while (a->succ[i]->key < key) a=a->succ[i];

            update[i]=a;

        }

        return a->succ[0];

    }

    node* lower_bound(int key){

        node* a=header;

        for (int i=height-1; i>=0; i--)

        while (a->succ[i]->key < key) a=a->succ[i];

        return a->succ[0];

    }

    void insert(int key){

        node* update[height];

        node* a = surround(key, update);

        if (a->key==key) return;

        a=new node(random_height(height), key);

        f0(i,a->height) {

            a->succ[i]=update[i]->succ[i];

            update[i]->succ[i]=a;

        }

    }

    void erase(int key){

        node* update[height];

        node* a = surround(key, update);

        if (a->key != key) return ;

        f0(i,a->height) {

            if (update[i]->succ[i] != a) break;

            update[i]->succ[i] = a->succ[i];

        }

        delete a;

    }

    void show(){

        for (node* i=header->succ[0]; i!=nil; i=i->succ[0])

        cout << i->key << endl;

    }

    skip_list(int _height){

        if (nil==NULL){

            nil = new node(height, 0x55556666);

            f0(i,height) nil->succ[i]=nil;

        }

        height=_height;

        header=new node(height, -0x55556666);

    }

};

skip_list skl(20);

int m;

main(){

    set<int> S;

    S.insert(0x55556666);

    cin >> m;

    for (int i=1; i<=m; i++){

        char c; int x;

        x=rand()%100*1000;

        if (rand()&1) { skl.insert(x); S.insert(x); }

        else if (rand()&1) { skl.erase(x); S.erase(x); }

        else if (rand()&1) {

            int r1 = skl.lower_bound(x)->key;

            int r2 = *S.lower_bound(x);

            assert(r1==r2);

            cout << r1 << endl;

        }

        {

            node* i=skl.header->succ[0];

            set<int> :: iterator j=S.begin();

            while (i!=nil) {

                assert(i->key==*j);

                i=i->succ[0], j++;

            }

        }

    }

}

Nhận xét

Code trên đã được kiểm tra đọ chính xác bằng cách thực hiện các truy vấn random và so sánh với kiểu std::set.

Tuy nhiên thời gian chạy chưa được kiểm tra.