跳跃表 https://61mon.com/index.php/archives/222/

跳跃表（英文名：Skip List），于 1990 年 William Pugh 发明，是一个可以在有序元素中实现快速查询的数据结构，其插入，查找，删除操作的平均效率都为

。

跳跃表的整体性能可以和二叉查找树（AVL 树，红黑树等）相媲美，其在 Redis 和 LevelDB 中都有广泛的应用。

每个结点除了数据域，还有若干个指针指向下一个结点。

整体上看，Skip List 就是带有层级结构的链表（结点都是排好序的），最下面一层（level 0）是所有结点组成的一个链表，依次往上，每一层也都是一个链表。不同的是，它们只包含一部分结点，并且越往上结点越少。仔细观察你会发现，通过增加层数，从当前结点可以直接访问更远的结点（这也就是 Skip List 的精髓所在），就像跳过去一样，所以取名叫 Skip List（跳跃表）。

具体参考：https://61mon.com/index.php/archives/222/

/**

*

* author 刘毅（Limer）

* date   2017-09-01

* mode   C++

*/

#include <iostream>

#include <cstdlib>

#include <cstring>

using namespace std;

#define P 0.25

#define MAX_LEVEL 32

struct Node

{

    int key;

    Node ** forward;

    Node(int key = , int level = MAX_LEVEL)

    {

        this->key = key;

        forward = new Node*[level];

        memset(forward, , level * sizeof(Node*));

    }

};

class SkipList

{

private:

    Node * header;

    int level;

private:

    int random_level();

public:

    SkipList();

    ~SkipList();

    bool insert(int key);

    bool find(int key);

    bool erase(int key);

    void print();

};

int SkipList::random_level()

{

    int level = ;

    while ((rand() & 0xffff) < (P * 0xffff) && level < MAX_LEVEL)

        level++;

    return level;

}

SkipList::SkipList()

{

    header = new Node;

    level = ;

}

SkipList::~SkipList()

{

    Node * cur = header;

    Node * next = nullptr;

    while (cur)

    {

        next = cur->forward[];

        delete cur;

        cur = next;

    }

    header = nullptr;

}

bool SkipList::insert(int key)

{

    Node * node = header;

    Node * update[MAX_LEVEL];

    memset(update, , MAX_LEVEL * sizeof(Node*));

    for (int i = level - ; i >= ; i--)

    {

        while (node->forward[i] && node->forward[i]->key < key)

            node = node->forward[i];

        update[i] = node;

    }

    node = node->forward[];

    if (node == nullptr || node->key != key)

    {

        int new_level = random_level();

        if (new_level > level)

        {

            for (int i = level; i < new_level; i++)

                update[i] = header;

            level = new_level;

        }

        Node * new_node = new Node(key, new_level);

        for (int i = ; i < new_level; i++)

        {

            new_node->forward[i] = update[i]->forward[i];

            update[i]->forward[i] = new_node;

        }

        return true;

    }

    return false;

}

bool SkipList::find(int key)

{

    Node * node = header;

    for (int i = level - ; i >= ; i--)

    {

        while (node->forward[i] && node->forward[i]->key <= key)

            node = node->forward[i];

        if (node->key == key)

            return true;

    }

    return false;

}

bool SkipList::erase(int key)

{

    Node * node = header;

    Node * update[MAX_LEVEL];

    fill(update, update + MAX_LEVEL, nullptr);

    for (int i = level - ; i >= ; i--)

    {

        while (node->forward[i] && node->forward[i]->key < key)

            node = node->forward[i];

        update[i] = node;

    }

    node = node->forward[];

    if (node && node->key == key)

    {

        for (int i = ; i < level; i++)

            if (update[i]->forward[i] == node)

                update[i]->forward[i] = node->forward[i];

        delete node;

        for (int i = level - ; i >= ; i--)

        {

            if (header->forward[i] == nullptr)

                level--;

            else

                break;

        }

    }

    return false;

}

void SkipList::print()

{

    Node * node = nullptr;

    for (int i = ; i < level; i++)

    {

        node = header->forward[i];

        cout << "Level " << i << " : ";

        while (node)

        {

            cout << node->key << " ";

            node = node->forward[i];

        }

        cout << endl;

    }

    cout << endl;

}

int main()

{

    SkipList sl;

    // test "insert"

    sl.insert();

    sl.insert();

    sl.insert(); sl.insert();

    sl.insert();

    sl.insert(); sl.insert();

    sl.insert();

    sl.insert();

    sl.insert();

    sl.insert();

    sl.insert();

    sl.insert();

    sl.insert();

    sl.print();

    // test "find"

    cout << sl.find() << endl;

    cout << sl.find() << endl;

    cout << sl.find() << endl << endl;

    // test "erase"

    sl.erase();

    sl.print();

    sl.erase();

    sl.print();

    sl.erase();

    sl.print();

    return ;

}