B树
B 树又叫平衡多路查找树。B树是一种自平衡树，是AVL树的一般化，它维护有序数据并允许以对数时间进行搜索，顺序访问，插入和删除。
与AVL树不同的是，B树非常适合读取和写入相对较大的数据块（如光盘）的存储系统。它通常用于数据库和文件系统。
一颗m阶的B树满足如下条件：
- 每个节点最多只有
m个子节点。 - 除根节点外，每个非叶子节点具有至少有
m/2（向下取整）个子节点。 - 非叶子节点的根节点至少有两个子节点（不然就变成单支了）。
- 有k颗子树的非叶节点有
k-1个键，键按照递增顺序排列。 - 叶节点都在同一层中。
注意: B树的叶子节点指的是最下面一层的空节点，代表查找失败的情况，不计算在层高里，属于外部节点。
B树的阶： B树中节点的子节点数目的最大值
内部节点：除叶子节点和根节点之外的所有节点，即拥有父节点和子节点的节点。
容易知道 在具有n个关键字的B树中 具有n+1种查找失败的情况 也就是查找到任意两个相邻关键字之间的情况
因此 在具有n个关键字的B树中 叶子节点有n+1个
由此可以推导得到具有n个关键字的B树的最大高度和最小高度
B树的插入
针对m阶高度h的B树，插入一个元素时，首先在B树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素。
- 若该节点元素个数小于m-1，直接插入；
- 若该节点元素个数等于m-1，引起节点分裂；以该节点中间元素为分界，取中间元素（偶数个数，中间两个随机选取）插入到父节点中；
- 重复上面动作，直到所有节点符合B树的规则；最坏的情况一直分裂到根节点，生成新的根节点，高度增加1。
以一颗5阶B树的插入为例
B树的删除
首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除；删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中，然后是移动之后的情况；如果没有，直接删除。
- 某结点中元素数目小于（m/2）, (m/2)向下取整，则需要看其某相邻兄弟结点是否丰满；
如果丰满（结点中元素个数大于(m/2)），则向父节点借一个元素来满足条件； - 如果其相邻兄弟都不丰满，即其结点数目等于(m/2)，则该结点与其相邻的某一兄弟结点进行“合并”成一个结点；
以5阶B树为例
B+树
B+树是应文件系统所需而产生的B树的变形树
一颗m阶的B+树满足如下条件：
- 每个节点最多只有m个子节点。
- 除根节点外，每个非叶子节点具有至少有 m/2（向下取整）个子节点。
- 非叶子节点的根节点至少有两个子节点。
- 有k颗子树的非叶节点有k个键，键按照递增顺序排列。
- 叶节点都在同一层中。
B树与B+树的区别
| B+树 | B树 |
|---|---|
| 有m颗子树的节点中含有m个关键码 | 有m颗子树的节点中含有m-1个关键码 |
| 所有的叶子结点中包含了完整的索引信息，包括指向含有这些关键字记录的指针，中间节点每个元素不保存数据，只用来索引 | B树中非叶子节点的关键码与叶子结点的关键码均不重复，它们共同构成全部的索引信息 |
| 所有的非叶子节点可以看成是高层索引，结点中仅含有其子 树根结点中最大(或最小)关键字 | B树的非叶子节点包含需要查找的有效信息 |
B+树的检索
在B+树中检索关键码key的方法与B树的检索方式相似，但若在内部节点中找到检索的关键码时，检索并不会结束，要继续找到B+树的叶子结点为止。
B+树的插入
与B树的插入操作相似，总是插到叶子结点上。
当叶节点中原关键码的个数等于m时，该节点分裂成两个节点，分别使关键码的个数为 (m+1)/2 （向上取整）和 (m+1)/2 （向下取整）。
B+树的删除
仅在叶节点删除关键码。
若因为删除操作使得节点中关键码数少于 m/2（向下取整）时，则需要调整或者和兄弟节点合并。
合并的过程和B树类似，区别是父节点中作为分界的关键码不放入合并后的节点中。
红黑树
红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）。它同时满足以下特性：
- 节点是红色或黑色
- 根节点是黑色
- 叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），
null节点的父节点在红黑树里不将其看作叶子节点 - 红色节点的子节点都是黑色
- 红色节点的父节点都是黑色
- 从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
- 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
红黑树与B树的等价变换：
- 红黑树 和 4阶B树（2-3-4树）具有等价性
- 黑色节点与它的红色子节点融合在一起，形成1个B树节点
- 红黑树的黑色节点个数 与 4阶B树的节点总个数相等
- 在所有的B树节点中，永远是黑色节点是父节点，红色节点是子节点。黑色节点在中间，红色节点在两边。
旋转操作
旋转操作分为左旋和右旋，左旋是将某个节点旋转为其右孩子的左孩子，而右旋是节点旋转为其左孩子的右孩子。
红黑树的插入操作
红黑树的插入过程和二叉查找树插入过程基本类似，不同的地方在于，红黑树插入新节点后，需要进行调整，以满足红黑树的性质。
性质1规定红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色，原因也不难理解。如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点，这个调整起来会比较麻烦。
如果插入的节点是红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况。这种情况下，通过变色和旋转进行调整即可，比之前的简单多了。
所以插入的时候将节点设置为红色，可以保证满足性质1、2、3、5 ，只有性质4不一定满足，需要进行相关调整。如果是添加根节点，则将节点设定为黑色。
进行插入操作的时候，只会将节点插入到叶子节点中，总共就会有12种情况，其中4种情况满足红黑树的性质，8种情况不满足红黑树性质。
parent节点为黑色时
这种条件下满足性质，无需调整，共四种情况
LL和RR插入情况
RR情况：父节点为祖父节点的右节点，插入节点为父节点的右节点
LL 情况：父节点为祖父节点的左节点，插入节点为父节点的左节点
判定条件：uncle 不是红色节点。
修复办法：旋转之后染色即可
- parent 染成黑色，grand 染成红色
- grand 进行单旋操作
- LL：右旋转
- RR：左旋转
RL和LR插入情况
RL情况：父节点为祖父节点的右节点，插入节点为父节点的左节点
LR情况：父节点为祖父节点的左节点，插入节点为父节点的右节点
与RR和LL基本类似 旋转染色即可
判定条件：uncle 不是红色节点。
修复办法：旋转之后染色即可
- 插入节点染成黑色
- grand 染成红色，进行双旋操作
- LR：parent 左旋转， grand 右旋转
- RL：parent 右旋转， grand 左旋转
上溢情况
LL情况：父节点为祖父节点的左节点，插入节点为父节点的左节点。并且构成的新的B树节点已经超过了B树节点容量大小范围。
判定条件：uncle 是红色节点。
满足这个条件的就都是上溢的情况，上溢的修复只需要染色，不需要旋转。
修复步骤总结：
- parent、uncle 染成黑色，grand 向上合并
- 将向上合并的grand染成红色，相对上一层，就当做是新添加的节点，再次来一遍插入情况的判断，进行处理。
同理有上溢RR，LR，RL的情况
总结
插入一共有12种情况：
-
插入节点的父节点是黑色的情况有4种
这种情况仍然会维持红黑树的性质，则不需要进行额外处理。 -
插入节点的父节点是红色的情况有8种
这种情况不满足红黑树的性质4，需要进行额外的修复处理。
这8种情况中：
1） 叔父节点不是红色的情况有4种，这些情况都是非上溢，需要通过重新染色和旋转来进行修复
2） 叔父节点是红色的情况有4种，这些情况都是上溢的，只需要通过祖父节点上溢合并和染色即可完成修复
红黑树的删除操作
在红黑树中，被删除的节点一定在最后一层。
删除红色节点
如果删除的节点是红色直接删除，不用作任何调整。因为删除最后一层的红色节点，并没有影响红黑树的任何性质。
删除黑色节点
有3种情况：
-
拥有 2 个红色子节点的黑色节点
- 不可能被直接删除，因为会找它的子节点替代删除，因此不用考虑这种情况
-
拥有 1 个红色子节点的黑色节点
-
黑色叶子节点
删除拥有1个红色子节点的黑色节点
对于一个二叉树来说，删除一个度为1的节点（度指的是一个节点的子节点个数），将其删除后需要用它唯一的子节点来进行替换。而红黑树的这种情况的判定条件，就是判定要替代删除节点的子节点是不是红色
判定条件：用以替代的子节点是红色节点
修复步骤总结：
- 用删除节点的唯一子节点对其进行替代
- 将替代节点染成黑色
删除黑色叶子节点——删除节点为根节点
一棵红黑树只有一个黑色根节点（也就是唯一的一个叶子节点，整个红黑树只有这一个黑色节点），可直接删除该节点，无需做其他操作。
删除黑色叶子节点——删除节点的兄弟节点为黑色
兄弟节点至少有1个红色子节点
因为兄弟节点有红色子节点，所以可以借出一个节点来进行修复。
判定条件：兄弟节点至少有 1 个红色子节点
修复步骤总结：
- 进行旋转操作
- 旋转之后的中心节点继承父节点（删除节点的父节点）的颜色
- 旋转之后的左右节点染为黑色
兄弟节点没有红色子节点
当删除节点的兄弟节点没有红色节点可以借出的情况下，就需要父节点来向下合并进行修复
判定条件：兄弟节点没有1个红色子节点
修复步骤总结：
- 父节点向下与兄弟节点进行合并
- 将兄弟染成红色、父节点染成黑色即可修复红黑树性质
- 如果父节点是黑色，直接将父节点当成被删除的节点处理，来修复父节点的下溢情况
删除黑色叶子节点——删除节点的兄弟节点为红色
判定条件：兄弟节点是红色
修复步骤总结：
- 兄弟节点染成黑色，父节点染成染成红色，对父节点进行右旋
- 于是又回到兄弟节点是黑色的情况（侄子节点变为兄弟节点），继续使用兄弟节点为黑色的方法进行修复
哈夫曼树
哈夫曼树是是指最优m叉树,也叫做严格m叉树, 即m叉树的带权路径长度达到最小。
哈夫曼树（Huffman Tree）是一种特殊的二叉树，用于编码和压缩数据。哈夫曼树的构建基于哈夫曼编码算法，该算法可以根据数据的出现频率来生成最优的编码方案，以便在压缩数据时能够获得最小的压缩比。
哈夫曼树的构建过程通常如下：
-
统计数据中每个字符出现的频率，并将其存储在一个频率表中。
-
将频率表中的每个字符和其出现频率作为一个叶子节点，构建一个森林。
-
从森林中选择两个频率最小的节点，将它们合并为一个新节点，并将新节点的权值设置为两个节点的权值之和。
-
将新节点插入森林中，并从森林中删除原来的两个节点。
-
重复步骤3和4，直到森林中只剩下一个节点，即为哈夫曼树的根节点。
在哈夫曼树中，每个叶子节点表示一个字符，其权值为该字符在数据中出现的频率。每个非叶子节点表示一个编码，其权值为其子节点的权值之和。哈夫曼编码是一种前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀，以便在解码时能够唯一确定每个字符的编码。
哈夫曼树上的节点度要么为0要么为满。
所以m叉哈夫曼树 如果有n个叶子节点
- 其总结点数为
n+x（x为满度节点数量） - 又可知 总结点数还可表示为
1+m*x即计算总入度+1=总分支数加上根节点
由此可得等式 n+x = 1 + m*x 从而求解n或者m或x