Skip List and Hash
跳表和散列都是用来做查找、插入、删除的随机方法。跳表的本质是增加了额外的向前指针的链表。
| 方法 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 跳表 | \(O(logn)\) | \(O(n)\) |
| 散列 | \(O(1)\) | \(O(n)\) |
Skip List
Find
跳表通过一层或者多层间隔不同的随机指针实现快速的定位。例如下图，要寻找数字5的话，从上面向下逐级检索，例如现在在第二层\(4<5 \&\& 5<6\)，那么将会在数字4的位置上到进入下一层随机指针，再向后遍历。
Insert
插入元素时
- 先查找应该插入的位置，在最下一层插入该元素（同时保留了查找元素的路径）
- 确定该元素拥有几级链表，根据概率来确定。（在规则情况下，对于共有n个元素的链表，每级链表的数量时可以确定的）
- 补充链表级别
Hash
参考STL库，数组+链表+红黑树的模式
Tree
| 类型 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| AVL Tree | \(\Theta(logn)\) | \(O(logn)\) |
| Red-Black Tree | \(O(logn)\) | \(O(logn)\) |
| B Tree | \(O(logn)\) | \(O(logn)\) |
| B+ Tree | \(O(logn)\) | 近似\(O(logn)\) |
Adelson-Velsky and Landis Tree (AVL Tree)
Intro
AVL树（Adelson-Velsky and Landis Tree）是最早被发明的平衡二叉树，也叫高度平衡树，具有如下性质：
- 满足二叉搜索树的所有性质
- 任一节点对应的两棵子树的最大高度差为1
AVL树的性质要求任意节点的左右子树的平衡因子差值都不能大于1。所以和红黑树相比，是一种严格的平衡二叉树，不论是增加还是删除，都要通过旋转来时刻保持平衡的性质 。
Time Complexity
增加/删除/查找：正常情况\(\Theta(logn)\)，最坏情况\(O(logn)\)
由于每一次操作都要保证平衡，所以所有的正常情况都是最坏情况
Simple Rotation
如下图，\(t_{23}\)(\(Z\)内侧的孩子)比\(t_4\)要更矮，在这种情况下可以将\(t_{23}\)旋转到和\(t_1\)一起，来和\(t_4\)达到平衡。这种情况称之为Simple Rotation
Double Rotation
如下图，\(Z\)内侧的孩子Y的高度要高于Z外侧的孩子。因此需要两次旋转，第一次，将内侧孩子旋转到外侧，成为Simple Rotation的状态，在按照Simple Rotation规则继续旋转。
Applicable Scene
- 适用于查找多但增加/删除不频繁的场景，这种情况下AVL树的性能较优于红黑树，如在Windows NT内核中的广泛使用。
Red-Black Tree
Intro
红黑树是一种弱平衡二叉树，在二叉查找树的基础上，对每个节点增加一个储存位来表示颜色节点。其追求的是一颗二叉树的局部平衡全非全局平衡，性质如下：
- 根节点和每个叶节点是黑的，其余节点非红即黑
- 如果一个节点是红的，那么它的左右孩子都是黑的
- 对于任意节点，其到叶子节点（NULL节点）的每条路径都包含相同数目的黑节点
红黑树通过对任何一条从根节点到叶子节点的路径上节点着色的限制，保证了每两条路径之间的差不会超过一倍路径长。相比于平衡二叉树任一节点对应的两棵子树的最大高度差为1的性质，它是一种弱平衡二叉树，也就是说，相同个数的节点构造出的AVL树高度小于等于红黑树，但其每次增删操作的旋转次数大大减少。
Operator
左旋
右旋
Insert
约定节点名称
找到插入的位置，颜色设置为红色（红色不会影响路径上黑色节点数量一样多的性质，因此优先设置为红色）。再进行如下的调整
插入的节点为红黑树的第一个节点，颜色设置为黑色
插入的节点已经存在了，颜色修改为旧节点的颜色
插入的节点的父节点上黑色的，万事大吉
插入节点的父节点是红色的（因为根是黑色的，所以这个红色的父节点必有祖父节点）
叔叔节点存在并为红色
若pp节点是根，pp修改为黑色，此景是唯一会增加黑色节点层数的情况；
若pp节点的父节点是黑色的，万事大吉；
若pp节点的父节点是红色的，则将pp看成新插入的节点，重新执行调整操作
叔叔节点不存在或为黑色且P节点是PP节点的左孩子
I是P的左孩子，右旋调整层级颜色和原来的一样
红色节点是不能相邻的，所以通过旋转将红色节点旋转到同一层来解决问题
I是P的右孩子，可以交换I和P的层级，转化成左孩子的情况
叔叔节点不存在或为黑色且P节点是PP节点的右孩子
和“叔叔节点不存在或为黑色且P节点是PP节点的左孩子”的情况正好镜像
直接放图
Delete
分为三种情景
情景1：若删除结点无子结点，直接删除
情景2：若删除结点只有一个子结点，用子结点替换删除结点
情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点
第三种情况，我们相当于删除了被替代的节点，即下图原来Q的位置
上述三种场景最终都可以转换成情景1
约定节点名称
删除节点是红色的，删了即可
删除节点是黑色的
R是左孩子
S是红色的（2.1.1）
转换成2.1.2的问题
S是黑色的(2.1.2)
SR是红色的(2.1.2.1)
SR是黑色的，SL是红色的(2.1.2.2)
转换成SR是红色的情况，再执行
SR和SL都是黑色的(2.1.2.3)
将S节点设置为黑色的，将P节点看成要被替换的节点，重新处理
R是右孩子，镜像处理不再赘述
Time Complexity
- 增加/删除/查找：正常情况\(O(logn)\)，最坏情况\(O(logn)\)
Applicable Scene
适用于增加/删除频繁的查找场景，如：
- C++ STL中的map，set底层都是用红黑树实现的；
- Linux进程调度算法Completely Fair Scheduler用红黑树管理进程控制块。进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
- IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查；
B Tree
Intro
B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树，相对于二叉树，B树每个内节点有多个分支，与红黑树相比，在相同的的节点的情况下，一颗B/B+树的高度远远小于红黑树的高度。
一颗 m 阶的B树是一颗有以下属性的树：
- 每一个节点最多有 m 个子节点
- 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
- 如果根节点不是叶子节点，那么它至少有两个子节点
- 有 k 个子节点的非叶子节点拥有 k − 1 个键
- 所有的叶子节点都在同一层
一棵5阶B+树，最多4个元素，最少3个子节点、2个元素。
Time Complexity
增加/删除/查找：正常情况\(O(logn)\)，最坏情况\(O(logn)\)
最好情况\(O(1)\)，好坏取决于访问的节点所在高度
Insert
Applicable Scene
由于传统的机械磁盘具有快速顺序读写、慢速随机读写的访问特性，为了避免这个特性带来的影响，科学家发明了B树和B+树。构造一个多阶的B类树，尽量多的在结点上存储相关的信息，保证层数（树的高度）尽量的少，同时节点内部有序。这样的数据结构大大减少磁盘的IO操作。
B树常用于操作系统文件系统以及部分数据库索引（MongoDB）。
B+树
Intro
B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生，一颗B+树的性质如下：
- 非叶子节点存放的是索引数据
- 叶子节点存放的是行数据，并且是顺序存放的（叶节点间是双向链表结构，附图是单向链表）
B+树的叶子节点包含了所有全量元素信息，并且叶子节点间形成有序链表。
Time Complexity
- 增加/删除/查找：正常情况\(O(logn)\)，最坏情况\(O(logn)\)
Applicable Scene
B+树常用于操作系统文件系统以及部分数据库索引（MySQL）。
Questions
为什么B+树要这样设计？
这个跟它的使用场景有关。B+树在数据库的索引中用得比较多，数据库中select数据，很多时候会选中多条，比如按照id进行排序后选100条。如果是多条的话，B树可能需要跨层访问。而B+树由于所有数据都在叶子结点不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了。
为什么B+树相较于B树更适合实际操作系统的文件索引和数据库索引？
- 不同于B树只适合随机检索，B+树同时支持随机检索和顺序检索
- 单一节点存储更多的元素，非叶子节点占用内存小（方便加载到内存），使得相同高度下B+树能够载入更多的数据页
- 所有查询都要查找到叶子节点，查询性能稳定
- 所有叶子节点形成有序链表，便于范围查询
红黑树与B+树的区别
- 在内存中，红黑树比B树更优，但是涉及到磁盘操作，B/B+树更优。对于相同元素个数，B+树更矮更肥，在不同层间查找效率高，在从整颗树的角度，红黑树的结构更快。
既然增加树的路数可以降低树的高度，那么无限增加树的路数是不是可以有最优的查找效率？
- 这样会形成一个有序数组，文件系统和数据库的索引都是存在硬盘上的，如果数据量大的话，无法一次性加载到内存中。有序数组没法一次性加载进内存，这时候B+树的多路存储威力就出来了，可以每次加载B+树的一个结点，然后一步步往下找。
Reference
- 《数据结构、算法与应用》
- 蔡师弟整理的笔记
- 30张图带你彻底理解红黑树