新手做导航网站,凡科登录入口官网,订单拆单在电商网站建设,正邦设计的logo跳表#xff08;Skip List#xff09;是一种概率性数据结构#xff0c;它通过在普通有序链表的基础上增加多级索引层来实现快速的查找、插入和删除操作。跳表的效率可以与平衡树相媲美#xff0c;其操作的时间复杂度也是O(log n)#xff0c;但跳表的结构更简单#xff0c…跳表Skip List是一种概率性数据结构它通过在普通有序链表的基础上增加多级索引层来实现快速的查找、插入和删除操作。跳表的效率可以与平衡树相媲美其操作的时间复杂度也是O(log n)但跳表的结构更简单更易于实现。
跳表的核心特征
多层结构跳表包含多个层级。最底层第0层包含所有的元素。每一层都是下一层的“快速通道”每个元素出现在上层的概率通常是1/2。头节点跳表有一个头节点head它在所有层级中都存在。头节点的值通常不存储实际的数据它的目的是为了搜索、插入和删除操作提供一个统一的起点。随机层级每个新插入的节点的层数是通过随机过程决定的以确保跳表的平衡性。这意味着高层索引不会过于密集或稀疏。
数据结构组件
节点SkipListNode每个节点包含的信息有 值value存储的数据值。前进指针forward一个指针数组指向同一层级的下一个节点以及上层对应的节点。头节点Head是一个特殊的节点它的forward指针数组的长度等于跳表的最大层数。它在所有层级上都指向该层的第一个实际节点如果存在。层数Level跳表当前的最大层数。这个值是动态的随着新节点的插入可以增加。
操作原理
搜索Search从头节点开始在最高层级搜索如果当前节点的下一个节点的值小于目标值则向前移动如果大于目标值则下降到下一层级继续搜索直至找到目标值或搜索失败。插入Insert首先通过随机过程确定新节点的层数。然后从最高层开始寻找插入位置逐层向下直到达到新节点应存在的最低层级。在每一层将新节点插入到适当的位置并更新相关节点的指针。删除Delete与搜索类似首先定位要删除的节点。然后从其所在的最高层开始逐层向下删除节点并更新指针。
优点与应用
简单性跳表的数据结构和算法相对简单特别是与平衡树和B树等结构相比。动态性跳表可以很容易地支持动态数据集合的操作如实时插入和删除。效率对于大多数操作跳表可以提供对数时间复杂度的性能适用于需要快速搜索操作的场景如数据库索引和内存数据库。
跳表通过简单的随机化过程来避免复杂的重平衡操作使得它成为一种既高效又易于实现的数据结构选项。 简单的跳表实现示例
import java.util.Random;class SkipListNode {int value;SkipListNode[] forward; // 指向不同层的指针数组public SkipListNode(int value, int level) {this.value value;this.forward new SkipListNode[level 1];}
}public class SkipList {private static final float P 0.5f;private static final int MAX_LEVEL 16;private SkipListNode head;private int level;private Random random;public SkipList() {level 0;head new SkipListNode(0, MAX_LEVEL);random new Random();}// 随机生成节点的层数private int randomLevel() {int lvl 1;while (random.nextFloat() P lvl MAX_LEVEL) {lvl;}return lvl;}// 插入节点public void insert(int value) {int lvl randomLevel();SkipListNode newNode new SkipListNode(value, lvl);SkipListNode current head;SkipListNode[] update new SkipListNode[MAX_LEVEL 1];for (int i level; i 0; i--) {while (current.forward[i] ! null current.forward[i].value value) {current current.forward[i];}update[i] current;}for (int i 0; i lvl; i) {newNode.forward[i] update[i].forward[i];update[i].forward[i] newNode;}if (lvl level) {level lvl;}}// 查找节点public boolean search(int value) {SkipListNode current head;for (int i level; i 0; i--) {while (current.forward[i] ! null current.forward[i].value value) {current current.forward[i];}}current current.forward[0];return current ! null current.value value;}// 删除节点public void delete(int value) {SkipListNode[] update new SkipListNode[MAX_LEVEL 1];SkipListNode current head;for (int i level; i 0; i--) {while (current.forward[i] ! null current.forward[i].value value) {current current.forward[i];}update[i] current;}current current.forward[0];if (current.value value) {for (int i 0; i level; i) {if (update[i].forward[i] ! current) break;update[i].forward[i] current.forward[i];}while (level 0 head.forward[level] null) {level--;}}}// 打印跳表的内容public void display() {System.out.println(SkipList: );for (int i 0; i level; i) {SkipListNode node head.forward[i];System.out.print(Level i : );while (node ! null) {System.out.print(node.value );node node.forward[i];}System.out.println();}}
}// 使用示例
public class Main {public static void main(String[] args) {SkipList list new SkipList();list.insert(3);list.insert(6);list.insert(7);list.insert(9);list.insert(12);list.insert(19);list.insert(17);list.display();System.out.println(Searching 6: list.search(6));System.out.println(Searching 15: list.search(15));list.delete(6);System.out.println(After deleting 6: );list.display();}
}这段代码首先定义了SkipListNode类它是跳表节点的结构包括节点值和一个数组forward数组中每个元素是对应层级的下一个节点的引用。SkipList类实现了跳表包括初始化、插入、查找、删除和打印跳表的方法。
insert方法用于插入新的节点。search方法用于查找一个值如果找到则返回true。delete方法用于删除一个值。display方法用于打印跳表的所有层级和节点。
通过一个具体的例子来说明跳表的插入过程
假设我们有一个跳表它当前的状态如下其中每一行代表一个层级层级0是最底层包含所有元素
层级31 -------------------------------- 9
层级21 ------------ 5 ------------ 9
层级11 ---- 3 ---- 5 ---- 7 ---- 9
层级01 - 2 - 3 - 4 - 5 - 6 - 7 - 9现在我们想要插入一个新的节点值为8并假设通过随机过程决定新节点8将出现在层级0、1和2上不出现在层级3上。下面是插入过程的步骤
步骤1寻找每一层的插入位置
从跳表的最高层在这个例子中是层级3开始寻找直到找到比插入值小的最大节点。因为8不会被插入到层级3我们直接从层级2开始
层级2从1开始遍历到5因为9大于8所以5是层级2的插入位置。层级1同样从1开始遍历到5然后到7因为9大于8所以7是层级1的插入位置。层级0从1开始按顺序遍历直到7因为9大于8所以7是层级0的插入位置。
步骤2插入节点并更新指针
层级2在5和9之间插入8更新5的下一个指针为88的下一个指针为9。层级1在7和9之间插入8更新7的下一个指针为88的下一个指针为9。层级0在7和9之间插入8更新7的下一个指针为88的下一个指针为9。
插入8后跳表变为
层级31 -------------------------------- 9
层级21 ------------ 5 ------- 8 ---- 9
层级11 ---- 3 ---- 5 ---- 7 - 8 - 9
层级01 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9步骤3调整跳表的总层数如果需要
在这个例子中新插入的节点8并没有增加跳表的总层数因此不需要调整。
通过这个例子你可以看到插入过程如何在每一层找到正确的插入位置并更新指针来维护跳表的结构。这个过程确保了跳表的搜索效率使得搜索、插入和删除操作的时间复杂度都为O(log n)。
