跳躍表的實作（c++）

跳躍表簡單的說就是個能夠提供快車道（區間的索引）實作快速通路的有序連結清單，普通的連結清單的查找複雜度是n，這個複雜度太大了，跳躍表查找插入删除都在lg(n)的複雜度，是一種随手就能寫出來的資料結構（為什麼這麼說呢，因為其它lg(n)的可以來實作查找的資料結構實在包含挺多細節的，對我這種渣渣來說每次看完紅黑樹過不了多久我就會忘了它的操作細節了，隻記得它通過維護顔色的平衡來實作樹的平衡，更别說随手寫了）。關于跳躍表這裡就不做介紹了，如果還沒了解過這個資料結構的話還是看一遍《算法導論公開課 跳躍表》，才知道跳躍表的理論基礎以及推導過程。

代碼中有一個容易誤解的地方解釋一下，randomLevel模拟抛硬币的過程比較不太直覺，在插入過程中一個節點上升的次數實際上等價于連續出現“正面”的次數，是以我們直接一次性算出來，而不是每插完一個節點抛一次硬币，這樣友善在進行實際插入之前進行一些檢查

還有由于插入提升節點的過程中，需要知道往上提升的位置，是以每次往下走的時候都要記住走下來的位置，我們用updateNode記住這個位置，其它的就是普通連結清單的細節了

本代碼沒有做邊界檢查和驗證，僅做簡單的實作示範使用

//List.h
#include <iostream>

namespace OJP {

    template<typename T>
        class Node {
            public:
                Node* next;
                Node* down;
                T val;
            public:
                void setNext(Node* next) {
                    this->next = next;
                }

                Node(const T& val) {
                    this->val = val;
                    this->next = NULL;
                }

                Node() {
                    this->next = NULL;
                    this->down = NULL;
                }
        };

    template<typename T>
        class List {
            public:
                Node<T>* head;
                Node<T>* end;
            public:
                List() {
                    head = new Node<T>();
                    end = NULL;
                    head->next = end;
                    head->down = NULL;
                }

                void pushBack(const T& val) {
                    auto node = new Node<T>(val);
                    auto tmp = head;
                    while(tmp->next != end) {
                        tmp = tmp->next;
                    }
                    node->next = end;
                    tmp->next = node;
                }

                void insert(Node<T>* node, const T& val) {
                    auto newNode = new Node<T>(val);
                    newNode->next = node->next;
                    node->next = newNode;
                }

                Node<T>* find(const T& val) {
                    auto tmp = head->next;
                    while(tmp != end) {
                        if(tmp->val == val) {
                            return tmp;
                        }
                        tmp = tmp->next;
                    }
                    return NULL;
                }

                Node<T>* findLastLEOf(const T& t, Node<T>* node = NULL) {
                    auto tmp = head;
                    if(node != NULL) {
                        tmp = node;
                        if(tmp != head && tmp->val > t) {
                            return NULL;
                        }
                    }
                    while(tmp->next != end && tmp->next->val <= t) {
                        tmp = tmp->next;
                    }
                    return tmp;
                }

                Node<T>* findLastLessOf(const T& t, Node<T>* node = NULL) {
                    auto tmp = head;
                    if(node != NULL) {
                        tmp = node;
                        if(tmp != head && tmp->val >= t) {
                            return NULL;
                        }
                    }
                    while(tmp->next != end && tmp->next->val < t) {
                        tmp = tmp->next;
                    }
                    return tmp;
                }

                bool remove(const T& t, Node<T>* after) {
                    auto tmp = head;
                    if(after != NULL) {
                        tmp = after;
                    }
                    while(tmp->next != end) {
                        if(tmp->next->val > t) {
                            return false;
                        }
                        if(tmp->next->val == t) {
                            Node<T>* delNode = tmp->next;
                            tmp->next = tmp->next->next;
                            delete delNode;
                            return true;
                        }
                    }
                    return false;
                }

                void for_each(void (*func)(const T& )) {
                    auto tmp = head->next;
                    while(tmp != end) {
                        func(tmp->val);
                        tmp = tmp->next;
                    }
                }

                ~List() {
                    auto tmp = head->next;
                    while(tmp != end) {
                        Node<T>* node = tmp;
                        tmp = tmp->next;
                        delete node;
                    }
                }
        };
}

template<typename T>
void print(const T& a) {
    std::cout<<a<<" ";
}
           

//SkipList.cpp
#include "List.h"
using namespace std;

template<typename T>
class SkipList {
    private:
        OJP::List<T>* lists;
        static const int initialLevel = ;
        int level;

    public:
        SkipList() {
            lists = new OJP::List<T>[initialLevel];
            for(int i = ; i < initialLevel; i++) {
                lists[i].head->down = lists[i - ].head;
            }
            level = ;
        }

        static int randomLevel() {
            int i = ;
            while(rand() %  == ) {
                i++;
            }
            return i;
        }

        bool push(const T& t) {
            auto updateNode = new OJP::Node<T>*[initialLevel];
            for(int i = ; i < initialLevel; i++) {
                updateNode[i] = lists[i].head;
            }

            int updateLevel = level;
            auto searchFrom = lists[updateLevel].head;
            while(updateLevel >= ) {
                OJP::List<T>* list = &lists[updateLevel];
                updateNode[updateLevel] = list->findLastLEOf(t, searchFrom);
                searchFrom = updateNode[updateLevel]->down;
                if(searchFrom != NULL) {
                }
                updateLevel--;
            }

            if(updateNode[]->val == t) {
                return false;
            } else {
                lists[].insert(updateNode[], t);

                int newLevel = randomLevel();
                if(newLevel > initialLevel - ) {
                    return false;
                } else if(newLevel > level) {
                    level = newLevel;
                }

                updateLevel = ;
                while(updateLevel < newLevel) {
                    ++updateLevel;
                    lists[updateLevel].insert(updateNode[updateLevel], t);
                    updateNode[updateLevel]->next->down = updateNode[updateLevel - ]->next;
                }
            }
            return false;
        }

        bool find(const T& t) {
            int searchLevel = level;
            auto searchFrom = lists[searchLevel].head;
            while(searchLevel >= ) {
                OJP::List<T>* list = &lists[searchLevel];
                searchFrom = list->findLastLEOf(t, searchFrom);
                if(searchFrom->down && searchLevel > ) {
                    searchFrom = searchFrom->down;
                }
                searchLevel--;
            }
            if(searchFrom->val == t && searchFrom != lists[].head) {
                return true;
            }
            return false;
        }

        bool remove(const T& t) {
            int searchLevel = level;
            auto searchFrom = lists[searchLevel].head;
            while(searchLevel >= ) {
                OJP::List<T>* list = &lists[searchLevel];
                searchFrom = list->findLastLessOf(t, searchFrom);
                list->remove(t, searchFrom);
                if(searchFrom->down && searchLevel > ) {
                    searchFrom = searchFrom->down;
                }
                searchLevel--;
            }
            if(searchFrom->val == t && searchFrom != lists[].head) {
                return true;
            }
            return false;
        }

        ~SkipList() {
            delete []lists;
        }

        void dump() {
            for(int i = level; i >= ; i--) {
                cout<<"level["<<i<<"]: ";
                lists[i].for_each(print);
                cout<<endl;
            }
        }

};

int main() {
    SkipList<int> skipList = SkipList<int>();
    for(int i = ; i < ; i++) {
        int val = rand() % ;
        cout<<"push "<<val<<endl;
        skipList.push(val);
    }
    for(int i = ; i < ; i++) {
        int val = rand() % ;
        cout<<"find "<<val<<" "<<skipList.find(val)<<endl;
    }
    /*
    skipList.dump();
    skipList.remove(79);
    skipList.remove(92);
    skipList.remove(99);
    skipList.dump();*/
    return ;
}