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代码