一、树
1.基本概念
- 用来模拟具有树状结构性质的数据集合。
- 连接的节点具有父子关系，和图相比树能表示节点间的层次关系。
2、名词解释
- 节点的度：一个节点子树的个数
- 树的度：一个树中，所以节点的度的最大值就成为树的度
- 根节点：树的第一层的节点，也是没有双亲的节点
-
高度/深度：从根开始到最多层次，最底下的节点，其长度就成为树的高度，根的高度为1
3、二叉树
- 其每一个节点的度都<=2。
- 在二叉树第i层最多有2^(i-1)个节点。
- 深度为k的二叉树最多有2^k-1个节点。
- 对于任何一棵二叉树T,叶子节点数为n0,度为2的节点数为n2则n0=n2 + 1。
二叉树的特殊类型有：满二叉树、完全二叉树、二叉查找树、平衡二叉查找树（AVL树）、红黑树
3.1 满二叉树
除了最后一层，其它层的结点都有两个子结点。
- 在二叉树第i层有2^(i-1)个节点。
- 深度为k的二叉树有2^k-1个节点。
3.2 完全二叉树
除了最后一层结点，其它层的结点数都达到了最大值；同时最后一层的结点都是按照从左到右依次排布。
- 具有n个节点的完全二叉树的深度为[log2n] + 1,
- 如果对一棵有n个节点的完全二叉树(深度为[log2n] + 1)的节点按层序编号，对任一节点i(1<=i<=n)有:
- 如果i=1,则i是根节点,无双亲;否则其双亲是 i/2.
- 如果2i>n,则节点i无左孩子(节点i为叶节点);否则左孩子为2i.
- 如果2i+1>n,则节点i无右孩子(节点i为叶子节点);否则右孩子为2i+1.
3.3 二叉查找树
是一棵空树，或者：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
3.4 平衡二叉查找树（AVL树）
- 平衡二叉树的产生是为了解决二叉排序树在插入时发生线性排列，退化成链表的现象。
四种旋转方式：
（1）LR型：左叶子结点插入右子节点
先通过以3为旋转中心，进行左旋转，结果如图所示，然后再以7为旋转中心进行右旋转，旋转后恢复平衡了。
（2）LL型：左叶子结点插入左子节点
只用经过一次右旋转
（3）RR型：右叶子结点插入右子节点
对插入节点的父节点进行左旋转
（4）RL型：
对插入节点先右旋转再左旋转
3.5 红黑树
红黑树是一种自平衡的二叉搜索树，它保证了每个节点都有一个颜色属性，可以是红色或者黑色，并且满足以下五个性质：
- 根节点是黑色的。
- 每个叶子节点（NULL节点）是黑色的。
- 如果一个节点是红色的，则其子节点必须是黑色的。
- 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。
- 空节点被视为黑色。
这些性质确保了红黑树具有较好的平衡性和搜索效率，在插入、删除等操作时能够保持树的平衡，使得最坏情况下的时间复杂度为 O(log n)。
与AVL树的区别：
1、红黑树的插入和删除操作效率比AVL树高，因为红黑树在插入和删除节点时只需进行 O(1) 次数的旋转和变色操作，即可保持基本平衡状态，而不需要像 AVL 树一样进行 O(logn) 次数的旋转操作。
2、红黑树并不追求严格的平衡，而是大致的平衡。正因如此，红黑树的查询效率稍有下降，因为红黑树的平衡性相对较弱，可能会导致树的高度较高，
3、多叉树
B树和B+树都是一种多叉平衡搜索树
3.1B树
B树的定义如下，假设有M个子节点：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字大于K[i-1],小于 K[i]的子树；
8.所有叶子结点位于同一层；
3.2 B+树
其定义基本与B树同，除了：
1.非叶子结点的子树指针与关键字个数相同；
2.非叶子结点的子树指针P[i]，指向关键字值大于等于K[i]小于K[i+1] （左闭右开）的子树
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；
区别：
| B树 | B+树 | |
| 存储结构 | 每个节点既存储数据，也存储子节点指针 | 非叶子节点只存储子节点指针，数据只存储在叶子节点中， b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖” |
| 叶子节点 | 叶子节点可以包含数据，也可以不包含数据 | 叶子节点必须包含全部数据，且按照键值大小排序形成一个链表。 |
| 遍历方式 | 为了遍历全部数据，需要对每个节点进行遍历 | B+树可以通过遍历叶子节点的链表来获取所有数据 |
| 范围查询 | 范围查询需要对每个节点进行遍历，相对较慢 | 通过遍历叶子节点的链表来快速定位并返回符合条件的数据 |
| 关键字个数 | 非叶子结点的关键字个数=指向儿子的指针个数-1 | 非叶子结点的子树指针与关键字个数相同 |
| 子节点指针的范围 | 开区间，P[i]指向关键字大于K[i-1],小于 K[i]的节点 | 左闭右开，P[i]指向关键字值大于等于K[i]小于K[i+1] （左闭右开）的节点 |
二、堆
-
堆在物理层面上，表现为一组连续的数组区间；将整个数组看作是堆。
堆在逻辑结构上，一般被视为是一颗完全二叉树。
- 对于任意一个父节点的序号n来说（这里n从0算），它的子节点的序号一定是2n+1，2n+2，因此可以直接用数组来表示一个堆。
- 堆中某个节点的值总是不大于或不小于其父节点的值。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
public class HeapTest {
/**
* 小堆的向下调整，要求满足向下调整的前提
* @param array 堆所在的数组
* @param size 前 size 个元素视为堆中的元素
* @param index 要调整位置的下标
*/
public static void shiftDown(long[] array, int size, int index) {
// 只要看到 int 类型的，基本就是下标或者个数，不是元素
// 这里直接 while(true)即可
// while (2 * index + 1 < size) { 如果这么写，下面就不用再进行叶子的判断
while (true) {
// 1. 判断 index 所在位置是不是叶子
// 逻辑上，没有左孩子一定就是叶子了（因为完全二叉树这个前提）
int left = 2 * index + 1;
if (left >= size) {
// 越界 -> 没有左孩子 -> 是叶子 -> 调整结束
return; // 循环的出口一：走到的叶子的位置
}
// 2. 找到两个孩子中的最值【最小值 via 小堆】
// 先判断有没有右孩子
int right = left + 1; // right = 2 * index + 2
int min = left; // 假设最小值就是左孩子，所以 min 保存的最小值孩子所在的下标
if (right < size && array[right] < array[left]) {
// right < size 必须在 array[right] < array[left] 之前，不能交换顺序
// 因为先得确定有右孩子，才有比较左右孩子的意义
// 有右孩子为前提的情况下，然后右孩子的值 < 左孩子的值
min = right; // min 应该是右孩子所在的下标
}
// 3. 将最值和当前要调整的位置进行比较，判断是否满足堆的性质
if (array[index] <= array[min]) {
// 当前要调整的结点的值 <= 最小的孩子值；说明这里也满足堆的性质了，所以，调整结束
return; // 循环的出口一：循环期间，已经满足堆的性质了
}
// 4. 交换两个值，物理上对应的就是数组的元素交换 min 下标的值、index 下标的值
long t = array[index];
array[index] = array[min];
array[min] = t;
// 5. 再对 min 位置重新进行同样的操作（对 min 位置进行向下调整操作）
index = min;
}
}
public static void main(String[] args) {
long[] array = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
shiftDown(array,9,0);
}
}
2、堆的插入
堆的插入总共需要两个步骤：
1️⃣. 先将元素放入到最后
2️⃣. 将最后新插入的节点向上调整，直到满足堆的性质 ；
1 // 注意：上图是按照大堆来调整的，注意比较方式 2 public void shiftUp(int child) { 3 // 找到child的双亲 4 int parent = (child - 1) / 2; 5 6 while (child > 0) { 7 // 如果双亲比孩子大，parent满足堆的性质，调整结束 8 if (array[parent] > array[child]) { 9 break; 10 } 11 else{ 12 // 将双亲与孩子节点进行交换 13 int t = array[parent]; 14 array[parent] = array[child]; 15 array[child] = t; 16 17 // 小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增 18 child = parent; 19 parent = (child - 1) / 1; 20 } 21 } 22 }
3. 堆的删除(poll)
具体如下：（ 注意：堆的删除一定删除的是堆顶元素。）
1️⃣. 将堆顶元素对堆中最后一个元素交换；
2️⃣. 将堆中有效数据个数减少一个；
3️⃣. 对堆顶元素进行向下调整；
1 public long poll() { 2 // 返回并删除堆顶元素 3 if (size < 0) { 4 throw new RuntimeException("队列是空的"); 5 } 6 7 long e = array[0]; 8 9 // 用最后一个位置替代堆顶元素，删除最后一个位置 10 array[0] = array[size - 1]; 11 array[size - 1] = 0; // 0 代表这个位置被删除了，不是必须要写的 12 size--; 13 14 // 针对堆顶位置，做向下调整 15 shiftDown(array, size, 0); 16 17 return e; 18 }