数据结构：跳表

1、理想情况

在一个使用有序链表描述的具有n个元素的字典中进行搜索，至多需要n次比较。如果在链中部节点加一个指针，则比较次数可以减少到n/2+1。搜索时，首先将要搜索的元素与中间节点进行比较，如果该元素较小，则仅需搜索链表的左半部分。否则，只需搜索又半部分。

以上图为例，如果要搜索的数为26，则将26先与40比较，因为26<40,因此只需要搜索40的左边元素。

而如果在左半部分和右半部分再增加一个中间指针，则可以进一步减小搜索范围（b）。

初始的链称为0级链，如上图中的全部节点。

至少指向2个节点的链称为1级链，上图e中的24,40,75,77

以此类推，这种结构就称为跳表。i级链所包含的元素是i-1级链的子集。

2、插入和删除

　　在进行插入和删除时，要想保持跳表的结构，必须耗时O（n)。在这种结构中，有n/2ⁱ个元素为i级链元素，在进行插入式应尽量逼近这种结构。在进行插入时，新元素属于i级链的概率为1/2ⁱ.在确定新元素的级时，应考虑各种可能的情况。因此，把新元素作为i级链的可能性为pⁱ。对于一般的p,链的级数为log_1/pn+1。在这种情况下，每p个i-1级链中有一个在i级链中。插入时，首先要通过搜索以确定链中是否有此元素，搜索时记录下每一层遇到的最后一个元素。插入时，要为新元素分配一个级，分配过程由随机数产生器决定。

删除时，也要先通过搜索确定元素是否在链中以及每一层遇到的最后一个元素。

3、级分配

　　如前面分析所述，i-1级链中的元素属于i级链的概率为p。假设有一个随机数产生器所产生的数在0到RAND_MAX之间，则下一次所产生的属技术小于等于CutOff=p*RAND_MAX的概率为p。因此，若下一个随机数小于等于CutOff，则新元素应在1级链上。是否在2级链上，则由下一个随机数决定。重复这个过程，直到得到一个随机数大于CutOff为止。

int lev=0

while(rand()<=CutOff)++lev;

这种方法的潜在缺点是可能为某些元素分配特别大的级，从而导致一些元素的级远超过log_1/pN，其中N为字典中预期的最大数目。

为避免这种情况，可以设定一个上限Maxlevel。在有N个元素的跳表中，最大值为log_1/pN-1。

另一个缺点是还可能出现这种情况：如在插入一个新元素前有三条链，而在插入之后就有了10条链。这是，新插入的元素为9级，尽管前面并没有出现3到8级元素。

这种情况可以通过将新元素的级调整为3。

if(lev>Levels)

lev=++Levels;

Levels为当前的最大链级

 1 template<typename K,typename E>
 2 int SkipList<K,E>::Level()
 3 {
 4     int lev = 0;
 5     while (rand()<=CutOff)
 6     {
 7         ++lev;
 8     }
 9 
10     return (lev <= MaxLevel) ? lev : MaxLevel;
11 }

View Code

4、实现

节点：

 1 template<typename K,typename E>
 2 class SkipNode
 3 {
 4     friend ostream& operator<< <>(ostream&, const SkipNode<K, E>&);
 5     friend class SkipList < K, E >;
 6 public:
 7     SkipNode(int size,const K& k=0,const E& e=0):key(k),data(e)
 8     {
 9         link = new SkipNode<K, E>*[size];
10         for (int i = 0; i < size;++i)
11         {
12             link[i] = NULL;
13         }
14         
15     }
16     ~SkipNode()
17     {
18         if (link!=NULL)
19         {
20             delete[] link;
21         }
22         
23         link = NULL;
24     }
25     //获取0级连接
26     SkipNode<K,E>* getLinkLevel0()const
27     {
28         if (link!=NULL&&link[0]!=NULL)
29         {
30             return link[0];
31         }
32         return NULL;
33     }
34 private:
35     E data;
36     K key;
37     SkipNode<K, E>** link;
38 };
39 
40 template<typename K,typename E>
41 ostream& operator<<(ostream& output,const SkipNode<K,E>& s)
42 {
43     if (&s!=NULL)
44     {
45         output << s.key << "=>" << s.data << endl;
46     }
47 
48     return output;
49 }

View Code

完整实现：

  1 #ifndef SKIPLIST_H
  2 #define SKIPLIST_H
  3 
  4 #include<iostream>
  5 #include<cstdlib>
  6 #include<time.h>
  7 using namespace std;
  8 template<typename K,typename E>
  9 class SkipList;
 10 
 11 template<typename K,typename E>
 12 class SkipNode
 13 {
 14     friend ostream& operator<< <>(ostream&, const SkipNode<K, E>&);
 15     friend class SkipList < K, E >;
 16 public:
 17     SkipNode(int size,const K& k=0,const E& e=0):key(k),data(e)
 18     {
 19         link = new SkipNode<K, E>*[size];
 20         for (int i = 0; i < size;++i)
 21         {
 22             link[i] = NULL;
 23         }
 24         
 25     }
 26     ~SkipNode()
 27     {
 28         if (link!=NULL)
 29         {
 30             delete[] link;
 31         }
 32         
 33         link = NULL;
 34     }
 35     //获取0级连接
 36     SkipNode<K,E>* getLinkLevel0()const
 37     {
 38         if (link!=NULL&&link[0]!=NULL)
 39         {
 40             return link[0];
 41         }
 42         return NULL;
 43     }
 44 private:
 45     E data;
 46     K key;
 47     SkipNode<K, E>** link;
 48 };
 49 
 50 template<typename K,typename E>
 51 ostream& operator<<(ostream& output,const SkipNode<K,E>& s)
 52 {
 53     if (&s!=NULL)
 54     {
 55         output << s.key << "=>" << s.data << endl;
 56     }
 57 
 58     return output;
 59 }
 60 
 61 template<typename K,typename E>
 62 class SkipList
 63 {
 64     friend ostream& operator<< <>(ostream& output, const SkipList<K, E>& sl);
 65 public:
 66     SkipList(K Large, int MaxE = 10000, float p = 0.5);
 67     ~SkipList();
 68 
 69     bool Search(const K&, E&)const;
 70     SkipList<K, E>& Insert(const K&,const E&);
 71     SkipList<K, E>& Delete(const K&, E& e);
 72 private:
 73     int Level();//分配层号
 74     SkipNode<K, E>* SaveSearch(const K&)const;
 75     int MaxLevel;
 76     int Levels;//非空的最大层
 77     int CutOff;//分层阈值
 78     K TailKey;//一个很大的Key值
 79     SkipNode<K, E>* head;
 80     SkipNode<K, E>* tail;
 81     SkipNode<K, E>** last;//记录插入和删除操作时，所遇到的每条链上的最后一个元素
 82 };
 83 
 84 template<typename K,typename E>
 85 SkipList<K,E>::SkipList(K Large, int MaxE, float p):Levels(0),TailKey(Large)
 86 {
 87     CutOff = p*RAND_MAX;
 88     MaxLevel = ceil(log(MaxE) / log(1 / p)) - 1;
 89     srand(time(0));
 90 
 91     head = new SkipNode<K, E>(MaxLevel+1);
 92     tail = new SkipNode<K, E>(0);
 93     last = new SkipNode<K, E>*[MaxLevel + 1];
 94     tail->key = TailKey;
 95 
 96     for (int i = 0; i <= MaxLevel;++i)
 97     {
 98         head->link[i] = tail;
 99     }
100 }
101 
102 template<typename K,typename E>
103 SkipList<K,E>::~SkipList()
104 {
105     SkipNode<K, E>* next = NULL;
106     while (head!=tail&&head!=NULL)
107     {
108         next = head->getLinkLevel0();
109         delete head;
110         head = next;
111     }
112 
113     delete tail;
114 
115     delete[] last;
116 }
117 
118 template<typename K,typename E>
119 bool SkipList<K,E>::Search(const K& k, E& e)const
120 {
121     if (k>=TailKey)
122     {
123         return false;
124     }
125 
126     SkipNode<K, E>* p = head;
127     for (int i = Levels; i >= 0;--i)//逐级向下搜索，尽可能逼近k
128     {
129         while (p->link[i]!=NULL&&p->link[i]->key<k)
130         {
131             p = p->link[i];
132         }
133     }
134 
135     e = p->link[0]->data;
136     return (p->link[0]->key==k);
137 }
138 
139 template<typename K,typename E>
140 SkipNode<K,E>* SkipList<K,E>::SaveSearch(const K& k)const
141 {
142 
143     SkipNode<K, E>* p = head;
144     for (int i = Levels; i >= 0;--i)
145     {
146         while (p->link[i] != NULL&&p->link[i]->key<k)
147         {
148             p = p->link[i];
149         }
150         last[i] = p;
151     }
152 
153     return (p->link[0]);
154 }
155 
156 template<typename K,typename E>
157 int SkipList<K,E>::Level()
158 {
159     int lev = 0;
160     while (rand()<=CutOff)
161     {
162         ++lev;
163     }
164 
165     return (lev <= MaxLevel) ? lev : MaxLevel;
166 }
167 
168 template<typename K,typename E>
169 SkipList<K,E>& SkipList<K,E>::Insert(const K& k,const E& e)
170 {
171     if (k>=TailKey)
172     {
173         std::cerr << "键值过大" << std::endl;
174         //exit(1);
175         return *this;
176     }
177 
178     SkipNode<K, E>* p = SaveSearch(k);
179     if (p->key==e)
180     {
181         std::cerr << "当前key已存在" << std::endl;
182         //exit(1);
183         return *this;
184     }
185 
186     int lev = Level();
187     if (lev>Levels)
188     {
189         lev = ++Levels;
190         last[lev] = head;
191     }
192 
193     SkipNode<K, E>* y = new SkipNode<K, E>(lev+1);
194     y->data = e;
195     y->key = k;
196     for (int i = 0; i <= lev;++i)
197     {
198         y->link[i] = last[i]->link[i];
199         last[i]->link[i] = y;
200     }
201 
202     return *this;
203 }
204 
205 template<typename K,typename E>
206 SkipList<K,E>& SkipList<K,E>::Delete(const K& k, E& e)
207 {
208     if (k>=TailKey)
209     {
210         std::cerr << "key过大" << std::endl;
211         //exit(1);
212         return *this;
213     }
214 
215     SkipNode<K, E>* p = SaveSearch(k);
216     if (p->key!=k)
217     {
218         std::cerr << "key不存在" << std::endl;
219         //exit(1);
220         return *this;
221     }
222 
223     for (int i = 0; i <= Levels&&last[i]->link[i] == p;++i)
224     {
225         last[i]->link[i] = p->link[i];
226     }
227 
228     //修改级数
229     while (Levels>0&&head->link[Levels]==tail)
230     {
231         --Levels;
232     }
233 
234     e = p->data;
235     delete p;
236 
237     return *this;
238 }
239 
240 template<typename K,typename E>
241 ostream& operator<<(ostream& output,const SkipList<K,E>& sl)
242 {
243     SkipNode<K, E>* p = sl.head->getLinkLevel0();
244     while (p!=sl.tail&&p!=NULL)
245     {
246         output << *p;
247         p = p->getLinkLevel0();
248     }
249 
250     return output;
251 }
252 #endif

View Code

test.cpp:

 1 #include<iostream>
 2 
 3 #include "SkipList.h"
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     SkipList<int, char> sl(1000);
10     sl.Insert(0, 'a');
11     sl.Insert(1, 'b');
12     sl.Insert(4, 'e');
13     sl.Insert(3, 'c');
14 
15     cout << sl;
16     char x;
17     sl.Delete(0, x);
18     cout << "after delete:" << endl;
19     cout << sl;
20     if (sl.Search(1, x))
21     {
22         cout << "data of key " << 1 << " is " << x << endl;
23     }
24     return 0;
25 }

View Code

时间复杂度分析：

构造函数的时间复杂度为O（MaxLevel)

插入、删除、搜索的最坏复杂度为O（n+MaxLevel)，平均复杂度为O（logn)