红黑树前世今生
关键词：二叉搜索树、前驱节点、后继节点、B树、红黑树
什么是B树
前世
B树是一种相对于来说特殊二叉搜索树，多用于数据库和文件搜索系统中。
n阶B树的性质
B树是一种平衡的多路搜索树，拥有平衡二叉树的一些特性，与平衡二叉树的最大区别在于每个节点不再是只能存储一个元素，而且每个节点可以拥有多个子节点而像二叉平衡树只能拥有两个。
- B树每个节点最多可以存储超过2个元素，可以拥有超过2个子节点
- B树每个子节点的子树高度一致
- B树和二叉搜索树一样，左子树<根节点<右子树
- 根节点元素个数: 1≤ X ≤ n - 1
- 非根节点元素个数: n/2 - 1 ≤ x ≤ n - 1 (n/2 向上取整)
- 如果有子节点，子节点个数 y = x + 1,
- 根节点 2 ≤ y ≤ n
非根节点 n / 2 ≤ y ≤ n (n/2 向上取整)
数据库中一般使用的是200-300阶B树
4阶B树元素个数为(2-3-4)，所以4阶B树也叫2-4树或者2-3-4树
5阶B树元素个数为 3-4-5 所以5阶B树叫（3，5）树
6阶B树元素个数3-4-5-6，所以6阶B树叫（3，6）树
7阶B树元素个数为4-5-6-7，所以7阶B树叫（4，7）树
B树 VS 二叉搜索树
- B树与二叉搜索树逻辑上等价
- n阶B树最多需要log2 N代合并
- 多代节点合并可以获得超节点
- 2代合并最多拥有4个子节点
- 3代合并最多拥有8个子节点
- n代合并最多拥有2^n个子节点（至少是2^n阶B树）
B树的添加与上溢
上溢出（overflow）:添加元素到子节点后，该节点元素个数大于N时，我们称之为上溢出
B树的元素添加的位置一定是叶子节点
B树添加导致上溢
B树上溢最极端的情况是一直分裂到根节点
B树的删除与下溢
删除
删除叶子节点的话直接删除
删除的非叶子节点的话：1、先找到前驱或后继节点元素，覆盖需要删除的值，2、把前驱或后继元素删除（说明：一个树的前驱在左子树的最后边，后驱在右子树的最左边。）
- 非叶子节点前驱或后继元素，必然是在叶子节点中，所以真正删除的元素都是叶子节点
下溢出（underflow）：叶子节点被删除一个元素后，元素个数可能会低于最低限制 （n/2 - 1 向上取整）
下溢出的解决方案是旋转，总体元素是哪个方向失衡往哪个方向转，子树大小顺序不能乱
4阶B树
- 4阶B树所有节点都能储存的元素个数x: 1 ≤ x ≤ 3
- 4阶B树非叶子节点的子节点个数：2 ≤ y ≤ 4
为什么需要红黑树?
红黑树是在二叉搜索树的基础上对AVL树的改进，二叉搜索树顾名思义是对搜索算法的一种优化，能够大大减少我们元素对比的次数。红黑树在Java中的应用如HashSet(底层是数组单链表和红黑树)、数据库搜索也有应用。
什么是红黑树？
红黑树是一种自平衡的二叉搜索树也叫平衡二叉B树
红黑树5个性质
- 节点分为红色与黑色
- 根节点是黑色
- 叶子节点是黑色
- 不能有两个连续的红色节点
- 从任意节点到叶子节点上所有路径的黑色节点数目必须相等
红黑树等价变换
红黑树等价于4阶B树
红黑树添加失衡如何解决？
添加失衡
- Parrent节点为黑色时不需要处理
- Parrent节点为红色（Double Red）
- Uncle节点不是red: LL/RR LR/RL
- Uncle节点是red:
红黑树删除节点失衡如何解决？
红黑树 VS AVL树
搜索性能
添加
删除
实际应用
Java8中的hashMap是使用数组+链表实现的，在解决哈希碰撞时使用了红黑树。