type
status
date
slug
summary
tags
category
icon
password
Property
跳跃表(Skip List)是在链表的基础上增加了“跳跃”的功能，即加上了【多级索引】，通过索引来快速查找，可以支持快速的删除、插入和查找操作。它实际上是一种增加了前向指针的链表，是一种随机化的数据结构。其具有如下性质：
- 由很多层链表组成
- 每一层都是一个有序的链表
- 最底层（level 1）的链表包含所有元素
- 如果一个元素出现在 level i 层的链表中，则它在 level i 之下的链表也都会出现
- 每个节点都包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素
对于下图所示的单链表而言，即使数据是有序的，但是如果想要查找某个数据，只能从头节点开始向后遍历，查询效率低，时间复杂度为：
将其变为跳表形式，则如下图所示：
type
status
date
slug
summary
tags
category
icon
password
Property
目录
堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。
每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。STL 中的
priority_queue 其实就是一个大根堆。（小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。一些功能强大的堆（可并堆）还能（高效地）支持
merge等操作。一些功能更强大的堆还支持可持久化，也就是对任意历史版本进行查询或者操作，产生新的版本。堆的分类
操作 \ 数据结构 | 配对堆 | 二叉堆 | 左偏树 | 二项堆 | 斐波那契堆 |
type
status
date
slug
summary
tags
category
icon
password
Property
目录
平衡二叉搜索树（Self-balancing binary search tree），又称AVL树
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。具有以下性质：
- 左右子树都是AVL树