红黑树杀杀杀
好难，学不会了喵
- 定义
一个红黑树是一个二叉搜索树只要满足：
1. 一个节点不是红的就是黑的
2. 根节点是黑的
3. 每一个叶子结点(NIL）是黑的
4. 如果一个节点是红的，那么它的两个儿子一定是黑色的
5. 对于每一个节点来说，每一条从该节点到其后代子叶子中一定包含相等数量的黑色节点数量
【Definition】 The black-height of any node x, denoted by bh(x), is the number of black nodes on any simple path from x (x not included) down to a leaf. bh(Tree) = bh(root).
A red-black tree with N internal nodes has height at most 2ln(N +1).
- 红黑树的插入操作
分情况讨论，讨论清楚各种情况所对应的旋转方式就可以了
记住就三种情况，插入一个节点首先默认他是全红的
- 红黑树的删除操作
- 删除一个叶子节点 Reset its parent link to NIL.
- 删除一个度数为1的节点 Replace the node by its single child.
- 删除一个度数为2的节点
1. Replace the node by the largest one in its left subtree or the smallest one in its right subtree.
2. Delete the replacing node from the subtree.
B+树
A B+ tree of order M is a tree with the following structural properties:
- The root is either a leaf or has between 2 and M children.
- All nonleaf nodes (except the root) have between M/2 and M children.
- All leaves are at the same depth.
- Assume each nonroot leaf also has between M/2 and M children.
很形象的图示，可以帮助你更深入的理解B+树是什么
- B+树中order的定义M
- 一般来说3-4个比较好
例子
首先是红黑树的插入操作，注意重点需要掌握一下特殊情况，然后逐层往上进行回溯，直到符合所有的要求即可
最终结果是这样，注意重复的步骤中间有一些比较复杂的地方需要注意
下面是红黑树的删除操作
可以通过执行各个选项的操作之后选择C
下面对红黑树的插入和删除操作进行一个汇总
红黑树的插入操作
- 如果原来的树是空的，插入一个节点之后不需要做任何的修正
- 当前的父节点为根节点并且为黑色，也是不需要做任何的修正
- 如果当前的节点的父节点为根节点，并且为红色，只需要把根节点染黑就可以
- 当前节点 N 的父节点 P 和叔节点 U 均为红色，此时 P 包含了一个红色子节点，违反了红黑树的性质，需要进行重新染色。由于在当前节点 N 之前该树是一棵合法的红黑树，根据性质 3 可以确定 N 的祖父节点 G 一定是黑色，这时只要后续操作可以保证以 G 为根节点的子树在不违反性质 4 的情况下再递归维护祖父节点 G 以保证性质 3 即可。
因此只需要：
1. 把PU节点都染黑
2.再递归的维护G节点
- 当前节点 N 与父节点 P 的方向相反（即 N 节点为右子节点且父节点为左子节点，或 N 节点为左子节点且父节点为右子节点。类似 AVL 树中 LR 和 RL 的情况）。根据性质 4，若 N 为新插入节点，U 则为 NIL 黑色节点，否则为普通黑色节点。
该种情况无法直接进行维护，需要通过旋转操作将子树结构调整为 Case 6 的初始状态并进入 Case 6 进行后续维护。
- 当前节点 N 与父节点 P 的方向相同（即 N 节点为右子节点且父节点为右子节点，或 N 节点为左子节点且父节点为右子节点。类似 AVL 树中 LL 和 RR 的情况）。根据性质 4，若 N 为新插入节点，U 则为 NIL 黑色节点，否则为普通黑色节点。注意与case4的区别
- 若 N 为左子节点则右旋祖父节点 G，否则左旋祖父节点 G.（该操作使得旋转过后 P - N 这条路径上的黑色节点个数比 P - G - U 这条路径上少 1，暂时打破性质 4）。
- 重新染色，将 P 染黑，将 G 染红，同时满足了性质 3 和 4。
在这种情况下，若想在不改变结构的情况下使得子树满足性质 3，则需将 G 染成红色，将 P 染成黑色。但若这样维护的话则性质 4 被打破，且无法保证在 G 节点的父节点上性质 3 是否成立。而选择通过旋转改变子树结构后再进行重新染色即可同时满足性质 3 和 4。
因此，这种情况的维护需要：
红黑树的删除操作
- 若待删除节点为根节点的话，直接删除即可，这里不将其算作删除操作的 3 种基本情况中。
- 若待删除节点 N 既有左子节点又有右子节点，则需找到它的前驱或后继节点进行替换（仅替换数据，不改变节点颜色和内部引用关系），则后续操作中只需要将后继节点删除即可。这部分操作与普通 BST 完全相同，在此不再过多赘述。
注：这里选择的前驱或后继节点保证不会是一个既有非 NIL 左子节点又有非 NIL 右子节点的节点。这里拿后继节点进行简单说明：若该节点包含非空左子节点，则该节点并非是 N 节点右子树上键值最小的节点，与后继节点的性质矛盾，因此后继节点的左子节点必须为 NIL。
待删除节点为叶子节点，若该节点为红色，直接删除即可，删除后仍能保证红黑树的 4 条性质。若为黑色，删除后性质 4 被打破，需要重新进行维护。
注：由于维护操作不会改变待删除节点的任何结构和数据，因此此处的代码示例中为了实现方便起见选择先进行维护，再解引用相关节点。
- 待删除节点 N 有且仅有一个非 NIL 子节点，则子节点 S 一定为红色。因为如果子节点 S 为黑色，则 S 的黑深度和待删除结点的黑深度不同，违反性质 4。由于子节点 S 为红色，则待删除节点 N 为黑色，直接使用子节点 S 替代 N 并将其染黑后即可满足性质 4。
root是leaf的情况没有考虑吧
所有的叶子一定都在同一深度
需要除去根部，根是2-M
需要注意的是B+树的删除操作
注意操作即可
红黑树是一种自平衡的二叉搜索树，这意味着它通过一些额外的规则和操作，保持树的平衡，确保查找、插入和删除操作的效率。在红黑树中删除一个节点可能是比较复杂的，因为需要在删除节点后调整树，以保持满足红黑树的性质。下面我将详细介绍红黑树的删除操作步骤。
红黑树的性质
在详细介绍删除操作之前，首先回顾一下红黑树的五大性质：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色的。
- 所有叶子节点（NIL节点，空节点）都是黑色的。
- 每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
删除操作
删除操作可以分为三个主要步骤：找到要删除的节点，删除节点，然后重新调整树以保持红黑树的性质。
1. 找到要删除的节点
首先，和在普通的二叉搜索树中一样，我们需要找到要删除的节点。这通过比较待删除键与节点键来完成，如果待删除键小于节点键，就转到左子树，否则转到右子树，直到找到该键或者找到一个叶子节点（表明键不存在）。
2. 删除节点
一旦找到要删除的节点，就有以下几种情况：
- 节点是叶子节点：直接删除它。
- 节点有一个子节点：删除该节点，并用其子节点替代它。
- 节点有两个子节点：找到该节点的中序后继（右子树中的最小节点），用其值替代要删除的节点的值，然后删除中序后继节点。中序后继节点是没有左子树的，因此更易于删除。
3. 重新调整树（复杂的部分）
删除节点可能会破坏红黑树的性质，尤其是如果被删除的或被移动的是黑色节点。这时，需要通过一系列的树旋转和重新着色来修复这些性质。调整过程主要关注以下几种情况：
- 情况1：被删除节点的兄弟节点是红色。解决办法是重新着色并旋转。
- 情况2：被删除节点的兄弟节点是黑色，并且该兄弟节点的两个子节点都是黑色。解决办法是重新着色，并递归向上调整。
- 情况3：被删除节点的兄弟节点是黑色，兄弟的左子是红色，右子是黑色。解决办法是重新着色和旋转。
- 情况4：被删除节点的兄弟节点是黑色，且兄弟的右子是红色。解决办法是旋转并重新着色，然后结束调整。
这些调整保证了在删除节点后，红黑树依旧保持平衡，确保了其操作的高效性。
总结
红黑树的删除操作可能涉及复杂的调整步骤，但这些步骤至关重要，以确保树的平衡性和操作效率。实际编程实现时，需要仔细处理