nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

B Tree

B树是一颗多叉树，和二叉树比较类似,但是每个节点有多个子节点和多个键，通常我们称最多拥有N个子节点的B树为N阶B树，B树为了保证树的有序，树上节点的子节点数量恰好比键的数量多1，这就保证了存在一种方式将子节点和键排在一起，且每个键的左边、右边都是子节点，这样形成的序列即为维护的序列。

B Tree 约束

B树的节点分三类，根节点、叶子节点、内部节点(除了根节点和叶子节点以外的节点)
所有的叶子节点的深度相同,这一点保证树的平衡
根节点的键的的数量在区间[2,N-1]上 , N>=3
每个内部节点、叶子节点的键的数量在区间$[\lceil\frac{N}{2}\rceil-1,N-1]$上
每个节点的键的个数恰好比子节点个数多1

B Tree insert

B树的插入很简单，找到应该插入的叶子节点，然后插入。这会可能导致树不符合约束->叶子节点上键的数量过多，此时叶子结点上的键的数量为N，这时候我们分裂叶子节点为两个叶节点，从中取出中位数置入父节点作为划分这两个叶子节点的键。我们很容易证明$\lfloor\frac{N-1}{2}\rfloor\ge\lceil\frac{N}{2}\rceil-1$,若父节点依旧超出约束范围，同理向上继续对内部节点分裂,直道碰到根节点，若根节点依旧键的个数过多，则继续分裂，然后创建新的根节点将分裂出的节点连接。

B Tree erase

B树的删除同普通平衡树一样，若删除点出现在内部节点或根节点中，我们取出他的前驱或后继将他替换。然后再删除。我们将所有情况合并到了删除叶子节点上。若删除后树依旧满足约束，则不需要调整。若不满足约束，根据N>=3我们得出每个节点最少两个子节点，若删除位置的兄弟节点有较多键，我们只需要从兄弟节点移动一个键过来即可。若兄弟节点同样处于最少键时，我们可以合并这两个节点$2*(\lceil\frac{N}{2}\rceil-1)\le N-1$

直接二分向下即可。

注意

注意vector的 insert、erase后会导致的引用失效,

code

B Tree代码