一、前置概念
1.B树
多路平衡树：多路平衡二叉树，B树，B+树，红黑树
索引存储
1.外存和内存进行数据交互比较慢
2.数据管理方案：通常会使用索引表进行数据查找和交互，由于外存中数据比较多，建立的索引表中索引数据也会比较多
分页：一页就是一次磁盘 I/O 的数据量（在后面举例中假设为4K）。一个索引节点也会被设计成一页的大小
通过树型结构对索引进行管理：一个树中的节点存放一页（4K）个数据--->多路查找树
多路查找树+不允许有高度差--->多路平衡树
多路平衡树的例子：2-3树
由以下节点组成：
（1）二叉（2-）节点：含有一个数据和两个孩子的节点，其中左子树的值均小于父亲节点的值，右子树的值均大于父亲节点的值
（2）三叉（3-）节点：含有两个孩子和三个孩子的节点，并且数据之间保持顺序性，左⼦树所有元素的值均⼩于它的⽗结点，中⼦树所有元素的值都位于⽗结点两个元素之间，右⼦树所有元素的值均⼤于它的⽗结点。
下图为一棵2-3树：
同理，下图为2-3-4树：
多路平衡树：2-3-4-......-n树：树的度（阶）：n ----->n阶B树
2-3树---->3阶B树
2-3-4树--->4阶B树
B树：表示的是一类树，它允许一个节点可以有多于两个子节点，同时，也是自平衡的。叶子节点的高度都是相同的。所以，为了更好地区分一颗B树到底属于哪一类树，我们给它一个新的属性：度（Degree）。具有度为3的B树，表示一个节点最多有三个子节点，也就是2-3树的定义。具有度为4的B树，表示一个节点最多有四个子节点，也就是2-3-4树的定义。
缺陷：按范围查找元素，例如查找大于B且小于K的所有元素，很难查找。所以后续出现了B+树。
2.红黑树
概念
用二叉树表示的4（或3）阶B树，把4阶B树中的3-4-节点拆分成2-节点，就是红黑树。
红黑树是特殊的二叉排序树，不是二叉平衡树。
红黑树的节点分类：
1.内部节点：内部叶子节点和其他节点
2.外部节点（叶子节点）：NULL节点
注意：无特殊说明，红黑树中叶子节点指外部节点
上图就是红黑树
红黑树性质
1、节点是红⾊或者⿊⾊
2、根结点是⿊⾊
3、所有的叶⼦结点是⿊⾊（注意：这里的叶⼦结点是外部节点，也就是NULL结点）
4、每个红⾊结点的两个⼦结点都是⿊⾊（从根结点到每个叶⼦结点的路径不能有两个连续的红结点）
5、从根结点到每个叶⼦结点的所有路径都包含相同数⽬的⿊⾊结点（都是未拆分前B树到每个内部叶子节点的距离，而B树到每个内部叶子节点的距离相同）
黑高(bh)：从根节点到叶子节点的路径上黑色节点的数目
口诀：左根右，根叶黑，不红红，黑路同
左子树<根节点<右子树；根节点和叶子节点是黑色的；没有两个连续的红色；从根节点到任意叶子节点的路径上黑色节点的数目相同
两个结论
1.从根节点到叶子节点的最长路径不大于最短路径的两倍
最短路径：只有黑色节点的是最短的
最长路径：在最短路径的基础上，每两个节点分下去一个红色节点
2.有n个内部节点的红黑树，其高度h<=2log(n+1) --->红黑树操作的时间复杂度（logn)
黑高（bh）内部节点的数目最少是多少个？只有黑色节点的满二叉树 n>=2*bh-1
---->h<=2log(n+1)
BST-->AVL--->平衡因子的约束太严格了，需要频繁调整----->红黑树：一棵子树的高度最多可以是另一棵子树的2倍
二、红黑树操作
查找
特殊的BST，同BST的查找操作
插入
在一棵RBT（红黑树）中插入一个数据
1.
typedef struct RBTreeNode{ int data;//数据 struct RBTreeNode* l; struct RBTreeNode* r; int color; // 0是红色，1是黑色 struct RBTreeNode* parent;//双亲结点（可写可不写） }RBTNode,*RBTree;2.z插入位置：同BST，先执行BST的插入操作：把节点插入到树中
3.确定z的初始颜色：
（1）黑色：一定破坏“黑路同”----->每次插入都得调整---->产生AVL的弊端
（2）红色：可能会破坏“不红红”，z的父亲也红色才需要调整--->不需要频繁调整
因此，z的初始颜色先定为红色。
注意：如果是在一棵空树上插入节点，根结点直接赋成黑色就行
4.如果破坏了“不红红”，如何调整？
（1）染色：红色--->黑色，黑色--->红色
（2）旋转：LL，LR，RR，RL
插入一个节点z，z初始是红色的，
进行插入的几种情况
若树为空：如果是在一棵空树上插入根结点，根节点直接赋成黑色就行
若树不空：
插入：此时z是红色，根据z->parent的颜色进行判断：
2.1）z是红色，z->parent是黑色，此时不破坏任何性质，仍然是一棵完美的红黑树，不需要调整，插入结束
2.2）z是红色，z->parent是红色，破坏“不红红”，进行调整：
设父亲节点p=z->parent，p为红色
设爷爷节点g=p->parent，因为p是红色，所以g是黑色。
设叔叔节点u为g的另一个孩子节点，则u可能是红色，也可能是黑色。
我们根据u的位置和颜色来分类：
- p=g->right; u=g->left
若u是红色：
若u是黑色： - p=g->left; u=g->right：
和1的情况反一下就行
删除
任务：在已经建立好的红黑树中删除一个数据z。
1. 先按照BST的删除操作，删除z：
1）z的左右孩子都存在（z的度为2），用z的中序遍历前驱y（或者中序遍历后继y2）节点的数据 替换 z （z->data = y->data），问题转化为删除y节点（y的度一点是0或1）
2）z的度为0或1，直接用z的唯一的孩子x（z的度为0时，x为null），顶替z的位置
最终：删除的是一个度为0或1的y节点，x顶替y的位置（x是y的唯一一个孩子）
2. 根据红黑树的性质调整： 关注x和y的颜色（x是y唯一的一个孩子）
1）简单情况：
1> y红x黑：不破坏任何性质，不需要调整
2> y黑x红：可能破坏“不红红”，一定破坏“黑路同” ——> 直接将x赋为黑色即可
2）复杂情况：y黑x黑 涉及到替换后x的兄弟节点w，p节点是x和w的父亲（y的父亲）
概念：双黑节点：删除一个度为0或1的黑色的y节点后，其黑色的孩子顶替了y的位置，顶替之后 x看成双黑节点。此时我们认为双黑节点对黑高的贡献是2。
下面的情况中，假设x是右孩子，w是左孩子。
可能情况：x（双黑）、p（黑或红）、w（黑或红）
a）w是黑色，w的孩子都是黑色
w褪一层黑色，w变成红色，褪掉的黑色给父亲p。
p本身红色，p直接变黑色，结束。
p本身是黑色，p变成双黑，p作为新的要调整的节点x，循环调整。若p为根节点，直接结束就行，整棵树的黑高减一不会破坏性质。
b）w是黑色，w的孩子存在红色
b.1）Red是w左孩子（LL）
以p为中心，w先变成p的颜色，p和r变黑色
b.2）Red是w右孩子（LR）
以w为中心左旋，w变红，r变黑，调换w和p的指针，转换为LL
c）w是红色，w的孩子都是黑色 --> 转换为 a/b
w变黑，以p为中心右旋。
若x是左孩子，w是右孩子，类似。
