跳跃表插入节点的流程有以下几步:
1. 新节点和各层索引节点逐一比较,确定原链表的插入位置。O(logN)
2. 把索引插入到原链表.O(1)
3. 利用抛硬币的随机方法,决定新节点是否提升为上一级索引。结果为正则提升并继续抛硬币,结果为负则停止.O(logN)
总体上,跳跃表插入操作的时间复杂度为O(logN),而这种数据结构所占用空间市2N,既空间复杂度是O(N)
跳跃表中删除节点的步骤:
1. 自上而下,查找第一个出现节点的索引,并逐层找到每一层对应的节点logN
2. 删除每一层查找到的节点,如果该层只剩下一个节点,删除整个一层,原链表除外O(logN)
跳跃表删除操作的时间复杂度是O(logN)