数据结构相关的东西忘的差不多了，临时抱佛脚准备一波。
左堆
空路径长度：如果定义节点的空路径长度npl(x)为节点x到不满两个儿子的节点的最短路径，具有0个或1个儿子的节点的npl为0，空节点为-1，2个节点为1。
左堆：对堆中的每个节点x，左儿子的npl大于等于右儿子的npl。
有序表的查找
- 顺序查找
- 二分查找
- 差值查找
- 分块查找
查找树
二叉查找树
左子树的所有元素的键值都比根节点小。右子树所有元素的键值都比根节点大。
最坏的情况退化为单链表。
平均查找的时间复杂度是O（logN）
AVL树
节点的平衡度：节点的左子树的高度减去右子树的高度。
AVL树：满足每个节点平衡度都为0，-1，+1的二叉查找树
LL或RR情况：单旋转；LR或RL情况：双旋转；
所有操作在最坏情况都是对数级的
红黑树
红黑树时间代价也是对数级的。
红黑树是满足如下条件的二叉查找树：
- 每个节点为黑色或红色。
- 根节点为黑色。
- 如果一个节点为红色，子节点必须是黑色。
- 从任何一个节点出发到空节点的路径上必须包含相同数目的黑节点。
AA树
左儿子不能为红色的红黑树
伸展树
伸展树：将访问的节点向根节点旋转
B树
https://juejin.im/post/5d8194b5e51d4561e6237214
B+树
B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点。
内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
父节点存有右孩子的第一个元素的索引。
B+树相对于B树有一些自己的优势，可以归结为下面几点。
单一节点存储的元素更多，使得查询的IO次数更少，所以也就使得它更适合做为数据库MySQL的底层数据结构了。
所有的查询都要查找到叶子节点，查询性能是稳定的，而B树，每个节点都可以查找到数据，所以不稳定。
所有的叶子节点形成了一个有序链表，更加便于查找。
文件索引使用B树，B+树而不使用二叉树的原因：
索引存放在磁盘中，访问慢