数据结构与算法—跳表（skiplist）

目录

前言

跳表

查询时间分析

1、时间复杂度  o(logn)

2、空间复杂度O(n)

动态插入和删除

跳表动态更新

跳表与红黑树比较

跳表实现

---

前言

二分查找用的数组

链表可不可以实现二分查找呢？

跳表

        各方面性能比较优秀的动态数据结构，可以支持快速插入、删除、查找操作。写起来也不复杂，甚至可以代替红黑树。

跳表特点

对链表建立一级索引，每两个节点提取一个节点到上一级，叫做索引节点。

加一层索引之后，查找一个结点需要遍历的节点个数减少了，也就是查找效率提高了。

这种查找方式就是跳表

查询时间分析

1、时间复杂度  o(logn)

1. 在单链表中查询某个数据的时间复杂度O(N)
2. 跳表，n个节点，会有几层索引。

• 第k级索引的节点个数是k-1级索引节点个数的1/2；即 第k级索引节点的个数 n/2^k
• k = log2n-1,如果包含原始链表层，整个跳表的高度是log2 n
• 在跳表查找某个数据时，如果每一层需要遍历m个节点，那么跳表查询一个数据的时间复杂度O(m*logn)
• m是多少？ 每一级索引最多只需要遍历3个节点， m = 3 常数 

2、空间复杂度O(n)

索引节点的个数 n/2+n/4+n/8…+8+4+2=n-2 ,所以跳表的空间复杂度O(n)

意思是n个节点的单链表改成跳表，需要额外再用接近n个节点的内存空间。

在软件开发中原始链表中存储的有可能是很大的对象，而索引节点只需要存储关键值和几个指针，并不需要存储对象。所以当对象所以节点很大时，索引占用的空间可以忽略不计了。

动态插入和删除

插入、删除操作时间复杂度O(logn)

查找，需要遍历每个节点。查找时间复杂度O(logn)

删除，要拿到前驱节点，如果是双向链表，不需要考虑这个问题。

跳表动态更新

• 插入数据，如果跳表不更新，跳表会退化成单链表。
• 跳表通过随机函数维护 “平衡性”
• 往跳表中插入数据时，同时将数据插入到索引层中。（哪个索引层？）

        通过随机函数，决定这个点插入到哪几级索引，如随机函数生成K，则节点添加到第一级到第K级索引中。 

跳表与红黑树比较

1，按照区间查找数据，红黑树的效率没有跳表高。跳表O(logn)

2、跳表灵活，通过改变索引结构，有效平衡执行效率和内存消耗

3、红黑树一般有现成的可用，跳表需要自己实现

跳表实现

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>typedef struct _node
{int key;int value;int max_level;struct _node *next[0];
}node;typedef struct _skiplist
{int level;int count;node *head;
}skiplist;#define offsetof(TYPE,MEMBER) ((size_t) & ((TYPE *)0)->MEMBER)
#define container(ptr,type,member) ({\const typeof( ((type *)0)->member) *__mptr = (ptr);\(type *) ( (char *)__mptr - offsetof(type,member));})node * skip_list_create_node(int level,int key,int value)
{node *tmp = NULL;tmp = (node *)malloc(sizeof(node) + level*sizeof(node*));assert(tmp !=NULL);memset(tmp,0,sizeof(node) + level * sizeof(node*));tmp->key = key;tmp->value = value;tmp->max_level = level;return tmp;
}
skiplist *skip_list_create(int max_level)
{int i=0;skiplist *list = NULL;list = (skiplist *)malloc(sizeof(skiplist));assert(list != NULL);list->level = 1;list->count = 0;list->head = skip_list_create_node(max_level,0,0);if(list->head == NULL){free(list);return NULL;}return list;
}
void skip_list_destory(skiplist *list)
{int i = 0;node *tmp = NULL;if((list == NULL) || list->head == NULL){return ;}while(list->head->next[0] != NULL){tmp = list->head->next[0];list->head->next[0] = tmp->next[0];free(tmp);}free(list->head);free(list);return;
}int skip_list_level(skiplist *list)
{int i = 0;int level = 1;for(i = 0;i<list->head->max_level;i++){if(rand()%2 == 1)level++;}return level;
}int skip_list_insert(skiplist *list,int key,int value)
{int i = 0;int level = 0;node **update = NULL;node *tmp = NULL;node *prev = NULL;if(list == NULL)return 1;update = (node **)malloc(sizeof(node *)*list->head->max_level);if(update == NULL)return 2;prev = list->head;for(i = (list->level - 1);i>=0;i--){while(((tmp = prev->next[i]) != NULL) && (tmp->key < key)){prev = tmp;}update[i] = prev;}if((tmp != NULL) && (tmp->key == key))return 3;//get ramdon levellevel = skip_list_level(list);tmp = skip_list_create_node(level,key,value);if(tmp == NULL)return 4;//update max level,updateif(level > list->level){for(i = list->level;i<level;i++){update[i] = list->head;}list->level = level;}//update node pointerfor(i = 0;i<level;i++){tmp->next[i] = update[i]->next[i];update[i]->next[i] = tmp;}list->count++;return 0;
}int skip_list_search(skiplist *list,int key,int *value)
{int i=0;node *prev = NULL;node *tmp = NULL;if((list == NULL) || (list->count == 0) || (value == NULL)){return 1;}prev = list->head;for(i = list->level - 1;i >= 0;i--){//while(((tmp == prev->next[i])!=NULL) && (tmp->key<=key))while(((tmp = prev->next[i]) != NULL) && (tmp->key <= key)){if(tmp->key == key){*value = tmp->value;return 0;}prev = tmp;}}return -1;
}void skip_list_dump(skiplist *list)
{int i = 0;node *ptmp = NULL;printf("\r\n skiplist level[%d],count[%d]",list->level,list->count);for(i = list->level -1 ;i>=0;i--){ptmp = list->head->next[i];printf("\r\n level[%d]:",i);while(ptmp != NULL){printf("%d-%d ",ptmp->key,ptmp->value);ptmp = ptmp->next[i];}}printf("\r\n-----------------------------------\n");return;
}int skip_list_delete(skiplist *list,int key,int *value)
{int i = 0;node **update = NULL;node *tmp = NULL;node *prev = NULL;if((list == NULL) && value == NULL || list->count ==0)return 1;update = (node **)malloc(sizeof(node *)*list->level);if(update == NULL)return 2;prev = list->head;for(i = (list->level - 1);i>=0;i++){while((tmp = prev->next[i]) != NULL && (tmp->key < key)){prev=tmp;}update[i] = prev;}if((tmp != NULL) && (tmp->key == key)){*value = tmp->value;for(i = 0;i<list->level;i++){if(update[i]->next[i] == tmp){update[i]->next[i] = tmp->next[i];}}free(tmp);tmp = NULL;for(i = list->level -1 ;i>=0 ;i++){if(list->head->next[i]==NULL)list->level--;elsebreak;}list->count--;}elsereturn 3;//not findreturn 0;
}int main()
{int res = 0;int key = 0;int value = 0;skiplist *list = NULL;list = skip_list_create(8);assert(list != NULL);int i=0;for(i = 0;i<30;i++){key = value = i;res = skip_list_insert(list,key,value);if(res !=0){printf("insert error res=%d\n",res);}}printf("insert down\n");skip_list_dump(list);printf("############search#######\n");key = 10;skip_list_search(list,key,&value);printf("search value=%d\n",value);printf("############del############\n");skip_list_delete(list,key,&value);printf("del value=%d\n",value);	skip_list_dump(list);
}

# ./a.out 
insert downskiplist level[8],count[30]level[7]:15-15 level[6]:15-15 16-16 23-23 level[5]:0-0 1-1 5-5 8-8 14-14 15-15 16-16 19-19 22-22 23-23 24-24 level[4]:0-0 1-1 3-3 4-4 5-5 6-6 7-7 8-8 13-13 14-14 15-15 16-16 17-17 18-18 19-19 22-22 23-23 24-24 27-27 29-29 level[3]:0-0 1-1 2-2 3-3 4-4 5-5 6-6 7-7 8-8 9-9 10-10 13-13 14-14 15-15 16-16 17-17 18-18 19-19 20-20 21-21 22-22 23-23 24-24 25-25 26-26 27-27 28-28 29-29 level[2]:0-0 1-1 2-2 3-3 4-4 5-5 6-6 7-7 8-8 9-9 10-10 11-11 12-12 13-13 14-14 15-15 16-16 17-17 18-18 19-19 20-20 21-21 22-22 23-23 24-24 25-25 26-26 27-27 28-28 29-29 level[1]:0-0 1-1 2-2 3-3 4-4 5-5 6-6 7-7 8-8 9-9 10-10 11-11 12-12 13-13 14-14 15-15 16-16 17-17 18-18 19-19 20-20 21-21 22-22 23-23 24-24 25-25 26-26 27-27 28-28 29-29 level[0]:0-0 1-1 2-2 3-3 4-4 5-5 6-6 7-7 8-8 9-9 10-10 11-11 12-12 13-13 14-14 15-15 16-16 17-17 18-18 19-19 20-20 21-21 22-22 23-23 24-24 25-25 26-26 27-27 28-28 29-29 
-----------------------------------
############search############
search value=10
############del############
del value=10skiplist level[8],count[29]level[7]:15-15 level[6]:15-15 16-16 23-23 level[5]:0-0 1-1 5-5 8-8 14-14 15-15 16-16 19-19 22-22 23-23 24-24 level[4]:0-0 1-1 3-3 4-4 5-5 6-6 7-7 8-8 13-13 14-14 15-15 16-16 17-17 18-18 19-19 22-22 23-23 24-24 27-27 29-29 level[3]:0-0 1-1 2-2 3-3 4-4 5-5 6-6 7-7 8-8 9-9 13-13 14-14 15-15 16-16 17-17 18-18 19-19 20-20 21-21 22-22 23-23 24-24 25-25 26-26 27-27 28-28 29-29 level[2]:0-0 1-1 2-2 3-3 4-4 5-5 6-6 7-7 8-8 9-9 11-11 12-12 13-13 14-14 15-15 16-16 17-17 18-18 19-19 20-20 21-21 22-22 23-23 24-24 25-25 26-26 27-27 28-28 29-29 level[1]:0-0 1-1 2-2 3-3 4-4 5-5 6-6 7-7 8-8 9-9 11-11 12-12 13-13 14-14 15-15 16-16 17-17 18-18 19-19 20-20 21-21 22-22 23-23 24-24 25-25 26-26 27-27 28-28 29-29 level[0]:0-0 1-1 2-2 3-3 4-4 5-5 6-6 7-7 8-8 9-9 11-11 12-12 13-13 14-14 15-15 16-16 17-17 18-18 19-19 20-20 21-21 22-22 23-23 24-24 25-25 26-26 27-27 28-28 29-29 
-----------------------------------