一、动态数组
- 普通动态数组
- 环形动态数组
接口设计
int size(){} // 元素的数量boolean isEmpty(){} // 是否为空void add(E element){} // 添加元素到最后面void set(int index,E element){} // 设置index位置的元素void add(int index,E element){} // 在index位置插入一个元素void remove(int index){} // 删除index位置的元素boolean contains(E element){} // 是否包含某个元素E get(int index){} // 获取index位置的元素int indexOf(E element){} // 查看元素的索引void clear(){} // 清除所有元素
复杂度分析
-
add(int index,E element)
最好：O(1) 最坏：O(n) 平均：O(n) -
add(E element)
最好：O(1) 最坏：O(1) 平均：O(1) 均摊：O(1) -
remove(int index)
最好：O(1) 最坏：O(n) 平均：O(n) -
set(int index,E element)
最好：O(1) 最坏：O(1) 平均：O(1) -
get(int index)
最好：O(1) 最坏：O(1) 平均：O(1)
二、链表
- 单向链表
- 单向循环链表
- 双向链表
- 双向循环链表
- 静态链表
接口设计
同动态数组相同
复杂度分析
- 添加
最好：O(1) 最坏：O(n) 平均：O(n) - 添加元素到结尾
最好：O(1) 最坏：O(1) 平均：O(1) - 删除
最好：O(1) 最坏：O(n) 平均：O(n) - 设置index位置的值
最好：O(1) 最坏：O(n) 平均：O(n) - 获取inde位置的值
最好：O(1) 最坏：O(n) 平均：O(n)
双向链表 vs 动态数组
-
复杂度对比
Snip20200914_22.png 动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可以通过缩容来解决）
双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存浪费
如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择
如果频繁在头部进行添加、删除操作，建议选择使用双向链表（环形数组也可以）
如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表
如果有频繁的查询操作（随机访问操作），建议选择使用动态数组
三、栈
- 栈是一种特殊的线性表，只能在一端进行操作
- 往栈中添加元素的操作，一般叫做push，入栈
- 从栈中移除元素的操作，一般叫做pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）
- 后进先出的原则，Last In First Out ,LIFO
栈的接口设计
int size(){} // 元素的数量boolean isEmpty() {} // 是否为空void push(E element){} // 入栈E pop(){} // 出栈E top(){} // 获取栈顶元素void clear(){} // 清空
栈的实现
- 利用动态数组
- 利用双向链表
复杂度分析
时间复杂度: O(1)
四、队列
- 队列是一种特殊的线性表，只能在头尾两端进行操作
- 队尾（rear）：只能从队尾添加元素，一般叫做enQueue，入队
- 队头（front）：只能从队头移除元素，一般叫做deQueue，出队
- 先进先出的原则，First In First Out，FIFO
队列的类型
- 普通队列
只能从队尾添加元素，只能从队头移除元素，先进先出，优先使用双向链表实现 - 双端队列
可以从两端添加或者删除元素，优先使用双向链表实现 - 循环队列
其实队列底层也可以使用动态数组实现，并且各项接口也可以优化到O(1)的时间复杂度，这个用数组实现并且优化之后的队列叫做循环队列 - 循环双端队列
可以进行两端添加、删除操作的循环队列
队列的接口设计
1. 普通队列
int size(){} // 元素的数量boolean isEmpty(){} // 是否为空void clear(){} // 清空void enQueue(E element){} // 入队E deQueue(){} // 出队E front(){} // 获取队列的头元素
2. 双端队列
int size(){} // 元素的数量boolean isEmpty(){} // 是否为空void clear(){} // 清空void enQueueRear(E element){} // 从队尾入队E deQueueFront(){} // 从队头出队void enQueueFront(E element){} // 从队头入队E deQueueRear(){} // 从队尾出队E front(){} // 获取队列的头元素E rear(){} // 获取队列的尾元素
复杂度分析
时间复杂度：O(1)
五、二叉树
二叉树的特点
- 每个节点的度最大为2（最多拥有2颗子树）
- 左子树和右子树是有顺序的，因此二叉树是有序树
- 即使某节点只有一棵子树，也要区分左右子树
二叉树的性质
- 非空二叉树的第i层，最多有2^(i-1）个节点（i >= 1）
- 在高度为h的二叉树上最多有2^h-1个节点（h >= 1）
- 对于任何一棵非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则有：n0 = n2 + 1;
- 假设度为1的节点个数为n1,那么二叉树的节点总数 n = n0 + n1 + n2;
- 二叉树的边树 T = n1 + 2*n2 = n - 1 = n0 + n1 + n2 - 1
- 因此 n0 = n2 + 1;
真二叉树
所有节点的度要么为0，要么为2，也就是所有非叶子节点的度都为2
满二叉树
- 最后一层节点的度都为0，其他节点的度都为2，也就是所有非叶子节点的度都为2，且所有的叶子节点都在最后一层
- 在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多
- 满二叉树一定是真二叉树，真二叉树不一定是满二叉树
- 假设二叉树的高度为h(h>=1),那么
- 第 i 层的节点数量：2^(i-1)
- 叶子节点数量：（2^(h-1)）
- 总节点数量 n = 2^h - 1;
- h = log2(n+1)
完全二叉树
- 完全二叉树：对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应
- 叶子节点只会出现最后2层，最后1层的叶子节点都靠左对齐
- 完全二叉树从根节点至倒数第2层是一棵满二叉树
- 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
完全二叉树的性质
度为1的节点只有左子树
度为1的节点要么是1个，要么是0个
同样节点数量的二叉树，完全二叉树的高度最小
-
假设完全二叉树的高度为h(h>=1)，那么
- 至少有2^(h-1)个节点
- 最多有2^h - 1 个节点
- 假设总节点数量为n
2^(h-1) <= n < 2^h
h-1 <= log2(n) < h
那么 h = floor(log2(n)) + 1 (floor是向下取整，另外ceiling是向上取整)
-
一棵有n个节点的完全二叉树（n > 0 ），从上到下、从左到右对节点从1开始进行编号，对任意第i个节点
- 如果 i = 1 ，它是根节点
- 如果 i > 1，它的父节点编号为 floor( i/2 )
- 如果 2i <= n，它的左子节点编号为2i
- 如果 2i > n ，它无左子节点
- 如果 2i + 1 <= n， 它的右子节点编号为 2i + 1
- 如果 2i + 1 > n ，它无右子节点
-
一棵有n个节点的完全二叉树（n > 0 ），从上到下、从左到右对节点从0开始进行编号，对任意第i个节点
- 如果 i = 0 ，它是根节点
- 如果 i > 0，它的父节点编号为 floor( (i-1)/2 )
- 如果 2i + 1 <= n-1，它的左子节点编号为2i+ 1
- 如果 2i + 1 > n - 1 ，它无左子节点
- 如果 2i + 2 <= n - 1， 它的右子节点编号为 2i + 2
- 如果 2i + 2 > n - 1，它无右子节点
完全二叉树面试题
如果一颗完全二叉树有768个节点，求叶子节点的个数。
解题思路：
- 假设叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2
- 总节点个数n = n0 + n1 + n2 ，而且n0 = n2 + 1，得出n = 2n0 + n1 -1
- 又已知完全二叉树的n1要么为0，要么为1
- n1为1时，n = 2n0，n必然是偶数，叶子节点个数n0 = n/2，非叶子节点个数 n1 + n2 = n/2
- n1为0时，n = 2n0 - 1，n必然是奇数，叶子节点个数n0 = （n + 1）/2，非叶子节点个数 n1 + n2 = （n - 1） /2
总结：
叶子节点个数 n0 = floor((n+1)/2) = ceiling(n/2)
非叶子节点个数 n1+ n2 = floor(n/2) = ceiling( (n-1)/2)
因此叶子节点个数为384
二叉树的遍历
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
二叉树的高度
判断一棵二叉树是否为完全二叉树
前驱节点
后继节点
表达式树
如果将表达式的操作数作为叶子节点，运算符作为父节点（假设只是四则运算），这些节点刚好可以组成一棵二叉树
比如表达式：A / B + C * D - E，组成的二叉树如下：
如果对这棵二叉树进行遍历
- 前序遍历，刚好就是前缀表达式
-+/AB*CDE - 中序遍历，刚好就是中缀表达式
A/B+C*D-E - 后序遍历，刚好就是后缀表达式
AB/CD*+E-
六、二叉搜索树
二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称BST，又被称为二叉查找树、二叉排序树
二叉搜索树的性质
- 二叉搜索树的任意一个节点的值都大于其左子树所有节点的值
- 二叉搜索树任意一个节点的值都小于其右子树所有节点的值
- 二叉搜索树的左右子树也是一棵二叉搜索树
- 二叉搜索树存储的元素必须具备可比较性
- 二叉搜索树存储的元素不允许为null
二叉搜索树的接口设计
int size() // 元素的数量boolean isEmpty() // 是否为空void clear() // 清空所有元素void add(E element) // 添加元素void remove(E element) // 删除元素boolean contains(E element) // 是否包含某元素
接口的实现
- 添加
- 如果添加的是第一个节点，创建节点并赋值给根节点，size++
- 如果添加的不是第一个节点，从根节点开始遍历，找到父节点parent，创建节点并添加到父节点的left或者right；如果遇到相等的值覆盖
- 删除
- 删除叶子节点，直接删除
- 删除度为1的节点，用子节点替代原节点的位置
- 删除度为2的节点，先用前驱或者后继节点的值覆盖原节点的值，然后删除相应的前驱或者后继节点
复杂度分析
二叉搜索树的添加、删除、搜索的时间复杂度和树的高度有关，也就是O(h)
- 最好情况：二叉搜索树的添加、删除、搜索的时间复杂度都为O(logn)
如果按照7、4、9、2、5、8、11的顺序添加节点，会得到一棵满二叉搜索树，已知满二叉树的h = log2(n+1)，所以当二叉搜索树是一棵满二叉树的时候，二叉搜索树的添加、删除、搜索的时间复杂度都为O(logn)
- 最坏情况：二叉搜索树退化成链表，添加、删除、搜索的时间复杂度都为O(n)
如果按照从小到大添加节点，二叉搜索树退化成了链表，h = n，二叉搜索树的添加、删除、搜索的时间复杂度都为O(n)
七、平衡二叉搜索树
二叉搜索树在添加、删除节点时，都可能会导致二叉搜索树退化成链表，为了防止二叉搜索树退化成链表，让添加、删除、搜索的复杂度维持在O(logn)，我们需要在添加或者删除节点操作之后，想办法让二叉搜索树恢复平衡。
平衡：当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡（高度越低）
最理想平衡，就是像完全二叉树、满二叉树那样，高度是最小的
二叉搜索树调整方案：用尽量少的调整次数达到适度平衡即可，一棵达到适度平衡的二叉搜索树，可以称之为平衡二叉搜索树
平衡二叉搜索树
Balanced Binary Search Tree，简称 BBST，经典常见的平衡二叉搜索树有：
AVL树
红黑树
一般也称它们为：自平衡的二叉搜索树
八、AVL树
AVL树的特点
- 每个节点的平衡因子（某节点的左右子树的高度差）只可能是1、0、-1（绝对值<=1，如果超过1，称之为失衡）
- 每个节点的的左右子树的高度差不超过1
- 搜索、添加、删除的时间复杂度是O(logn）
添加导致的失衡
- 最坏情况：可能会导致所有祖先节点都失衡
- 父节点、非祖先节点，都不可能失衡
- 只要让高度最低的失衡点恢复平衡，整棵树就恢复平衡，仅需O(1)次调整
恢复平衡的几种情况：
首先找到失衡节点g，接着找到它左右子树较高的子节点p，接着找到p左右子树较高的子节点n，然后判断n位于g的位置
- LL
g右旋（zig），让父节点成为这棵树的根节点，是整棵树都达到平衡 - RR
g左旋（zag），让父节点成为这棵树的根节点，使整棵树都达到平衡 - LR
p左旋，g右旋 - RL
p右旋，g左旋
private void rotateRight(Node<E> grand){
Node<E> parent = grand.left;
Node<E> child = parent.right;
grand.left = child;
parent.right = grand;
afterRotate(grand,parent,child);
}
private void rotateLeft(Node<E> grand){
Node<E> parent = grand.right;
Node<E> child = parent.left;
grand.right = child;
parent.left = grand;
afterRotate(grand,parent,child);
}
private void afterRotate(Node<E> grand,Node<E> parent,Node<E> child){
// 更新parent的父节点
parent.parent = grand.parent;
// 更新parent在父节点中的位置
if (grand.isLeftChild()){
grand.parent.left = parent;
}else if(grand.isRightChild()){
grand.parent.right = parent;
}else {
root = parent;
}
//更新child的父节点
if (child != null){
child.parent = grand;
}
//更新grand的父节点
grand.parent = parent;
//更新高度
updateHeight(grand);
updateHeight(parent);
}
删除导致的失衡
可能会导致父节点或祖先节点失衡（只有一个节点会失衡），其他节点都不可能失衡
如果恢复平衡之后，树的高度和之前不一样，可能会导致更高层的祖先节点失衡，需要再次恢复平衡，极端情况下，所有祖先节点都需要进行恢复平衡的操作，最多需要O(logn)次调整
时间复杂度分析
- 搜索：O(logn)
- 添加：O(logn)，仅需O(1)次的选择操作
- 删除：O(logn)，最多需要O(logn)次的选择操作
九、B树
B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现。
B树的特点
- 1个节点可以存储超过2个元素、可以拥有超过2个子节点
- 拥有二叉搜索树的一些性质
- 平衡，每个节点的所有子树高度一致
- 比较矮
m阶B树的性质
m阶：一个节点最多拥有m个子节点
假设一个节点存储的元素个数为x
- 根节点：1 <= x <= m-1
- 非根节点：⌈m/2⌉ - 1 <= x <= m-1（⌈⌉ ：向上取整，⌊⌋：向下取整）
- 如果有子节点，子节点个数 y = x+1
- 根节点：2 <= y <= m
- 非根节点：⌈m/2⌉ <= y <= m
比如m = 3, 2<=y<=3,因此可以称为(2,3)树，2-3树；
比如m = 4, 2<=y<=4,因此可以称为(2,4)树，2-3-4树；
比如m = 5, 3<=y<=5,因此可以称为(3,5)树，3-4-5树；
比如m = 6, 3<=y<=6,因此可以称为(3,6)树;
比如m = 7, 4<=y<=7,因此可以称为(4,7)树;
B树VS二叉搜索树
B树和二叉搜索树，在逻辑上是等价的
- 多代节点合并，可以获得一个超级节点
- 2代合并的超级节点，最多拥有4个子节点（至少是4阶B树）
- 3代合并的超级节点，最多拥有8个节点（至少是8阶B树）
- m代合并的超级节点，最多拥有2^n 个子节点（至少是2^n阶B树）
- m阶B树，最多需要log2(m)代合并
搜索
和二叉搜索树的搜索类似
- 先在节点内部从小到大开始搜索元素
- 如果命中，搜索结束
- 如果未命中，再去对应的子节点中搜索元素，重复步骤1
添加
新添加的元素必定是添加到叶子节点
假设下图是一个4阶B树
插入55
插入95
插入98
最右下角的叶子节点的元素个数将超过限制，这种现象可以称之为：上溢
添加 -上溢的解决
- 上溢节点的元素个数必然等于m
- 假设上溢节点最中间元素的位置为k，将k位置的元素向上与父节点合并
- 将[0,k-1]和[k+1,m-1]位置的元素分裂成2个子节点，这2个子节点的元素个数，必然不会低于最低限制
- 一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决
- 最极端的情况，有可能一直分裂到根节点
删除
- 删除-非叶子节点
假如需要删除的元素在非叶子节点中- 先找到前驱或后继元素，覆盖所需要删除元素的值
- 再把前驱或后继元素删除
非叶子节点的前驱或者后继元素，必定在叶子节点中，所以真正删除的元素在叶子节点中，因此，真正的删除元素都是发生在叶子节点中
- 删除 - 叶子节点
假如需要删除的元素在叶子节点中，那么直接删除即可。但是叶子节点被删掉一个元素后，元素个数可能会低于最低限制，这种现象称为下溢
删除 - 下溢的解决
- 下溢节点的元素数量必然等于⌈m/2⌉ - 2
- 如果下溢节点临近的兄弟节点，有至少⌈m/2⌉个元素，可以向其借一个元素
- 将父节点的元素b插入到下溢节点的0位置（最小位置）
- 用兄弟节点的元素a（最大的元素）替代父节点的元素b
-
这种操作可以称为：旋转
Snip20200901_20.png
- 如果下溢节点临近的兄弟节点，只有⌈m/2⌉-1个元素
- 将父节点的元素b挪下来跟左右子节点进行合并
- 合并后的节点元素个数等于⌈m/2⌉ + ⌈m/2⌉ - 2，不超过m-1
-
这个操作可能会导致父节点下溢，依然依照上述方法解决，下溢现象可能会一直往上传播。
Snip20200901_22.png
