跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。
其中-1表示INT_MIN, 链表的最小值,1表示INT_MAX,链表的最大值。
例子:查找元素 117
先确定该元素要占据的层数 K(采用丢硬币的方式,这完全是随机的)
然后在 Level 1 ... Level K 各个层的链表都插入元素。
例子:插入 119, K = 2
如果 K 大于链表的层数,则要添加新的层。
例子:插入 119, K = 4
插入元素的时候,元素所占有的层数完全是随机的,通过一下随机算法产生:
public int random_level() {
int k = 1;
while (Math.random() <= 0.5f) {
k++;
}
return k;
}
相当于做一次丢硬币的实验,如果遇到正面,继续丢,遇到反面,则停止。各个元素的层数,期望值是2层。
在各个层中找到包含 x 的节点,使用标准的 delete from list 方法删除该节点。
例子:删除 71
需求只要很明确,接下来都是体力活了。代码就不写了,毕竟跳跃表只是个思想,很多细节东西都是因人而异,因业务而异。
大部分编程语言中的Map类型都是通过红黑树实现的,在写程序的时候,可以直接拿过来用,不用自己再去实现一个红黑树。但是跳表并没有一个现成的实现,所以在开发中,如果要使用跳表这种数据结构,需要自己先去实现。
更多内容,欢迎关注微信公众号:全菜工程师小辉~