跳跃表的C++实现

andalousie

参考资料：Algorithms in C++ Parts 1-4, Robert Sedgewick
代码如下：

#ifndef SKIPLIST_H
#define SKIPLIST_H
#include "Random.h"

static const int max_level = 30;
        //for small lists, max_level can be set 5

template<typename Key, typename Value>
class SkipList
{
        struct Node
        {
                Key   key;
                Value val;
                int   sz;
                Node ** next;

                Node (Key key, Value value, int n)
                        : key(key), val(value), sz(n)
                {
                        next = new Node* [n];
                        for(int i = 0; i < n; ++i)
                                next[i] = 0;
                }
        };
public:
        SkipList ()
                : lgN(0)
        {
                head = new Node(0, 0, max_level);
        }

        int  count () { return count(head, 0); }

        void insert (const Key& k, const Value& v) { rootInsert(head, new Node(k, v, rand_gen()), lgN); }

        Value search (const Key& k) { return search(head, k, lgN); }

        void remove (const Key& k) { remove(head, k, lgN); }
private:
        Node * head;
        int    lgN;
        Random rnd;

        int rand_gen ()
        {
                int i, t = rnd.randomInt();
                for (i = 1; i < max_level; ++i)
                {
                        int res = t >> (31-i);
                        if (res) break;
                }
                if (i > lgN) lgN = i;
                return i;
        }

        int count (Node * t, int c)
        {
                Node * t0 = t->next[0];
                if (!t0) return c;
                return count(t0, c+1);
        }

        void rootInsert (Node * t, Node * x, int n)
        {
                Key v = x->key;
                Node * pos = t->next[n];
                if (!pos || v < pos->key)
                {
                        if (n < x->sz)
                        {
                                x->next[n] = pos;
                                t->next[n] = x;
                        }
                        if (!n) return;
                        rootInsert(t, x, n-1);
                        return;
                }
                rootInsert(pos, x, n);
        }

        Value search (Node * t, Key k, int n)
        {
                if (!t) return 0;
                if (k == t->key) return t->val;
                Node * x = t->next[n];
                if(!x || k < x->key)
                {
                        if (!n) return 0;
                        return search(t, k, n-1);
                }
                return search(x, k, n);
        }

        void remove (Node * t, Key k, int n)
        {
                if (!t) return;
                Node * x = t->next[n];
                if (!x || x->key >= k)
                {
                        if (x)
                        {
                                if (k == x->key)
                                        t->next[n] = x->next[n];
                                if (!k)
                                {
                                        delete x;
                                        return;
                                }
                        }
                        if (!n) return;
                        remove(t, k, n-1);
                }
                remove(t->next[n], k, n);
        }
};

#endif

由于原来我发布过的代码里面有Random.h，这里就不重读列出了。参见http://bbs.fishc.com/thread-44631-1-1.html的附件。