本文主要是介绍数据结构之:跳表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
跳表(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是最底层,包含所有元素):
层级3:1 --------------------------------> 9
层级2:1 ------------> 5 ------------> 9
层级1:1 ----> 3 ----> 5 ----> 7 ----> 9
层级0:1 -> 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
的下一个指针为8
,8
的下一个指针为9
。 - 层级1:在
7
和9
之间插入8
,更新7
的下一个指针为8
,8
的下一个指针为9
。 - 层级0:在
7
和9
之间插入8
,更新7
的下一个指针为8
,8
的下一个指针为9
。
插入8
后,跳表变为:
层级3:1 --------------------------------> 9
层级2:1 ------------> 5 -------> 8 ----> 9
层级1:1 ----> 3 ----> 5 ----> 7 -> 8 -> 9
层级0:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
步骤3:调整跳表的总层数(如果需要)
在这个例子中,新插入的节点8
并没有增加跳表的总层数,因此不需要调整。
通过这个例子,你可以看到插入过程如何在每一层找到正确的插入位置,并更新指针来维护跳表的结构。这个过程确保了跳表的搜索效率,使得搜索、插入和删除操作的时间复杂度都为O(log n)。
这篇关于数据结构之:跳表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!